Changeset 30

Timestamp:

12/31/06 11:53:18 (2 years ago)

Author:

chris

Message:

- Change to chart parser, initial implementation works with standard rules, but not permutable or searching rules

Files:

• lex/trunk (modified) (1 prop)
• lex/trunk/src/com/qwirx/lex/HebrewConverter.java (added)
• lex/trunk/src/com/qwirx/lex/parser/Chart.java (added)
• lex/trunk/src/com/qwirx/lex/parser/Edge.java (modified) (1 diff)
• lex/trunk/src/com/qwirx/lex/parser/EdgeBase.java (modified) (2 diffs)
• lex/trunk/src/com/qwirx/lex/parser/Parser.java (modified) (4 diffs)
• lex/trunk/src/com/qwirx/lex/parser/Rule.java (modified) (11 diffs)
• lex/trunk/src/com/qwirx/lex/parser/RuleEdge.java (modified) (12 diffs)
• lex/trunk/src/com/qwirx/lex/parser/WordEdge.java (modified) (4 diffs)
• lex/trunk/test/com/qwirx/lex/ParserTest.java (modified) (31 diffs)

lex/trunk/src/com/qwirx/lex/parser/Edge.java

@@ -29 +29 @@
-    Edge getBoundCopy();
-    Edge getUnboundCopy();
+    
+    boolean isAt(int pos);
-}

lex/trunk/src/com/qwirx/lex/parser/EdgeBase.java

@@ -71 +71 @@
-     * @param b The second Instance (actual)
-     */
+    /*
-    public boolean equals(Object object)
-    {
@@ -142 +143 @@
-        return true;
-    }
+    */
-}

lex/trunk/src/com/qwirx/lex/parser/Parser.java

@@ -9 +9 @@
-import java.sql.ResultSet;
-import java.sql.SQLException;
+import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Stack;
-import java.util.Vector;
-
-import com.qwirx.lex.DatabaseException;
-import com.qwirx.lex.parser.Rule.Match;
-import com.qwirx.lex.sql.SqlDatabase;
-
@@ -24 +23 @@
- * Window - Preferences - Java - Code Style - Code Templates
- */
-
+
+
-        private Rule [] rules;
-        
-
+
+
-                Vector ruleV = new Vector();
-                
@@ -57 +58 @@
-        }
-        
-Edge[][]
+Chart
-    {
-                String[] words = input.split(" ");
-
-
-
+
-                
-                for (int i = 0; i < words.length; i++) 
-        {
-
+
+
+
-            {
-
-
-
+
+
+
+
+
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
-                        }
-                }
-
-                System.out.println("Parse finished.");
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
-        }
-
-Edge[][]
+List
-    {
-        return parseFor(input, goal, false);
-    }
-    
+    /*
-    private String getStringFromArray(Object [] array)
-    {
@@ -141 +108 @@
-        return sb.toString();
-    }
+    */
-
-Edge[][]
+List
-    {
-Edge[][] parseResults
+Chart chart
-                
-
-
+
+
+
+
-        {
-                       Edge[] result = parseResults[i]
-
-                       
+            Edge edge = (Edge)( i.next() )
+
+            
-                if (verbose)
-                {
-
-
+
-                }   
-
-
-
-
-
-
-
-
-
-
-
+
-                continue;
-            }
-            
-                    results.add(result)
+         boolean hasHoles = false
-            
-if (!verbose
+for (int j = 0; j < chart.getWidth(); j++
-            {
+                if (! edge.isAt(j))
+                {
+                    hasHoles = true;
+                    break;
+                }
+            }
+            
+            if (hasHoles)
+            {
+                if (verbose)
+                {
+                    System.out.println("Rejected edge with holes: " + edge);
+                }   
-                continue;
-            }
-            
-            System.out.println("Accepted stack "+(i+1)+":"
-
-for (int j = 0; j < result.length; j++) 
+                    goals.add(edge
+
+if (verbose)
-            {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
-                }
-                
-
-
-
+
-        }
-}

lex/trunk/src/com/qwirx/lex/parser/Rule.java

@@ -7 +7 @@
-package com.qwirx.lex.parser;
-
+import java.util.ArrayList;
-import java.util.Hashtable;
-import java.util.Iterator;
@@ -24 +25 @@
-        private final boolean     m_isPermutable;
-    private final boolean     m_isSearching;
+    private final List []     m_PartBindingLists; 
+    private final boolean []  m_PartsFinished;
+    private       boolean []  m_PositionsUsed;
-    
-        public Rule
@@ -37 +41 @@
-                this.fixedAttrs = fixedAttrs;
-                this.copyAttrs  = copyAttrs;
-
-
+
+
+
+
+
+
+
+
+
+
+
-        }
-
@@ -207 +220 @@
-    
-    private int m_NumPartsRemaining;
-    private boolean [] m_PartsAlreadyUsed;
-    
-    private void hidePart(int index)
-    {
-AlreadyUs
+Finish
-        {
-            throw new AssertionError("the current rule part should " +
-                "not be marked to be skipped");
-        }
-AlreadyUs
+Finish
-        
-        if (m_NumPartsRemaining <= 0)
@@ -228 +240 @@
-    private void unhidePart(int index)
-    {
-AlreadyUs
+Finish
-        {
-            throw new AssertionError("the current rule part should " +
-                "be marked to be skipped");
-        }
-AlreadyUs
+Finish
-        
-        if (m_NumPartsRemaining >= right.length)
@@ -243 +255 @@
-    }
-    
+    private Chart m_CurrentChart;
+    
+    /** 
+     * Public entry point for parsing.
+     * @param chart A chart containing existing edges to apply to
+     * @param endPos The right-hand side of the chart, where this rule is
+     * required to match this time (it may match elsewhere as well) 
+     * @return A list of new Edges to be added to the Chart
+     */
+    public List applyTo(Chart chart, int endPos)
+    {
+        m_CurrentChart = chart;
+        
+        // debugging code
+        for (int i = 0; i < right.length; i++)
+        {
+            if (m_PartBindingLists[i].size() > 0)
+            {
+                throw new AssertionError
+                (
+                    "the part binding list should be empty at the start of " +
+                    "the parse"
+                );
+            }
+            
+            if (m_PartsFinished[i])
+            {
+                throw new AssertionError
+                (
+                    "no parts should be already used at the start of the parse"
+                );
+                
+            }
+        }
+        
+        m_PositionsUsed = new boolean[endPos + 1];
+
+        // we must always match an edge at the specified end position,
+        // which will be different every time we are called,
+        // otherwise we will generate duplicate edges.
+        
+        List oldEdges = chart.getEdgesAt(endPos);
+        List newEdges = new ArrayList();
+        
+        if (m_isSearching || m_isPermutable)
+        {
+            // any part can match one or more edges
+            
+        }
+        else
+        {
+            // the last part must match one or more edges,
+            // unless it's optional, in which case it might be skipped
+            // and the last-but-one might match, etc.
+            
+            int firstPartSkipped = right.length;
+            
+            for (int partIndex = right.length - 1; partIndex >= 0; partIndex--)
+            {
+                RulePart part = right[partIndex];
+                
+                for (Iterator i = oldEdges.iterator(); i.hasNext(); )
+                {
+                    Edge edge = (Edge)( i.next() );
+                    if (part.matches(edge))
+                    {
+                        bindAndContinueParse(partIndex, edge, newEdges);
+                    }
+                }
+                
+                if (!part.canSkip())
+                {
+                    break;
+                }
+                
+                m_PartsFinished[partIndex] = true;
+                firstPartSkipped = partIndex;
+            }
+            
+            for (int i = firstPartSkipped; i < right.length; i++)
+            {
+                if (!m_PartsFinished[i]) throw new AssertionError();
+                m_PartsFinished[i] = false;
+            }
+        }
+        
+        return newEdges;
+    }
+    
+    private void bindAndContinueParse(int partIndex, Edge edge, List newEdges)
+    {
+        for (int i = 0; i < right.length; i++)
+        {
+            if (m_PartBindingLists[i].contains(edge))
+            {
+                throw new AssertionError
+                (
+                    "No part binding list should already contain this edge"
+                );
+            }
+        }
+
+        m_PartBindingLists[partIndex].add(0, edge);
+
+        if (m_PartsFinished[partIndex])
+        {
+            throw new AssertionError
+            (
+                "Not allowed to bind a rule part that is already finished"
+            );
+        }
+        
+        for (int i = 0; i < m_PositionsUsed.length; i++)
+        {
+            if (!edge.isAt(i))
+            {
+                continue;
+            }
+            
+            if (m_PositionsUsed[i])
+            {
+                throw new AssertionError
+                (
+                    "Not allowed to bind an edge that overlaps an existing " +
+                    "bound edge"
+                );
+            }
+            
+            m_PositionsUsed[i] = true;
+        }
+        
+        if (right[partIndex].canRepeat())
+        {
+            continueParseWithThisPart(partIndex, true, newEdges);
+        }
+        else
+        {
+            m_PartsFinished[partIndex] = true;
+            continueParseWithNextPart(newEdges);        
+            m_PartsFinished[partIndex] = false;
+        }
+        
+        for (int i = 0; i < m_PositionsUsed.length; i++)
+        {
+            if (!edge.isAt(i))
+            {
+                continue;
+            }
+            
+            if (!m_PositionsUsed[i])
+            {
+                throw new AssertionError
+                (
+                    "Positions used by this edge should be marked as used"
+                );
+            }
+            
+            m_PositionsUsed[i] = false;
+        }
+
+        for (int i = 0; i < right.length; i++)
+        {
+            if (i == partIndex)
+            {
+                if (!m_PartBindingLists[i].contains(edge))
+                {
+                    throw new AssertionError
+                    (
+                        "The part binding list for this part should " +
+                        "contain this edge"
+                    );
+                }
+            }
+            else
+            {
+                if (m_PartBindingLists[i].contains(edge))
+                {
+                    throw new AssertionError
+                    (
+                        "No other part binding list should contain this edge"
+                    );
+                }
+            }
+        }
+
+        m_PartBindingLists[partIndex].remove(edge);
+    }
+
+    private void continueParseWithNextPart(List newEdges)
+    {
+        boolean foundUnfinishedPart = false;
+        
+        for (int i = right.length - 1; i >= 0; i--)
+        {
+            if (m_PartsFinished[i])
+            {
+                continue;
+            }
+            
+            foundUnfinishedPart = true;
+            
+            continueParseWithThisPart(i, false, newEdges);
+            
+            // reordering of elements in permutable rules happens here,
+            // by allowing the loop to proceed with the next unfinished part.
+            if (!m_isPermutable)
+            {
+                return;
+            }
+        }
+        
+        if (foundUnfinishedPart)
+        {
+            return;
+        }
+        
+        // base case: we end up here when all parts have been used,
+        // and we should be ready to create a new edge.
+        
+        // don't create new edges which don't contain any other edges:
+        // we could keep doing that forever.
+        
+        int numEdges = 0;
+        
+        for (int i = 0; i < right.length; i++)
+        {
+            numEdges += m_PartBindingLists[i].size();
+        }
+        
+        if (numEdges == 0)
+        {
+            return;
+        }
+
+        int position = 0;
+        Edge[] contained = new Edge[numEdges];
+        
+        for (int i = 0; i < right.length; i++)
+        {
+            for (Iterator j = m_PartBindingLists[i].iterator(); j.hasNext(); )
+            {
+                Edge edge = (Edge)( j.next() );
+                Edge unbound = edge.getUnboundCopy();
+                try
+                {
+                    unbound.bindTo(null, right[i]);
+                }
+                catch (AlreadyBoundException e)
+                {
+                    throw new AssertionError(e);
+                }
+                contained[position++] = unbound;
+            }
+        }
+        
+        if (position != numEdges)
+        {
+            throw new AssertionError();
+        }
+        
+        Edge newEdge = new RuleEdge(this, contained);
+        newEdges.add(newEdge);       
+    }
+
+    private void continueParseWithThisPart(int partIndex, boolean hasMatched,
+        List newEdges)
+    {
+        if (m_PartsFinished[partIndex])
+        {
+            throw new AssertionError
+            (
+                "Not allowed to bind a rule part that is already finished"
+            );
+        }
+
+        // find any other edges that we can use
+        
+        int rightmostEmptyPos = -1;
+        for (int i = m_PositionsUsed.length - 1; i >= 0; i--)
+        {
+            if (!m_PositionsUsed[i])
+            {
+                rightmostEmptyPos = i;
+                break;
+            }
+        }
+        
+        List edges = m_CurrentChart.getEdgesAt(rightmostEmptyPos);
+        RulePart part = right[partIndex];
+                
+        for (Iterator i = edges.iterator(); i.hasNext(); )
+        {
+            Edge edge = (Edge)( i.next() );
+            if (!part.matches(edge))
+            {
+                continue;
+            }
+            
+            // check that the edge doesn't overlap any previously chosen ones
+            boolean overlaps = false;
+            for (int j = rightmostEmptyPos + 1; 
+                j < m_CurrentChart.getWidth(); j++)
+            {
+                if (edge.isAt(j))
+                {
+                    overlaps = true;
+                    break;
+                }
+            }
+            
+            if (overlaps == true)
+            {
+                continue;
+            }
+            
+            bindAndContinueParse(partIndex, edge, newEdges);
+        }
+        
+        // Optional elements may only be skipped (match 0 times)
+        // in permutable rules if no matches have yet been made.
+        // This enforces the condition that they may not match 
+        // nothing at different places in the same input, which 
+        // would produce duplicate trees in the output.
+        
+        boolean canSkip = part.canSkip();
+        
+        if (canSkip && m_isPermutable)
+        {
+            for (int i = 0; i < m_PositionsUsed.length; i++)
+            {
+                if (m_PositionsUsed[i])
+                {
+                    canSkip = false;
+                    break;
+                }
+            }
+        }
+
+        // stop now if this part is not optional and has not matched yet
+        if (!canSkip && !hasMatched)
+        {
+            return;
+        }
+        
+        // mark it as finished, so we can move onto the next part
+        // (in the case where it is optional and being skipped)
+        
+        m_PartsFinished[partIndex] = true;
+        
+        continueParseWithNextPart(newEdges);
+        
+        if (!m_PartsFinished[partIndex])
+        {
+            throw new AssertionError("this part should still be marked" +
+                "as fininshed");
+        }
+        
+        m_PartsFinished[partIndex] = false;
+    }
+
-    private void apply(List stack, Match match, List out)
-    {
@@ -251 +623 @@
-            for (int i = 0; i < right.length; i++)
-            {
-AlreadyUs
+Finish
-                {
-                    realNumPartsRemaining--;
@@ -321 +693 @@
-            for (int i = right.length - 1; i >= 0; i--)
-            {
-AlreadyUs
+Finish
-                {
-                    firstRulePartIndex = i;
@@ -339 +711 @@
-        for (int i = firstRulePartIndex; i < right.length; i++)
-        {
-AlreadyUs
+Finish
-            {
-                // the caller has processed this part, and asked us to skip it
@@ -528 +900 @@
-            for (int i = right.length - 1; i >= 0; i--)
-            {
-AlreadyUs
+Finish
-                {
-                    nextPartIndex = i;
@@ -566 +938 @@
-        Match match = new Match(right.length);
-        List out = new Vector();
-
+
+
+
+
-        m_NumPartsRemaining = right.length;
-        apply(stack, match, out);

lex/trunk/src/com/qwirx/lex/parser/RuleEdge.java

@@ -16 +16 @@
-{
-        private final Edge [] parts;
-    
+
-        private Map attribs = new Hashtable();
-        
@@ -54 +54 @@
-                super();
-        this.rule  = rule;
-
+
+
-        
-        for (int i = 0; i < this.parts.length; i++)
@@ -104 +105 @@
-        }
-    
-
+
+
-                StringBuffer buf = new StringBuffer();
-                appendString(buf);
-                return buf.toString();
-        }
-
+
+
+
-                buf.append("{");
-                buf.append(rule().symbol());
@@ -115 +119 @@
-                
-                Map attribs = attributes();
-
+
+
-                        Entry e = (Entry)( i.next() );
-                        buf.append(e.getKey());
@@ -142 +147 @@
-                buf.append("}");
-        }
-
+
+
+
-                appendStringPrettyPrint(buf, "");
-        }
-
+
+
+
-                buf.append(indent);
-                buf.append("{");
@@ -152 +161 @@
-                
-                Map attribs = attributes();
-
+
+
-                        Entry e = (Entry)( i.next() );
-                        buf.append(e.getKey());
@@ -190 +200 @@
-                buf.append("}");
-        }
-
+
+
+
-                Vector v = new Vector();
-                appendWords(v);
-                return (String[])( v.toArray(new String[v.size()]) );
-        }
-
-
+
+
+
+
+
-                        parts[i].appendWords(words);
-                }
-        }
-
+
+
+
-                Edge [] result = new Edge[parts.length];
-                System.arraycopy(parts, 0, result, 0, parts.length);
@@ -219 +236 @@
-        
-    public Map attributes() { return attribs; }
-
+
+
-                attribs = new Hashtable();
-                
@@ -240 +258 @@
-                                
-                                Edge partInstance = parts[p];
+                
-                                Object value = partInstance.attributes().get(name);
-
+
+
+
-                                        throw new IllegalStateException(
-                                                        partInstance.toString()+
@@ -247 +268 @@
-                                                        name+" to copy into "+this);
-                                }
+                
-                                Object oldValue = attribs.get(name);
-
+
+
+
-                                        throw new IllegalStateException(
-                                                        "Unable to unify "+oldValue+" and "+value+
-                                                        " for attribute "+name+" of "+this);
-                                }
-
+
+
+
-                                        attribs.put(name, value);
-                                }
@@ -281 +307 @@
-                }
-        }
-
+
+
+
-                return getDepthScore(1);
-        }
-
+
+
+
-                int d = initialDepth;
-
-
+
+
+
+
-                                d += ((RuleEdge)(parts[i])).getDepthScore(initialDepth+1);
-                        }
@@ -293 +325 @@
-                return d;
-        }
+    
-    public Edge getUnboundCopy()
-    {
-        return new RuleEdge(rule, parts);
-    }
+    
+    public boolean isAt(int position)
+    {
+        for (int i = 0; i < parts.length; i++)
+        {
+            if (parts[i].isAt(position))
+            {
+                return true;
+            }
+        }
+        
+        return false;
+    }
-}

lex/trunk/src/com/qwirx/lex/parser/WordEdge.java

@@ -19 +19 @@
-    private static final Edge[]   parts   = new Edge[0];
-    private static final ImmutableMap attribs = new