Changeset 30

Show
Ignore:
Timestamp:
12/31/06 11:53:18 (5 years ago)
Author:
chris
Message:

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

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • lex/trunk

    • Property svn:ignore set to

      work

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

    r26 r30  
    2929    Edge getBoundCopy(); 
    3030    Edge getUnboundCopy(); 
     31     
     32    boolean isAt(int pos); 
    3133} 

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

    r26 r30  
    7171     * @param b The second Instance (actual) 
    7272     */ 
     73    /* 
    7374    public boolean equals(Object object) 
    7475    { 
    …… 
    142143        return true; 
    143144    } 
     145    */ 
    144146} 

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

    r26 r30  
    99import java.sql.ResultSet; 
    1010import java.sql.SQLException; 
     11import java.util.ArrayList; 
    1112import java.util.Iterator; 
    1213import java.util.List; 
    13 import java.util.Stack; 
    1414import java.util.Vector; 
    1515 
    1616import com.qwirx.lex.DatabaseException; 
    17 import com.qwirx.lex.parser.Rule.Match; 
    1817import com.qwirx.lex.sql.SqlDatabase; 
    1918 
    …… 
    2423 * Window - Preferences - Java - Code Style - Code Templates 
    2524 */ 
    26 public class Parser { 
     25public class Parser  
     26{ 
    2727        private Rule [] rules; 
    2828         
    29         public Parser(SqlDatabase db) throws DatabaseException, SQLException { 
     29        public Parser(SqlDatabase db) throws DatabaseException, SQLException  
     30    { 
    3031                Vector ruleV = new Vector(); 
    3132                 
    …… 
    5758        } 
    5859         
    59         public Edge[][] parse(String input)  
     60        public Chart parse(String input)  
    6061    { 
    6162                String[] words = input.split(" "); 
    62                  
    63                 Vector stacks = new Vector(); 
    64                 stacks.add(new Stack()); 
     63        Chart chart = new Chart(words.length); 
    6564                 
    6665                for (int i = 0; i < words.length; i++)  
    6766        { 
    68             for (int s = 0; s < stacks.size(); s++)  
     67            chart.add(new WordEdge(words[i], i)); 
     68             
     69                        for (int r = 0; r < rules.length; r++)  
    6970            { 
    70                 Stack stack = (Stack)( stacks.get(s) ); 
    71                 stack.push(new WordEdge(words[i])); 
    72             } 
     71                                /* 
     72                if (r == 4 && s == 5) 
     73                { 
     74                    System.out.println("boo"); 
     75                } 
     76                                */ 
    7377 
    74                         for (int s = 0; s < stacks.size(); s++)  
    75             { 
    76                                 Stack oldStack = (Stack)( stacks.get(s) ); 
    77                          
    78                                 for (int r = 0; r < rules.length; r++)  
    79                 { 
    80                                         /* 
    81                     if (r == 4 && s == 5) 
    82                     { 
    83                         System.out.println("boo"); 
    84                     } 
    85                                         */ 
    86  
    87                     Rule rule = rules[r]; 
    88                     List matches = rule.applyTo(oldStack); 
    89                      
    90                     for (Iterator m = matches.iterator(); m.hasNext(); ) 
    91                     { 
    92                         Match match = (Match)( m.next() ); 
    93                         // System.out.println(stacks.size() + ": " + match.stack); 
    94                         stacks.add(match.stack); 
    95                     } 
    96                                 } 
     78                Rule rule = rules[r]; 
     79                List newEdges = rule.applyTo(chart, i); 
     80                chart.add(newEdges); 
    9781                        } 
    9882                } 
    9983 
    10084                System.out.println("Parse finished."); 
    101                 Edge[][] results = new Edge[stacks.size()][]; 
    102  
    103                 for (int i = 0; i < stacks.size(); i++)  
    104         { 
    105                         Stack stack = (Stack)( stacks.get(i) ); 
    106                         // System.out.println("Stack "+(i+1)+" contains:"); 
    107  
    108                         Edge[] thisResult = new Edge[stack.size()]; 
    109  
    110                         for (int j = 0; j < stack.size(); j++)  
    111             { 
    112                                 // System.out.println(j+": "+ 
    113                                 //      stack.get(j).toString()); 
    114                                 thisResult[j] = (Edge)( stack.get(j) ); 
    115                         } 
    116                          
    117                         results[i] = thisResult; 
    118                 } 
    119                  
    120                 return results; 
     85         
     86        return chart; 
    12187        } 
    12288 
    123     public Edge[][] parseFor(String input, String goal) 
     89    public List parseFor(String input, String goal) 
    12490    { 
    12591        return parseFor(input, goal, false); 
    12692    } 
    12793     
     94    /* 
    12895    private String getStringFromArray(Object [] array) 
    12996    { 
    …… 
    141108        return sb.toString(); 
    142109    } 
     110    */ 
    143111 
    144         public Edge[][] parseFor(String input, String goal, boolean verbose)  
     112        public List parseFor(String input, String goal, boolean verbose)  
    145113    { 
    146                 Edge[][] parseResults = parse(input); 
     114                Chart chart = parse(input); 
    147115                 
    148                 Vector results = new Vector(); 
    149                 for (int i = 0; i < parseResults.length; i++)  
     116        List edges = chart.getEdges(); 
     117                List goals = new ArrayList(); 
     118         
     119                for (Iterator i = edges.iterator(); i.hasNext(); )  
    150120        { 
    151                        Edge[] result = parseResults[i]; 
    152                         if (result.length > 1)  
    153                        { 
     121            Edge edge = (Edge)( i.next() ); 
     122            if (! edge.symbol().equals(goal)) 
     123            { 
    154124                if (verbose) 
    155125                { 
    156                     System.out.println("Rejected stack " + (i+1) + 
    157                         ": too long: " + getStringFromArray(result)); 
     126                    System.out.println("Rejected non-goal edge: " + edge); 
    158127                }    
    159                 continue; 
    160                         } 
    161                          
    162             String symbol = result[0].symbol(); 
    163                         if (! symbol.equals(goal))  
    164             { 
    165                             if (verbose) 
    166                 { 
    167                     System.out.println("Rejected stack " + (i+1) + 
    168                         ": not " + goal + ": " + getStringFromArray(result)); 
    169                 } 
     128                 
    170129                continue; 
    171130            } 
    172131             
    173                        results.add(result); 
     132            boolean hasHoles = false; 
    174133             
    175             if (!verbose) 
     134            for (int j = 0; j < chart.getWidth(); j++) 
    176135            { 
     136                if (! edge.isAt(j)) 
     137                { 
     138                    hasHoles = true; 
     139                    break; 
     140                } 
     141            } 
     142             
     143            if (hasHoles) 
     144            { 
     145                if (verbose) 
     146                { 
     147                    System.out.println("Rejected edge with holes: " + edge); 
     148                }    
    177149                continue; 
    178150            } 
    179151             
    180                System.out.println("Accepted stack "+(i+1)+":"); 
    181              
    182             for (int j = 0; j < result.length; j++)  
     152                       goals.add(edge); 
     153 
     154            if (verbose) 
    183155            { 
    184                                 if (result[j] instanceof RuleEdge)  
    185                 { 
    186                                         RuleEdge instance = (RuleEdge)( result[j] ); 
    187                                         StringBuffer buf = new StringBuffer(); 
    188                                         instance.appendStringPrettyPrint(buf); 
    189                                         System.out.println(buf.toString()); 
    190                                 }  
    191                 else  
    192                 { 
    193                                         System.out.print(result[j]); 
    194                                         System.out.print(" "); 
    195                                 } 
    196                         } 
    197              
    198                         System.out.println(""); 
     156                System.out.println("Accepted edge: " + edge); 
     157            }    
    199158                } 
    200159                 
    201                 Edge[][] resultArray = new Edge[results.size()][]; 
    202                 resultArray = (Edge[][])( results.toArray(resultArray) ); 
    203                 return resultArray; 
     160                return goals; 
    204161        } 
    205162} 

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

    r26 r30  
    77package com.qwirx.lex.parser; 
    88 
     9import java.util.ArrayList; 
    910import java.util.Hashtable; 
    1011import java.util.Iterator; 
    …… 
    2425        private final boolean     m_isPermutable; 
    2526    private final boolean     m_isSearching; 
     27    private final List []     m_PartBindingLists;  
     28    private final boolean []  m_PartsFinished; 
     29    private       boolean []  m_PositionsUsed; 
    2630     
    2731        public Rule 
    …… 
    3741                this.fixedAttrs = fixedAttrs; 
    3842                this.copyAttrs  = copyAttrs; 
    39         this.m_isPermutable = isPermutable; 
    40         this.m_isSearching  = isSearching; 
     43         
     44        m_isPermutable = isPermutable; 
     45        m_isSearching  = isSearching; 
     46        m_PartBindingLists = new List [right.length]; 
     47        m_PartsFinished = new boolean [right.length]; 
     48         
     49        for (int i = 0; i < right.length; i++) 
     50        { 
     51            m_PartBindingLists[i] = new ArrayList(); 
     52            m_PartsFinished[i] = false; 
     53        } 
    4154        } 
    4255 
    …… 
    207220     
    208221    private int m_NumPartsRemaining; 
    209     private boolean [] m_PartsAlreadyUsed; 
    210222     
    211223    private void hidePart(int index) 
    212224    { 
    213         if (m_PartsAlreadyUsed[index]) 
     225        if (m_PartsFinished[index]) 
    214226        { 
    215227            throw new AssertionError("the current rule part should " + 
    216228                "not be marked to be skipped"); 
    217229        } 
    218         m_PartsAlreadyUsed[index] = true; 
     230        m_PartsFinished[index] = true; 
    219231         
    220232        if (m_NumPartsRemaining <= 0) 
    …… 
    228240    private void unhidePart(int index) 
    229241    { 
    230         if (!m_PartsAlreadyUsed[index]) 
     242        if (!m_PartsFinished[index]) 
    231243        { 
    232244            throw new AssertionError("the current rule part should " + 
    233245                "be marked to be skipped"); 
    234246        } 
    235         m_PartsAlreadyUsed[index] = false; 
     247        m_PartsFinished[index] = false; 
    236248         
    237249        if (m_NumPartsRemaining >= right.length) 
    …… 
    243255    } 
    244256     
     257    private Chart m_CurrentChart; 
     258     
     259    /**  
     260     * Public entry point for parsing. 
     261     * @param chart A chart containing existing edges to apply to 
     262     * @param endPos The right-hand side of the chart, where this rule is 
     263     * required to match this time (it may match elsewhere as well)  
     264     * @return A list of new Edges to be added to the Chart 
     265     */ 
     266    public List applyTo(Chart chart, int endPos) 
     267    { 
     268        m_CurrentChart = chart; 
     269         
     270        // debugging code 
     271        for (int i = 0; i < right.length; i++) 
     272        { 
     273            if (m_PartBindingLists[i].size() > 0) 
     274            { 
     275                throw new AssertionError 
     276                ( 
     277                    "the part binding list should be empty at the start of " + 
     278                    "the parse" 
     279                ); 
     280            } 
     281             
     282            if (m_PartsFinished[i]) 
     283            { 
     284                throw new AssertionError 
     285                ( 
     286                    "no parts should be already used at the start of the parse" 
     287                ); 
     288                 
     289            } 
     290        } 
     291         
     292        m_PositionsUsed = new boolean[endPos + 1]; 
     293 
     294        // we must always match an edge at the specified end position, 
     295        // which will be different every time we are called, 
     296        // otherwise we will generate duplicate edges. 
     297         
     298        List oldEdges = chart.getEdgesAt(endPos); 
     299        List newEdges = new ArrayList(); 
     300         
     301        if (m_isSearching || m_isPermutable) 
     302        { 
     303            // any part can match one or more edges 
     304             
     305        } 
     306        else 
     307        { 
     308            // the last part must match one or more edges, 
     309            // unless it's optional, in which case it might be skipped 
     310            // and the last-but-one might match, etc. 
     311             
     312            int firstPartSkipped = right.length; 
     313             
     314            for (int partIndex = right.length - 1; partIndex >= 0; partIndex--) 
     315            { 
     316                RulePart part = right[partIndex]; 
     317                 
     318                for (Iterator i = oldEdges.iterator(); i.hasNext(); ) 
     319                { 
     320                    Edge edge = (Edge)( i.next() ); 
     321                    if (part.matches(edge)) 
     322                    { 
     323                        bindAndContinueParse(partIndex, edge, newEdges); 
     324                    } 
     325                } 
     326                 
     327                if (!part.canSkip()) 
     328                { 
     329                    break; 
     330                } 
     331                 
     332                m_PartsFinished[partIndex] = true; 
     333                firstPartSkipped = partIndex; 
     334            } 
     335             
     336            for (int i = firstPartSkipped; i < right.length; i++) 
     337            { 
     338                if (!m_PartsFinished[i]) throw new AssertionError(); 
     339                m_PartsFinished[i] = false; 
     340            } 
     341        } 
     342         
     343        return newEdges; 
     344    } 
     345     
     346    private void bindAndContinueParse(int partIndex, Edge edge, List newEdges) 
     347    { 
     348        for (int i = 0; i < right.length; i++) 
     349        { 
     350            if (m_PartBindingLists[i].contains(edge)) 
     351            { 
     352                throw new AssertionError 
     353                ( 
     354                    "No part binding list should already contain this edge" 
     355                ); 
     356            } 
     357        } 
     358 
     359        m_PartBindingLists[partIndex].add(0, edge); 
     360 
     361        if (m_PartsFinished[partIndex]) 
     362        { 
     363            throw new AssertionError 
     364            ( 
     365                "Not allowed to bind a rule part that is already finished" 
     366            ); 
     367        } 
     368         
     369        for (int i = 0; i < m_PositionsUsed.length; i++) 
     370        { 
     371            if (!edge.isAt(i)) 
     372            { 
     373                continue; 
     374            } 
     375             
     376            if (m_PositionsUsed[i]) 
     377            { 
     378                throw new AssertionError 
     379                ( 
     380                    "Not allowed to bind an edge that overlaps an existing " + 
     381                    "bound edge" 
     382                ); 
     383            } 
     384             
     385            m_PositionsUsed[i] = true; 
     386        } 
     387         
     388        if (right[partIndex].canRepeat()) 
     389        { 
     390            continueParseWithThisPart(partIndex, true, newEdges); 
     391        } 
     392        else 
     393        { 
     394            m_PartsFinished[partIndex] = true; 
     395            continueParseWithNextPart(newEdges);         
     396            m_PartsFinished[partIndex] = false; 
     397        } 
     398         
     399        for (int i = 0; i < m_PositionsUsed.length; i++) 
     400        { 
     401            if (!edge.isAt(i)) 
     402            { 
     403                continue; 
     404            } 
     405             
     406            if (!m_PositionsUsed[i]) 
     407            { 
     408                throw new AssertionError 
     409                ( 
     410                    "Positions used by this edge should be marked as used" 
     411                ); 
     412            } 
     413             
     414            m_PositionsUsed[i] = false; 
     415        } 
     416 
     417        for (int i = 0; i < right.length; i++) 
     418        { 
     419            if (i == partIndex) 
     420            { 
     421                if (!m_PartBindingLists[i].contains(edge)) 
     422                { 
     423                    throw new AssertionError 
     424                    ( 
     425                        "The part binding list for this part should " + 
     426                        "contain this edge" 
     427                    ); 
     428                } 
     429            } 
     430            else 
     431            { 
     432                if (m_PartBindingLists[i].contains(edge)) 
     433                { 
     434                    throw new AssertionError 
     435                    ( 
     436                        "No other part binding list should contain this edge" 
     437                    ); 
     438                } 
     439            } 
     440        } 
     441 
     442        m_PartBindingLists[partIndex].remove(edge); 
     443    } 
     444 
     445    private void continueParseWithNextPart(List newEdges) 
     446    { 
     447        boolean foundUnfinishedPart = false; 
     448         
     449        for (int i = right.length - 1; i >= 0; i--) 
     450        { 
     451            if (m_PartsFinished[i]) 
     452            { 
     453                continue; 
     454            } 
     455             
     456            foundUnfinishedPart = true; 
     457             
     458            continueParseWithThisPart(i, false, newEdges); 
     459             
     460            // reordering of elements in permutable rules happens here, 
     461            // by allowing the loop to proceed with the next unfinished part. 
     462            if (!m_isPermutable) 
     463            { 
     464                return; 
     465            } 
     466        } 
     467         
     468        if (foundUnfinishedPart) 
     469        { 
     470            return; 
     471        } 
     472         
     473        // base case: we end up here when all parts have been used, 
     474        // and we should be ready to create a new edge. 
     475         
     476        // don't create new edges which don't contain any other edges: 
     477        // we could keep doing that forever. 
     478         
     479        int numEdges = 0; 
     480         
     481        for (int i = 0; i < right.length; i++) 
     482        { 
     483            numEdges += m_PartBindingLists[i].size(); 
     484        } 
     485         
     486        if (numEdges == 0) 
     487        { 
     488            return; 
     489        } 
     490 
     491        int position = 0; 
     492        Edge[] contained = new Edge[numEdges]; 
     493         
     494        for (int i = 0; i < right.length; i++) 
     495        { 
     496            for (Iterator j = m_PartBindingLists[i].iterator(); j.hasNext(); ) 
     497            { 
     498                Edge edge = (Edge)( j.next() ); 
     499                Edge unbound = edge.getUnboundCopy(); 
     500                try 
     501                { 
     502                    unbound.bindTo(null, right[i]); 
     503                } 
     504                catch (AlreadyBoundException e) 
     505                { 
     506                    throw new AssertionError(e); 
     507                } 
     508                contained[position++] = unbound; 
     509            } 
     510        } 
     511         
     512        if (position != numEdges) 
     513        { 
     514            throw new AssertionError(); 
     515        } 
     516         
     517        Edge newEdge = new RuleEdge(this, contained); 
     518        newEdges.add(newEdge);        
     519    } 
     520 
     521    private void continueParseWithThisPart(int partIndex, boolean hasMatched, 
     522        List newEdges) 
     523    { 
     524        if (m_PartsFinished[partIndex]) 
     525        { 
     526            throw new AssertionError 
     527            ( 
     528                "Not allowed to bind a rule part that is already finished" 
     529            ); 
     530        } 
     531 
     532        // find any other edges that we can use 
     533         
     534        int rightmostEmptyPos = -1; 
     535        for (int i = m_PositionsUsed.length - 1; i >= 0; i--) 
     536        { 
     537            if (!m_PositionsUsed[i]) 
     538            { 
     539                rightmostEmptyPos = i; 
     540                break; 
     541            } 
     542        } 
     543         
     544        List edges = m_CurrentChart.getEdgesAt(rightmostEmptyPos); 
     545        RulePart part = right[partIndex]; 
     546                 
     547        for (Iterator i = edges.iterator(); i.hasNext(); ) 
     548        { 
     549            Edge edge = (Edge)( i.next() ); 
     550            if (!part.matches(edge)) 
     551            { 
     552                continue; 
     553            } 
     554             
     555            // check that the edge doesn't overlap any previously chosen ones 
     556            boolean overlaps = false; 
     557            for (int j = rightmostEmptyPos + 1;  
     558                j < m_CurrentChart.getWidth(); j++) 
     559            { 
     560                if (edge.isAt(j)) 
     561                { 
     562                    overlaps = true; 
     563                    break; 
     564                } 
     565            } 
     566             
     567            if (overlaps == true) 
     568            { 
     569                continue; 
     570            } 
     571             
     572            bindAndContinueParse(partIndex, edge, newEdges); 
     573        } 
     574         
     575        // Optional elements may only be skipped (match 0 times) 
     576        // in permutable rules if no matches have yet been made. 
     577        // This enforces the condition that they may not match  
     578        // nothing at different places in the same input, which  
     579        // would produce duplicate trees in the output. 
     580         
     581        boolean canSkip = part.canSkip(); 
     582         
     583        if (canSkip && m_isPermutable) 
     584        { 
     585            for (int i = 0; i < m_PositionsUsed.length; i++) 
     586            { 
     587                if (m_PositionsUsed[i]) 
     588                { 
     589                    canSkip = false; 
     590                    break; 
     591                } 
     592            } 
     593        } 
     594 
     595        // stop now if this part is not optional and has not matched yet 
     596        if (!canSkip && !hasMatched) 
     597        { 
     598            return; 
     599        } 
     600         
     601        // mark it as finished, so we can move onto the next part 
     602        // (in the case where it is optional and being skipped) 
     603         
     604        m_PartsFinished[partIndex] = true; 
     605         
     606        continueParseWithNextPart(newEdges); 
     607         
     608        if (!m_PartsFinished[partIndex]) 
     609        { 
     610            throw new AssertionError("this part should still be marked" + 
     611                "as fininshed"); 
     612        } 
     613         
     614        m_PartsFinished[partIndex] = false; 
     615    } 
     616 
    245617    private void apply(List stack, Match match, List out) 
    246618    { 
    …… 
    251623            for (int i = 0; i < right.length; i++) 
    252624            { 
    253                 if (m_PartsAlreadyUsed[i]) 
     625                if (m_PartsFinished[i]) 
    254626                { 
    255627                    realNumPartsRemaining--; 
    …… 
    321693            for (int i = right.length - 1; i >= 0; i--) 
    322694            { 
    323                 if (!m_PartsAlreadyUsed[i]) 
     695                if (!m_PartsFinished[i]) 
    324696                { 
    325697                    firstRulePartIndex = i; 
    …… 
    339711        for (int i = firstRulePartIndex; i < right.length; i++) 
    340712        { 
    341             if (m_PartsAlreadyUsed[i]) 
     713            if (m_PartsFinished[i]) 
    342714            { 
    343715                // the caller has processed this part, and asked us to skip it 
    …… 
    528900            for (int i = right.length - 1; i >= 0; i--) 
    529901            { 
    530                 if (!m_PartsAlreadyUsed[i]) 
     902                if (!m_PartsFinished[i]) 
    531903                { 
    532904                    nextPartIndex = i; 
    …… 
    566938        Match match = new Match(right.length); 
    567939        List out = new Vector(); 
    568         m_PartsAlreadyUsed = new boolean [right.length]; 
     940        for (int i = 0; i < right.length; i++) 
     941        { 
     942            m_PartsFinished[i] = false; 
     943        } 
    569944        m_NumPartsRemaining = right.length; 
    570945        apply(stack, match, out); 

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

    r26 r30  
    1616{ 
    1717        private final Edge [] parts; 
    18         private final Rule        rule; 
     18        private final Rule    rule; 
    1919        private Map attribs = new Hashtable(); 
    2020         
    …… 
    5454                super(); 
    5555        this.rule  = rule; 
    56                 this.parts = new Edge [parts.length]; 
     56 
     57        this.parts = new Edge [parts.length]; 
    5758         
    5859        for (int i = 0; i < this.parts.length; i++) 
    …… 
    104105        } 
    105106     
    106         public String toString() { 
     107        public String toString()  
     108    { 
    107109                StringBuffer buf = new StringBuffer(); 
    108110                appendString(buf); 
    109111                return buf.toString(); 
    110112        } 
    111         public void appendString(StringBuffer buf) { 
     113     
     114        public void appendString(StringBuffer buf)  
     115    { 
    112116                buf.append("{"); 
    113117                buf.append(rule().symbol()); 
    …… 
    115119                 
    116120                Map attribs = attributes(); 
    117                 for (Iterator i = attribs.entrySet().iterator(); i.hasNext(); ) { 
     121                for (Iterator i = attribs.entrySet().iterator(); i.hasNext(); )  
     122        { 
    118123                        Entry e = (Entry)( i.next() ); 
    119124                        buf.append(e.getKey()); 
    …… 
    142147                buf.append("}"); 
    143148        } 
    144         public void appendStringPrettyPrint(StringBuffer buf) { 
     149     
     150        public void appendStringPrettyPrint(StringBuffer buf)  
     151    { 
    145152                appendStringPrettyPrint(buf, ""); 
    146153        } 
    147         private void appendStringPrettyPrint(StringBuffer buf, String indent) { 
     154     
     155        private void appendStringPrettyPrint(StringBuffer buf, String indent)  
     156    { 
    148157                buf.append(indent); 
    149158                buf.append("{"); 
    …… 
    152161                 
    153162                Map attribs = attributes(); 
    154                 for (Iterator i = attribs.entrySet().iterator(); i.hasNext(); ) { 
     163                for (Iterator i = attribs.entrySet().iterator(); i.hasNext(); )  
     164        { 
    155165                        Entry e = (Entry)( i.next() ); 
    156166                        buf.append(e.getKey()); 
    …… 
    190200                buf.append("}"); 
    191201        } 
    192         public String[] words() { 
     202     
     203        public String[] words()  
     204    { 
    193205                Vector v = new Vector(); 
    194206                appendWords(v); 
    195207                return (String[])( v.toArray(new String[v.size()]) ); 
    196208        } 
    197         public void appendWords(Vector words) { 
    198                 for (int i = 0; i < parts.length; i++) { 
     209     
     210        public void appendWords(Vector words)  
     211    { 
     212                for (int i = 0; i < parts.length; i++)  
     213        { 
    199214                        parts[i].appendWords(words); 
    200215                } 
    201216        } 
    202         public Edge[] parts() { 
     217     
     218        public Edge[] parts()  
     219    { 
    203220                Edge [] result = new Edge[parts.length]; 
    204221                System.arraycopy(parts, 0, result, 0, parts.length); 
    …… 
    219236         
    220237    public Map attributes() { return attribs; } 
    221         private void findAttributes() { 
     238        private void findAttributes()  
     239    { 
    222240                attribs = new Hashtable(); 
    223241                 
    …… 
    240258                                 
    241259                                Edge partInstance = parts[p]; 
     260                 
    242261                                Object value = partInstance.attributes().get(name); 
    243                                 if (value == null) { 
     262                 
     263                                if (value == null)  
     264                { 
    244265                                        throw new IllegalStateException( 
    245266                                                        partInstance.toString()+ 
    …… 
    247268                                                        name+" to copy into "+this); 
    248269                                } 
     270                 
    249271                                Object oldValue = attribs.get(name); 
    250                                 if (oldValue != null && ! oldValue.equals(value)) { 
     272                 
     273                                if (oldValue != null && ! oldValue.equals(value))  
     274                { 
    251275                                        throw new IllegalStateException( 
    252276                                                        "Unable to unify "+oldValue+" and "+value+ 
    253277                                                        " for attribute "+name+" of "+this); 
    254278                                } 
    255                                 if (oldValue == null) { 
     279                 
     280                                if (oldValue == null)  
     281                { 
    256282                                        attribs.put(name, value); 
    257283                                } 
    …… 
    281307                } 
    282308        } 
    283         public int getDepthScore() { 
     309     
     310        public int getDepthScore()  
     311    { 
    284312                return getDepthScore(1); 
    285313        } 
    286         private int getDepthScore(int initialDepth) { 
     314     
     315        private int getDepthScore(int initialDepth)  
     316    { 
    287317                int d = initialDepth; 
    288                 for (int i = 0; i < parts.length; i++) { 
    289                         if (parts[i] instanceof RuleEdge) { 
     318                for (int i = 0; i < parts.length; i++)  
     319        { 
     320                        if (parts[i] instanceof RuleEdge)  
     321            { 
    290322                                d += ((RuleEdge)(parts[i])).getDepthScore(initialDepth+1); 
    291323                        } 
    …… 
    293325                return d; 
    294326        } 
     327     
    295328    public Edge getUnboundCopy() 
    296329    { 
    297330        return new RuleEdge(rule, parts); 
    298331    } 
     332     
     333    public boolean isAt(int position) 
     334    { 
     335        for (int i = 0; i < parts.length; i++) 
     336        { 
     337            if (parts[i].isAt(position)) 
     338            { 
     339                return true; 
     340            } 
     341        } 
     342         
     343        return false; 
     344    } 
    299345} 

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

    r26 r30  
    1919    private static final Edge[]   parts   = new Edge[0]; 
    2020    private static final ImmutableMap attribs = new ImmutableMap(new HashMap()); 
     21    private int m_Position; 
    2122     
    2223    /** 
    …… 
    2526     * @param surface The text of the word 
    2627     */ 
    27     public WordEdge(String surface)  
     28    public WordEdge(String surface, int position)  
    2829    { 
    2930                super(); 
    3031                this.surface = surface; 
     32        this.m_Position = position; 
    3133        } 
    3234     
    …… 
    5961     * @param boundLocation 
    6062     */ 
    61     public WordEdge(String surface, RulePart boundLocation) 
     63    public WordEdge(String surface, int position, RulePart boundLocation) 
    6264    { 
    63         this(surface); 
     65        this(surface, position); 
    6466         
    6567        try 
    …… 
    9799    public Edge getUnboundCopy() 
    98100    { 
    99         return new WordEdge(surface); 
     101        return new WordEdge(surface, m_Position); 
     102    } 
     103    public boolean isAt(int position) 
     104    { 
     105        return m_Position == position; 
    100106    } 
    101107} 

  • lex/trunk/test/com/qwirx/lex/ParserTest.java

    r26 r30  
    1010import java.util.List; 
    1111import java.util.Map; 
    12 import java.util.Stack; 
    1312 
    1413import junit.framework.TestCase; 
    1514 
     15import com.qwirx.lex.parser.Chart; 
    1616import com.qwirx.lex.parser.Edge; 
    1717import com.qwirx.lex.parser.Parser; 
    …… 
    2222import com.qwirx.lex.parser.EdgeBase.AlreadyBoundException; 
    2323import com.qwirx.lex.parser.Rule.DuplicateNameException; 
    24 import com.qwirx.lex.parser.Rule.Match; 
    2524 
    2625/** 
    …… 
    3130public class ParserTest extends TestCase  
    3231{ 
     32    public void testEdgePositioning() 
     33    { 
     34        Edge e = new WordEdge("foo", 0); 
     35        assertTrue (e.isAt(0)); 
     36        assertFalse(e.isAt(-1)); 
     37        assertFalse(e.isAt(1)); 
     38 
     39        e = new WordEdge("bar", 1); 
     40        assertFalse(e.isAt(0)); 
     41        assertTrue (e.isAt(1)); 
     42        assertFalse(e.isAt(2)); 
     43    } 
     44     
     45    public void testAddToChart() 
     46    { 
     47        Chart chart = new Chart(2); 
     48        List edges = chart.getEdges(); 
     49        assertEquals(0, edges.size()); 
     50         
     51        Edge e1 = new WordEdge("foo", 0); 
     52        chart.add(e1); 
     53        assertEquals(0, edges.size()); 
     54        edges = chart.getEdges(); 
     55        assertEquals(1, edges.size()); 
     56        assertEquals(e1, edges.get(0)); 
     57 
     58        Edge e2 = new WordEdge("bar", 1); 
     59        chart.add(e2); 
     60        assertEquals(1, edges.size()); 
     61        edges = chart.getEdges(); 
     62        assertEquals(2, edges.size()); 
     63        assertEquals(e1, edges.get(0)); 
     64        assertEquals(e2, edges.get(1)); 
     65         
     66        edges = chart.getEdgesAt(1); 
     67        assertEquals(1,  edges.size()); 
     68        assertEquals(e2, edges.get(0)); 
     69 
     70        edges = chart.getEdgesAt(0); 
     71        assertEquals(1,  edges.size()); 
     72        assertEquals(e1, edges.get(0)); 
     73    } 
     74     
     75    public void testApplyRuleToChartReturnsEdge() 
     76    { 
     77        Chart chart = new Chart(2); 
     78        chart.add(new WordEdge("the", 0)); 
     79        chart.add(new WordEdge("cat", 1)); 
     80        Rule r1 = Rule.makeFromString(1, "DET", "the"); 
     81         
     82        List newEdges = r1.applyTo(chart, 0); 
     83        assertEquals(1, newEdges.size()); 
     84         
     85        newEdges = r1.applyTo(chart, 1); 
     86        assertEquals(0, newEdges.size()); 
     87    } 
     88     
    3389    public void testRulePartRepeat() 
    3490    { 
    …… 
    71127 
    72128            RulePart p = RulePart.fromString("the"+repString); 
    73             assertFalse(p.matches(new WordEdge(""))); 
    74             assertFalse(p.matches(new WordEdge("th"))); 
    75             assertTrue (p.matches(new WordEdge("the"))); 
    76             assertFalse(p.matches(new WordEdge("thet"))); 
    77             assertFalse(p.matches(new WordEdge("thethe"))); 
     129            assertFalse(p.matches(new WordEdge("", 0))); 
     130            assertFalse(p.matches(new WordEdge("th", 0))); 
     131            assertTrue (p.matches(new WordEdge("the", 0))); 
     132            assertFalse(p.matches(new WordEdge("thet", 0))); 
     133            assertFalse(p.matches(new WordEdge("thethe", 0))); 
    78134        } 
    79135         
    80136        WordEdge[] none = new WordEdge[]{}; 
    81         WordEdge[] one  = new WordEdge[]{new WordEdge("the")}; 
     137        WordEdge[] one  = new WordEdge[]{new WordEdge("the", 0)}; 
    82138        WordEdge[] two  = new WordEdge[]{one[0], one[0]}; 
    83         WordEdge[] odd  = new WordEdge[]{one[0], new WordEdge("tea")}; 
     139        WordEdge[] odd  = new WordEdge[]{one[0], new WordEdge("tea", 0)}; 
    84140         
    85141        RulePart p = RulePart.fromString("the"); 
    …… 
    241297    { 
    242298                Rule[] rules = new Rule[]{ 
    243                                 Rule.makeFromString(1, "DET",  "the"), 
    244                                 Rule.makeFromString(2, "NOUN", "cat"), 
    245                                 Rule.makeFromString(3, "VERB", "sat"), 
    246                                 Rule.makeFromString(4, "PREP", "on"), 
    247                                 Rule.makeFromString(5, "NOUN", "mat"), 
    248                                 Rule.makeFromString(6, "NP",   "{DET} {NOUN}"), 
    249                                 Rule.makeFromString(7, "PP",   "{PREP} {NP}"), 
    250                                 Rule.makeFromString(8, "VP",   "{VERB} {PP}"), 
    251                                 Rule.makeFromString(9, "SENTENCE", "{NP} {VP}") 
     299                                Rule.makeFromString(1,  "DET",      "the"), 
     300                                Rule.makeFromString(2,  "NOUN",     "cat"), 
     301                                Rule.makeFromString(3,  "VERB",     "sat"), 
     302                                Rule.makeFromString(4,  "P",        "on"), 
     303                                Rule.makeFromString(5,  "NOUN",     "mat"), 
     304                Rule.makeFromString(6,  "P",        "by"), 
     305                Rule.makeFromString(7,  "NOUN",     "door"), 
     306                                Rule.makeFromString(8,  "NP",       "{DET} {NOUN}"), 
     307                                Rule.makeFromString(9,  "PP",       "{P} {NP}"), 
     308                                Rule.makeFromString(10, "VP",       "{VERB}"), 
     309                                Rule.makeFromString(11, "SENTENCE", "{NP} {VP} {PP}"), 
     310                Rule.makeFromString(12, "SENTENCE", "{NP} {VP} {PP} {PP}") 
    252311                }; 
    253312                 
    254313                Parser p = new Parser(rules); 
    255                 Edge[][] results = p.parseFor("the cat sat on the mat", "SENTENCE"); 
    256                  
    257                 assertEquals(1, results.length); 
    258                 Edge[] result = results[0]; 
    259                  
    260                 Edge SENTENCE = result[0]; 
     314                List results = p.parseFor("the cat sat on the mat by the door", "SENTENCE"); 
     315                 
     316                assertEquals(1, results.size()); 
     317                 
     318                Edge SENTENCE = (Edge)( results.get(0) ); 
    261319                assertEquals("SENTENCE", SENTENCE.symbol()); 
    262320                 
    263                 Edge NP = SENTENCE.part(0); 
    264                 assertEquals("NP", NP.symbol()); 
    265  
    266                 Edge DET = NP.part(0); 
     321                Edge NP1 = SENTENCE.part(0); 
     322                assertEquals("NP", NP1.symbol()); 
     323 
     324                Edge DET = NP1.part(0); 
    267325                assertEquals("DET", DET.symbol()); 
    268326                assertEquals("the", DET.part(0).toString()); 
    269327                 
    270                 Edge NOUN = NP.part(1); 
     328                Edge NOUN = NP1.part(1); 
    271329                assertEquals("NOUN", NOUN.symbol()); 
    272330                assertEquals("cat",  NOUN.part(0).toString()); 
    …… 
    279337                assertEquals("sat", VERB.part(0).toString()); 
    280338                 
    281                 Edge PP = VP.part(1); 
    282                 assertEquals("PP", PP.symbol()); 
    283                  
    284                 Edge PREP = PP.part(0); 
    285                 assertEquals("PREP", PREP.symbol()); 
    286                 assertEquals("on",   PREP.part(0).symbol()); 
    287                  
    288                 NP = PP.part(1); 
    289                 assertEquals("NP", NP.symbol()); 
    290                  
    291                 DET = NP.part(0); 
     339                Edge PP1 = SENTENCE.part(2); 
     340                assertEquals("PP", PP1.symbol()); 
     341                 
     342                Edge P1 = PP1.part(0); 
     343                assertEquals("P",  P1.symbol()); 
     344                assertEquals("on", P1.part(0).symbol()); 
     345                 
     346                Edge NP2 = PP1.part(1); 
     347                assertEquals("NP", NP2.symbol()); 
     348                 
     349                DET = NP2.part(0); 
    292350                assertEquals("DET", DET.symbol()); 
    293351                assertEquals("the", DET.part(0).symbol()); 
    294352                 
    295                 NOUN = NP.part(1); 
     353                NOUN = NP2.part(1); 
    296354                assertEquals("NOUN", NOUN.symbol()); 
    297355                assertEquals("mat",  NOUN.part(0).symbol()); 
     356         
     357        Edge PP2 = SENTENCE.part(3); 
     358        assertEquals("PP", PP2.symbol()); 
     359         
     360        Edge P2 = PP2.part(0); 
     361        assertEquals("P",  P2.symbol()); 
     362        assertEquals("by", P2.part(0).symbol()); 
     363         
     364        Edge NP3 = PP2.part(1); 
     365        assertEquals("NP", NP3.symbol()); 
     366         
     367        DET = NP3.part(0); 
     368        assertEquals("DET", DET.symbol()); 
     369        assertEquals("the", DET.part(0).symbol()); 
     370         
     371        NOUN = NP3.part(1); 
     372        assertEquals("NOUN", NOUN.symbol()); 
     373        assertEquals("door",  NOUN.part(0).symbol()); 
    298374        } 
    299375 
    …… 
    337413                Parser p = new Parser(rules); 
    338414                 
    339                 Edge[][] results = p.parseFor("TWLDWT/ H CMJM/ W H >RY/", "NP"); 
    340                 assertEquals(2, results.length); 
    341                  
    342                 for (int i = 0; i < results.length; i++) { 
    343                         RuleEdge r = (RuleEdge)(results[i][0]); 
     415                List results = p.parseFor("TWLDWT/ H CMJM/ W H >RY/", "NP"); 
     416                assertEquals(2, results.size()); 
     417                 
     418                for (int i = 0; i < results.size(); i++) { 
     419                        RuleEdge r = (RuleEdge)(results.get(i)); 
    344420                        System.out.println("Depth score of result "+i+": "+ 
    345421                                        r.getDepthScore());      
    346422                } 
    347423                 
    348                 Edge[] result = results[1]; 
    349                 assertEquals(1, result.length); 
    350                  
    351                 Edge NP_all = result[0]; 
     424                Edge NP_all = (Edge)(results.get(1)); 
    352425                assertEquals("NP",       NP_all.symbol()); 
    353426                assertEquals("absolute", NP_all.attribute("state")); 
    …… 
    399472        Parser p = new Parser(rules); 
    400473         
    401         Edge[][] results = p.parseFor("cat dog", "must_CAT_must_DOG"); 
    402         assertEquals(1, results.length); 
    403          
    404         Edge[] result = results[0]; 
    405         assertEquals(1, result.length); 
    406          
    407         Edge instance = result[0]; 
     474        List results = p.parseFor("cat dog", "must_CAT_must_DOG"); 
     475        assertEquals(1, results.size()); 
     476         
     477        Edge instance = (Edge)( results.get(0) ); 
    408478        assertEquals("must_CAT_must_DOG", instance.symbol()); 
    409479         
    …… 
    415485         
    416486        String target = "must_CAT_must_DOG"; 
    417         assertEquals(0, p.parseFor("",                target).length); 
    418         assertEquals(0, p.parseFor("dog",             target).length); 
    419         assertEquals(0, p.parseFor("cat",             target).length); 
    420         assertEquals(0, p.parseFor("cat cat",         target).length); 
    421         assertEquals(1, p.parseFor("cat dog",         target).length); 
    422         assertEquals(0, p.parseFor("dog cat",         target).length); 
    423         assertEquals(0, p.parseFor("dog dog",         target).length); 
    424         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    425         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    426         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    427         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    428         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    429         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    430         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    431         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    432         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     487        assertEquals(0, p.parseFor("",                target).size()); 
     488        assertEquals(0, p.parseFor("dog",             target).size()); 
     489        assertEquals(0, p.parseFor("cat",             target).size()); 
     490        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     491        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     492        assertEquals(0, p.parseFor("dog cat",         target).size()); 
     493        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     494        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     495        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     496        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     497        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     498        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     499        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     500        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     501        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     502        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    433503 
    434504        target = "maybe_CAT_must_DOG"; 
    435         assertEquals(0, p.parseFor("",                target).length); 
    436         assertEquals(1, p.parseFor("dog",             target).length); 
    437         assertEquals(0, p.parseFor("cat",             target).length); 
    438         assertEquals(1, p.parseFor("cat dog",         target).length); 
    439         assertEquals(0, p.parseFor("dog cat",         target).length); 
    440         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    441         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
     505        assertEquals(0, p.parseFor("",                target).size()); 
     506        assertEquals(1, p.parseFor("dog",             target).size()); 
     507        assertEquals(0, p.parseFor("cat",             target).size()); 
     508        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     509        assertEquals(0, p.parseFor("dog cat",         target).size()); 
     510        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     511        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
    442512 
    443513        target = "maybe_CAT_maybe_DOG"; 
    444         assertEquals(0, p.parseFor("",                target).length); 
    445         assertEquals(1, p.parseFor("dog",             target).length); 
    446         assertEquals(1, p.parseFor("cat",             target).length); 
    447         assertEquals(1, p.parseFor("cat dog",         target).length); 
    448         assertEquals(0, p.parseFor("dog cat",         target).length); 
    449         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    450         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
     514        assertEquals(0, p.parseFor("",                target).size()); 
     515        assertEquals(1, p.parseFor("dog",             target).size()); 
     516        assertEquals(1, p.parseFor("cat",             target).size()); 
     517        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     518        assertEquals(0, p.parseFor("dog cat",         target).size()); 
     519        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     520        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
    451521 
    452522        target = "maybe_CATs_maybe_DOGs"; 
    453         assertEquals(0, p.parseFor("",                target).length); 
    454         assertEquals(1, p.parseFor("dog",             target).length); 
    455         assertEquals(1, p.parseFor("cat",             target).length); 
    456         assertEquals(1, p.parseFor("cat dog",         target).length); 
    457         assertEquals(0, p.parseFor("dog cat",         target).length); 
    458         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    459         assertEquals(1, p.parseFor("cat dog dog",     target).length); 
    460         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
     523        assertEquals(0, p.parseFor("",                target).size()); 
     524        assertEquals(1, p.parseFor("dog",             target).size()); 
     525        assertEquals(1, p.parseFor("cat",             target).size()); 
     526        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     527        assertEquals(0, p.parseFor("dog cat",         target).size()); 
     528        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     529        assertEquals(1, p.parseFor("cat dog dog",     target).size()); 
     530        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
    461531 
    462532        target = "must_CATs_must_DOGs"; 
    463         assertEquals(0, p.parseFor("",                target).length); 
    464         assertEquals(0, p.parseFor("dog",             target).length); 
    465         assertEquals(0, p.parseFor("cat",             target).length); 
    466         assertEquals(1, p.parseFor("cat dog",         target).length); 
    467         assertEquals(0, p.parseFor("dog cat",         target).length); 
    468         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    469         assertEquals(1, p.parseFor("cat dog dog",     target).length); 
    470         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
     533        assertEquals(0, p.parseFor("",                target).size()); 
     534        assertEquals(0, p.parseFor("dog",             target).size()); 
     535        assertEquals(0, p.parseFor("cat",             target).size()); 
     536        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     537        assertEquals(0, p.parseFor("dog cat",         target).size()); 
     538        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     539        assertEquals(1, p.parseFor("cat dog dog",     target).size()); 
     540        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
     541    } 
     542     
     543    public void testRepetitionOrder() throws Exception  
     544    { 
     545        Rule[] rules = new Rule[]{ 
     546                Rule.makeFromString(1, "N",  "door"), 
     547                Rule.makeFromString(2, "N",  "mat"), 
     548                Rule.makeFromString(3, "NP", "{N}+") 
     549        }; 
     550         
     551        Parser p = new Parser(rules); 
     552        List results = p.parseFor("door mat", "NP"); 
     553         
     554        assertEquals(1, results.size()); 
     555         
     556        Edge NP = (Edge)( results.get(0) ); 
     557        assertEquals("NP", NP.symbol()); 
     558         
     559        Edge N1 = NP.part(0); 
     560        assertEquals("N", N1.symbol()); 
     561 
     562        Edge DOOR = N1.part(0); 
     563        assertEquals("door", DOOR.symbol()); 
     564 
     565        Edge N2 = NP.part(1); 
     566        assertEquals("N", N2.symbol()); 
     567 
     568        Edge MAT = N2.part(0); 
     569        assertEquals("mat", MAT.symbol()); 
    471570    } 
    472571 
    …… 
    477576        Rule test = Rule.makeFromString(3, "maybe_CATs_maybe_DOGs", "# {CAT}* {DOG}*"); 
    478577         
    479         Stack stackIn = new Stack(); 
    480         stackIn.add(new RuleEdge(cat, new Edge[]{ 
    481             new WordEdge("cat", cat.part(0)) 
     578        Chart chart = new Chart(2); 
     579        chart.add(new RuleEdge(cat, new Edge[]{ 
     580            new WordEdge("cat", 0, cat.part(0)) 
    482581        })); 
    483         stackIn.add(new RuleEdge(dog, new Edge[]{ 
    484             new WordEdge("dog", dog.part(0)) 
     582        chart.add(new RuleEdge(dog, new Edge[]{ 
     583            new WordEdge("dog", 1, dog.part(0)) 
    485584        })); 
    486585         
    487         List matches = test.applyTo(stackIn); 
    488         assertEquals(2, matches.size()); 
    489          
    490         Match match = (Match)( matches.get(0) ); 
    491         Stack stackOut = match.getStack(); 
    492         assertEquals(2, stackOut.size()); 
    493          
    494         { 
    495             RuleEdge CAT = (RuleEdge)( stackOut.get(0) ); 
    496             assertEquals("CAT", CAT.symbol()); 
    497             assertEquals(1,     CAT.parts().length); 
    498             assertEquals("cat", CAT.parts()[0].symbol()); 
    499  
    500             RuleEdge MCMD = (RuleEdge)( stackOut.get(1) ); 
    501             assertEquals("maybe_CATs_maybe_DOGs", MCMD.symbol()); 
    502             assertEquals(1,     MCMD.parts().length); 
    503              
    504             RuleEdge DOG = (RuleEdge)( MCMD.parts()[0] ); 
    505             assertEquals("DOG", DOG.symbol()); 
    506             assertEquals(1,     DOG.parts().length); 
    507             assertEquals("dog", DOG.parts()[0].symbol()); 
    508         } 
    509          
    510         match = (Match)( matches.get(1) ); 
    511         stackOut = match.getStack(); 
    512         assertEquals(1, stackOut.size()); 
    513          
    514         { 
    515             RuleEdge MCMD = (RuleEdge)( stackOut.get(0) ); 
    516             assertEquals("maybe_CATs_maybe_DOGs", MCMD.symbol()); 
    517             assertEquals(2,     MCMD.parts().length); 
    518  
    519             RuleEdge CAT = (RuleEdge)( MCMD.parts()[0] ); 
    520             assertEquals("CAT", CAT.symbol()); 
    521             assertEquals(1,     CAT.parts().length); 
    522             assertEquals("cat", CAT.parts()[0].symbol()); 
    523  
    524             RuleEdge DOG = (RuleEdge)( MCMD.parts()[1] ); 
    525             assertEquals("DOG", DOG.symbol()); 
    526             assertEquals(1,     DOG.parts().length); 
    527             assertEquals("dog", DOG.parts()[0].symbol()); 
    528         } 
     586        List edges = cat.applyTo(chart, 0); 
     587        assertEquals(1, edges.size()); 
     588        chart.add(edges); 
     589 
     590        edges = dog.applyTo(chart, 1); 
     591        assertEquals(1, edges.size()); 
     592        chart.add(edges); 
     593 
     594        edges = test.applyTo(chart, 1); 
     595        assertEquals(1, edges.size()); 
     596         
     597        RuleEdge MCMD = (RuleEdge)( edges.get(0) ); 
     598        assertEquals("maybe_CATs_maybe_DOGs", MCMD.symbol()); 
     599        assertEquals(2,     MCMD.parts().length); 
     600 
     601        RuleEdge CAT = (RuleEdge)( MCMD.parts()[0] ); 
     602        assertEquals("CAT", CAT.symbol()); 
     603        assertEquals(1,     CAT.parts().length); 
     604        assertEquals("cat", CAT.parts()[0].symbol()); 
     605 
     606        RuleEdge DOG = (RuleEdge)( MCMD.parts()[1] ); 
     607        assertEquals("DOG", DOG.symbol()); 
     608        assertEquals(1,     DOG.parts().length); 
     609        assertEquals("dog", DOG.parts()[0].symbol()); 
    529610    } 
    530611     
    …… 
    543624        Parser p = new Parser(rules); 
    544625         
    545         Edge[][] results = p.parseFor("cat dog", "must_CAT_must_DOG"); 
    546         assertEquals(1, results.length); 
    547          
    548         Edge[] result = results[0]; 
    549         assertEquals(1, result.length); 
    550          
    551         Edge instance = result[0]; 
     626        List edges = p.parseFor("cat dog", "must_CAT_must_DOG"); 
     627        assertEquals(1, edges.size()); 
     628         
     629        Edge instance = (Edge)( edges.get(0) ); 
    552630        assertEquals("must_CAT_must_DOG", instance.symbol()); 
    553631         
    …… 
    559637         
    560638        String target = "must_CAT_must_DOG"; 
    561         assertEquals(0, p.parseFor("",                target).length); 
    562         assertEquals(0, p.parseFor("dog",             target).length); 
    563         assertEquals(0, p.parseFor("cat",             target).length); 
    564         assertEquals(0, p.parseFor("cat cat",         target).length); 
    565         assertEquals(1, p.parseFor("cat dog",         target).length); 
    566         assertEquals(1, p.parseFor("dog cat",         target).length); 
    567         assertEquals(0, p.parseFor("dog dog",         target).length); 
    568         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    569         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    570         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    571         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    572         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    573         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    574         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    575         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    576         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     639        assertEquals(0, p.parseFor("",                target).size()); 
     640        assertEquals(0, p.parseFor("dog",             target).size()); 
     641        assertEquals(0, p.parseFor("cat",             target).size()); 
     642        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     643        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     644        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     645        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     646        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     647        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     648        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     649        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     650        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     651        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     652        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     653        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     654        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    577655 
    578656        target = "maybe_CAT_must_DOG"; 
    579         assertEquals(0, p.parseFor("",                target).length); 
    580         assertEquals(1, p.parseFor("dog",             target).length); 
    581         assertEquals(0, p.parseFor("cat",             target).length); 
    582         assertEquals(0, p.parseFor("cat cat",         target).length); 
    583         assertEquals(1, p.parseFor("cat dog",         target).length); 
    584         assertEquals(1, p.parseFor("dog cat",         target).length); 
    585         assertEquals(0, p.parseFor("dog dog",         target).length); 
    586         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    587         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    588         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    589         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    590         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    591         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    592         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    593         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    594         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     657        assertEquals(0, p.parseFor("",                target).size()); 
     658        assertEquals(1, p.parseFor("dog",             target).size()); 
     659        assertEquals(0, p.parseFor("cat",             target).size()); 
     660        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     661        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     662        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     663        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     664        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     665        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     666        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     667        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     668        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     669        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     670        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     671        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     672        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    595673 
    596674        target = "maybe_CAT_maybe_DOG"; 
    597         assertEquals(0, p.parseFor("",                target).length); 
    598         assertEquals(1, p.parseFor("dog",             target).length); 
    599         assertEquals(1, p.parseFor("cat",             target).length); 
    600         assertEquals(0, p.parseFor("cat cat",         target).length); 
    601         assertEquals(1, p.parseFor("cat dog",         target).length); 
    602         assertEquals(1, p.parseFor("dog cat",         target).length); 
    603         assertEquals(0, p.parseFor("dog dog",         target).length); 
    604         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    605         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    606         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    607         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    608         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    609         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    610         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    611         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    612         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     675        assertEquals(0, p.parseFor("",                target).size()); 
     676        assertEquals(1, p.parseFor("dog",             target).size()); 
     677        assertEquals(1, p.parseFor("cat",             target).size()); 
     678        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     679        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     680        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     681        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     682        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     683        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     684        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     685        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     686        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     687        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     688        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     689        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     690        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    613691 
    614692        target = "maybe_CATs_maybe_DOGs"; 
    615         assertEquals(0, p.parseFor("",                target).length); 
    616         assertEquals(1, p.parseFor("dog",             target).length); 
    617         assertEquals(1, p.parseFor("cat",             target).length); 
    618         assertEquals(1, p.parseFor("cat cat",         target).length); 
    619         assertEquals(1, p.parseFor("cat dog",         target).length); 
    620         assertEquals(1, p.parseFor("dog cat",         target).length); 
    621         assertEquals(1, p.parseFor("dog dog",         target).length); 
    622         assertEquals(1, p.parseFor("cat cat cat",     target).length); 
    623         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    624         // assertEquals(1, p.parseFor("cat dog cat",     target).length); 
    625         // assertEquals(1, p.parseFor("dog cat dog",     target).length); 
    626         assertEquals(1, p.parseFor("dog dog cat",     target).length); 
    627         assertEquals(1, p.parseFor("dog dog dog",     target).length); 
    628         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
    629         //assertEquals(1, p.parseFor("cat dog cat dog", target).length); 
    630         //assertEquals(1, p.parseFor("cat dog dog cat", target).length); 
    631         //assertEquals(1, p.parseFor("dog cat dog cat", target).length); 
     693        assertEquals(0, p.parseFor("",                target).size()); 
     694        assertEquals(1, p.parseFor("dog",             target).size()); 
     695        assertEquals(1, p.parseFor("cat",             target).size()); 
     696        assertEquals(1, p.parseFor("cat cat",         target).size()); 
     697        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     698        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     699        assertEquals(1, p.parseFor("dog dog",         target).size()); 
     700        assertEquals(1, p.parseFor("cat cat cat",     target).size()); 
     701        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     702        // assertEquals(1, p.parseFor("cat dog cat",     target).size()); 
     703        // assertEquals(1, p.parseFor("dog cat dog",     target).size()); 
     704        assertEquals(1, p.parseFor("dog dog cat",     target).size()); 
     705        assertEquals(1, p.parseFor("dog dog dog",     target).size()); 
     706        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
     707        //assertEquals(1, p.parseFor("cat dog cat dog", target).size()); 
     708        //assertEquals(1, p.parseFor("cat dog dog cat", target).size()); 
     709        //assertEquals(1, p.parseFor("dog cat dog cat", target).size()); 
    632710 
    633711        target = "must_CATs_must_DOGs"; 
    634         assertEquals(0, p.parseFor("",                target).length); 
    635         assertEquals(0, p.parseFor("dog",             target).length); 
    636         assertEquals(0, p.parseFor("cat",             target).length); 
    637         assertEquals(0, p.parseFor("cat cat",         target).length); 
    638         assertEquals(1, p.parseFor("cat dog",         target).length); 
    639         assertEquals(1, p.parseFor("dog cat",         target).length); 
    640         assertEquals(0, p.parseFor("dog dog",         target).length); 
    641         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    642         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    643         //assertEquals(1, p.parseFor("cat dog cat",     target).length); 
    644         //assertEquals(1, p.parseFor("dog cat dog",     target).length); 
    645         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    646         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
    647         //assertEquals(1, p.parseFor("cat dog cat dog", target).length); 
    648         //assertEquals(1, p.parseFor("cat dog dog cat", target).length); 
    649         //assertEquals(1, p.parseFor("dog cat dog cat", target).length); 
     712        assertEquals(0, p.parseFor("",                target).size()); 
     713        assertEquals(0, p.parseFor("dog",             target).size()); 
     714        assertEquals(0, p.parseFor("cat",             target).size()); 
     715        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     716        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     717        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     718        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     719        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     720        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     721        //assertEquals(1, p.parseFor("cat dog cat",     target).size()); 
     722        //assertEquals(1, p.parseFor("dog cat dog",     target).size()); 
     723        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     724        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
     725        //assertEquals(1, p.parseFor("cat dog cat dog", target).size()); 
     726        //assertEquals(1, p.parseFor("cat dog dog cat", target).size()); 
     727        //assertEquals(1, p.parseFor("dog cat dog cat", target).size()); 
    650728    } 
    651729 
    …… 
    664742        Parser p = new Parser(rules); 
    665743         
    666         Edge[][] results = p.parseFor("cat dog", "must_CAT_must_DOG"); 
    667         assertEquals(1, results.length); 
    668          
    669         Edge[] result = results[0]; 
    670         assertEquals(1, result.length); 
    671          
    672         Edge instance = result[0]; 
     744        List edges = p.parseFor("cat dog", "must_CAT_must_DOG"); 
     745        assertEquals(1, edges.size()); 
     746         
     747        Edge instance = (Edge)( edges.get(0) ); 
    673748        assertEquals("must_CAT_must_DOG", instance.symbol()); 
    674749         
    …… 
    680755 
    681756        String target = "must_CAT_must_DOG"; 
    682         assertEquals(0, p.parseFor("",                target).length); 
    683         assertEquals(0, p.parseFor("dog",             target).length); 
    684         assertEquals(0, p.parseFor("cat",             target).length); 
    685         assertEquals(0, p.parseFor("cat cat",         target).length); 
    686         assertEquals(1, p.parseFor("cat dog",         target).length); 
    687         assertEquals(1, p.parseFor("dog cat",         target).length); 
    688         assertEquals(0, p.parseFor("dog dog",         target).length); 
    689         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    690         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    691         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    692         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    693         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    694         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    695         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    696         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    697         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     757        assertEquals(0, p.parseFor("",                target).size()); 
     758        assertEquals(0, p.parseFor("dog",             target).size()); 
     759        assertEquals(0, p.parseFor("cat",             target).size()); 
     760        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     761        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     762        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     763        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     764        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     765        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     766        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     767        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     768        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     769        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     770        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     771        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     772        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    698773 
    699774        target = "maybe_CAT_must_DOG"; 
    700         assertEquals(0, p.parseFor("",                target).length); 
    701         assertEquals(1, p.parseFor("dog",             target).length); 
    702         assertEquals(0, p.parseFor("cat",             target).length); 
    703         assertEquals(0, p.parseFor("cat cat",         target).length); 
    704         assertEquals(1, p.parseFor("cat dog",         target).length); 
    705         assertEquals(1, p.parseFor("dog cat",         target).length); 
    706         assertEquals(0, p.parseFor("dog dog",         target).length); 
    707         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    708         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    709         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    710         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    711         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    712         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    713         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    714         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    715         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     775        assertEquals(0, p.parseFor("",                target).size()); 
     776        assertEquals(1, p.parseFor("dog",             target).size()); 
     777        assertEquals(0, p.parseFor("cat",             target).size()); 
     778        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     779        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     780        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     781        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     782        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     783        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     784        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     785        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     786        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     787        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     788        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     789        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     790        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    716791 
    717792        target = "maybe_CAT_maybe_DOG"; 
    718         assertEquals(0, p.parseFor("",                target).length); 
    719         assertEquals(1, p.parseFor("dog",             target).length); 
    720         assertEquals(1, p.parseFor("cat",             target).length); 
    721         assertEquals(0, p.parseFor("cat cat",         target).length); 
    722         assertEquals(1, p.parseFor("cat dog",         target).length); 
    723         assertEquals(1, p.parseFor("dog cat",         target).length); 
    724         assertEquals(0, p.parseFor("dog dog",         target).length); 
    725         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    726         assertEquals(0, p.parseFor("cat cat dog",     target).length); 
    727         assertEquals(0, p.parseFor("cat dog cat",     target).length); 
    728         assertEquals(0, p.parseFor("dog cat dog",     target).length); 
    729         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    730         assertEquals(0, p.parseFor("cat cat dog dog", target).length); 
    731         assertEquals(0, p.parseFor("cat dog cat dog", target).length); 
    732         assertEquals(0, p.parseFor("cat dog dog cat", target).length); 
    733         assertEquals(0, p.parseFor("dog cat dog cat", target).length); 
     793        assertEquals(0, p.parseFor("",                target).size()); 
     794        assertEquals(1, p.parseFor("dog",             target).size()); 
     795        assertEquals(1, p.parseFor("cat",             target).size()); 
     796        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     797        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     798        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     799        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     800        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     801        assertEquals(0, p.parseFor("cat cat dog",     target).size()); 
     802        assertEquals(0, p.parseFor("cat dog cat",     target).size()); 
     803        assertEquals(0, p.parseFor("dog cat dog",     target).size()); 
     804        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     805        assertEquals(0, p.parseFor("cat cat dog dog", target).size()); 
     806        assertEquals(0, p.parseFor("cat dog cat dog", target).size()); 
     807        assertEquals(0, p.parseFor("cat dog dog cat", target).size()); 
     808        assertEquals(0, p.parseFor("dog cat dog cat", target).size()); 
    734809 
    735810        target = "maybe_CATs_maybe_DOGs"; 
    736         assertEquals(0, p.parseFor("",                target).length); 
    737         assertEquals(1, p.parseFor("dog",             target).length); 
    738         assertEquals(1, p.parseFor("cat",             target).length); 
    739         assertEquals(1, p.parseFor("cat cat",         target).length); 
    740         assertEquals(1, p.parseFor("cat dog",         target).length); 
    741         assertEquals(1, p.parseFor("dog cat",         target).length); 
    742         assertEquals(1, p.parseFor("dog dog",         target).length); 
    743         assertEquals(1, p.parseFor("cat cat cat",     target).length); 
    744         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    745         assertEquals(1, p.parseFor("cat dog cat",     target).length); 
    746         assertEquals(1, p.parseFor("dog cat dog",     target).length); 
    747         assertEquals(1, p.parseFor("dog dog cat",     target).length); 
    748         assertEquals(1, p.parseFor("dog dog dog",     target).length); 
    749         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
    750         assertEquals(1, p.parseFor("cat dog cat dog", target).length); 
    751         assertEquals(1, p.parseFor("cat dog dog cat", target).length); 
    752         assertEquals(1, p.parseFor("dog cat dog cat", target).length); 
     811        assertEquals(0, p.parseFor("",                target).size()); 
     812        assertEquals(1, p.parseFor("dog",             target).size()); 
     813        assertEquals(1, p.parseFor("cat",             target).size()); 
     814        assertEquals(1, p.parseFor("cat cat",         target).size()); 
     815        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     816        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     817        assertEquals(1, p.parseFor("dog dog",         target).size()); 
     818        assertEquals(1, p.parseFor("cat cat cat",     target).size()); 
     819        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     820        assertEquals(1, p.parseFor("cat dog cat",     target).size()); 
     821        assertEquals(1, p.parseFor("dog cat dog",     target).size()); 
     822        assertEquals(1, p.parseFor("dog dog cat",     target).size()); 
     823        assertEquals(1, p.parseFor("dog dog dog",     target).size()); 
     824        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
     825        assertEquals(1, p.parseFor("cat dog cat dog", target).size()); 
     826        assertEquals(1, p.parseFor("cat dog dog cat", target).size()); 
     827        assertEquals(1, p.parseFor("dog cat dog cat", target).size()); 
    753828 
    754829        target = "must_CATs_must_DOGs"; 
    755         assertEquals(0, p.parseFor("",                target).length); 
    756         assertEquals(0, p.parseFor("dog",             target).length); 
    757         assertEquals(0, p.parseFor("cat",             target).length); 
    758         assertEquals(0, p.parseFor("cat cat",         target).length); 
    759         assertEquals(1, p.parseFor("cat dog",         target).length); 
    760         assertEquals(1, p.parseFor("dog cat",         target).length); 
    761         assertEquals(0, p.parseFor("dog dog",         target).length); 
    762         assertEquals(0, p.parseFor("cat cat cat",     target).length); 
    763         assertEquals(1, p.parseFor("cat cat dog",     target).length); 
    764         assertEquals(1, p.parseFor("cat dog cat",     target).length); 
    765         assertEquals(1, p.parseFor("dog cat dog",     target).length); 
    766         assertEquals(0, p.parseFor("dog dog dog",     target).length); 
    767         assertEquals(1, p.parseFor("cat cat dog dog", target).length); 
    768         assertEquals(1, p.parseFor("cat dog cat dog", target).length); 
    769         assertEquals(1, p.parseFor("cat dog dog cat", target).length); 
    770         assertEquals(1, p.parseFor("dog cat dog cat", target).length); 
     830        assertEquals(0, p.parseFor("",                target).size()); 
     831        assertEquals(0, p.parseFor("dog",             target).size()); 
     832        assertEquals(0, p.parseFor("cat",             target).size()); 
     833        assertEquals(0, p.parseFor("cat cat",         target).size()); 
     834        assertEquals(1, p.parseFor("cat dog",         target).size()); 
     835        assertEquals(1, p.parseFor("dog cat",         target).size()); 
     836        assertEquals(0, p.parseFor("dog dog",         target).size()); 
     837        assertEquals(0, p.parseFor("cat cat cat",     target).size()); 
     838        assertEquals(1, p.parseFor("cat cat dog",     target).size()); 
     839        assertEquals(1, p.parseFor("cat dog cat",     target).size()); 
     840        assertEquals(1, p.parseFor("dog cat dog",     target).size()); 
     841        assertEquals(0, p.parseFor("dog dog dog",     target).size()); 
     842        assertEquals(1, p.parseFor("cat cat dog dog", target).size()); 
     843        assertEquals(1, p.parseFor("cat dog cat dog", target).size()); 
     844        assertEquals(1, p.parseFor("cat dog dog cat", target).size()); 
     845        assertEquals(1, p.parseFor("dog cat dog cat", target).size()); 
    771846    } 
    772847 
    …… 
    796871     * Asserts equality (equivalence) between two Instances,  
    797872     * either Rules or Words 
    798      * @param a The first Instance (expected) 
     873     * @param a The first Instance (expected) 
    799874     * @param b The second Instance (actual) 
    800875     */ 
    …… 
    892967    {         
    893968        Parser p = new Parser(english); 
    894         Edge[][] results = p.parseFor("the man saw the woman", "SENTENCE"); 
    895          
    896         assertEquals(1, results.length); 
    897         Edge[] result = results[0]; 
    898          
    899         Edge SENTENCE = result[0]; 
     969        List edges = p.parseFor("the man saw the woman", "SENTENCE"); 
     970        assertEquals(1, edges.size()); 
     971         
     972        Edge SENTENCE = (Edge)( edges.get(0) ); 
    900973        assertEquals("SENTENCE", SENTENCE.symbol()); 
    901974         
    …… 
    9441017                    new RuleEdge(english[4], new RuleEdge[]{ 
    9451018                            new RuleEdge(english[0], new WordEdge[]{ 
    946                                     new WordEdge("the", english[0].part(0)) 
     1019                                    new WordEdge("the", 0, english[0].part(0)) 
    9471020                            }, english[4].part(0)), 
    9481021                            new RuleEdge(english[1], new WordEdge[]{ 
    949                                     new WordEdge("man", english[1].part(0)) 
     1022                                    new WordEdge("man", 1, english[1].part(0)) 
    9501023                            }, english[4].part(1)) 
    9511024                    }, english[5].part(0)) 
    …… 
    9561029                    new RuleEdge(english[4], new RuleEdge[]{ 
    9571030                            new RuleEdge(english[0], new WordEdge[]{ 
    958                                     new WordEdge("the", english[0].part(0)) 
     1031                                    new WordEdge("the", 3, english[0].part(0)) 
    9591032                            }, english[4].part(0)), 
    9601033                            new RuleEdge(english[2], new WordEdge[]{ 
    961                                     new WordEdge("woman", english[2].part(0)) 
     1034                                    new WordEdge("woman", 4, english[2].part(0)) 
    9621035                            }, english[4].part(1)) 
    9631036                    }, english[6].part(0)) 
    …… 
    9721045                                        new RuleEdge(english[3],  
    9731046                                                new WordEdge[]{ 
    974                                                 new WordEdge("saw",  
     1047                                                new WordEdge("saw", 2, 
    9751048                                                        english[3].part(0)) 
    9761049                                        }, english[7].part(1)), 
    …… 
    9791052                        }, english[9].part(0)) 
    9801053                }), 
    981                 results[0][0] 
     1054                (Edge)( edges.get(0) ) 
    9821055        ); 
    9831056    } 
    …… 
    10311104    } 
    10321105 
    1033     private RuleEdge newRuleInstance(Rule rule, String s1) 
    1034     { 
    1035         Edge i1 = new WordEdge(s1, rule.part(0)); 
     1106    private RuleEdge newRuleInstance(Rule rule, int pos, String s1) 
     1107    { 
     1108        assertEquals(s1, rule.part(0).symbol()); 
     1109        Edge i1 = new WordEdge(s1, pos, rule.part(0)); 
    10361110        return new RuleEdge(rule, new Edge[]{i1}); 
    10371111    } 
    …… 
    10641138    {         
    10651139        Parser p = new Parser(english); 
    1066         Edge[][] results = p.parseFor("the woman saw the man", "SENTENCE"); 
     1140        List edges = p.parseFor("the woman saw the man", "SENTENCE"); 
    10671141         
    10681142        RuleEdge actor = newRuleInstance 
    …… 
    10721146                ( 
    10731147                        english[4],  
    1074                         new RuleEdge(english[0], new WordEdge[]{ 
    1075                                 new WordEdge("the", english[0].part(0)) 
    1076                         }), 
    1077                         new RuleEdge(english[2], new WordEdge[]{ 
    1078                                 new WordEdge("woman", english[2].part(0)) 
    1079                         }) 
     1148                        newRuleInstance(english[0], 0, "the"), 
     1149                        newRuleInstance(english[2], 1, "woman") 
    10801150                ) 
    10811151        ); 
    …… 
    10871157                ( 
    10881158                        english[4],  
    1089                         newRuleInstance(english[0], "the"), 
    1090                         newRuleInstance(english[1], "man") 
     1159                        newRuleInstance(english[0], 3, "the"), 
     1160                        newRuleInstance(english[1], 4, "man") 
    10911161                ) 
    10921162        ); 
    …… 
    11031173                                        english[7], 
    11041174                                        actor, 
    1105                                         newRuleInstance(english[3], "saw"),  
     1175                                        newRuleInstance(english[3], 2, "saw"),  
    11061176                                        undergoer 
    11071177                                ) 
    11081178                        ) 
    11091179                ), 
    1110                 results[0][0] 
     1180                (Edge)( edges.get(0) ) 
    11111181        ); 
    11121182    } 
    …… 
    11421212            ( 
    11431213                    dyirbal[9],  
    1144                     newRuleInstance(dyirbal[1], "bangul"), 
    1145                     newRuleInstance(dyirbal[5], "yara-ngu") 
     1214                    newRuleInstance(dyirbal[1], 0, "bangul"), 
     1215                    newRuleInstance(dyirbal[5], 0, "yara-ngu") 
    11461216            ) 
    11471217    ); 
    …… 
    11531223            ( 
    11541224                    dyirbal[12],  
    1155                     newRuleInstance(dyirbal[0], "balan"), 
    1156                     newRuleInstance(dyirbal[6], "dugumbil") 
     1225                    newRuleInstance(dyirbal[0], 0, "balan"), 
     1226                    newRuleInstance(dyirbal[6], 0, "dugumbil") 
    11571227            ) 
    11581228    ); 
    …… 
    11641234            ( 
    11651235                    dyirbal[11],  
    1166                     newRuleInstance(dyirbal[3], "bayi"), 
    1167                     newRuleInstance(dyirbal[4], "yara") 
     1236                    newRuleInstance(dyirbal[3], 0, "bayi"), 
     1237                    newRuleInstance(dyirbal[4], 0, "yara") 
    11681238            ) 
    11691239    ); 
    …… 
    11751245            ( 
    11761246                    dyirbal[10],  
    1177                     newRuleInstance(dyirbal[2], "bangun"), 
    1178                     newRuleInstance(dyirbal[7], "dugumbi-ru") 
     1247                    newRuleInstance(dyirbal[2], 0, "bangun"), 
     1248                    newRuleInstance(dyirbal[7], 0, "dugumbi-ru") 
    11791249            ) 
    11801250    ); 
    11811251 
    1182     RuleEdge dyirbal_verb_see = newRuleInstance(dyirbal[8], "buran"); 
     1252    RuleEdge dyirbal_verb_see = newRuleInstance(dyirbal[8], 0, "buran"); 
    11831253 
    11841254    RuleEdge dyirbal_SENTENCE_CORE(RuleEdge core) 
    …… 
    11981268    { 
    11991269        Parser p = new Parser(dyirbal); 
    1200         Edge[][] results = p.parseFor(input, "SENTENCE"); 
    1201         if (results.length == 0) 
    1202         { 
    1203             assertTrue("Parse failed: '"+input+"'", false); 
    1204         } 
    1205         if (results.length > 1) 
    1206         { 
    1207             assertEquals("Ambiguous parse: '"+input+"'", 1, results.length); 
    1208         } 
    1209         assertEquals(1, results.length); 
    1210         assertEquals(1, results[0].length); 
     1270        List edges = p.parseFor(input, "SENTENCE"); 
     1271        assertEquals(input, 1, edges.size()); 
    12111272 
    12121273        assertEquals 
    12131274        ( 
    12141275                dyirbal_SENTENCE_CORE(example), 
    1215                 results[0][0] 
     1276                (Edge)( edges.get(0) ) 
    12161277        ); 
    12171278    } 
    …… 
    14101471    {         
    14111472        Parser p = new Parser(hebrew); 
    1412         Edge[][] results = p.parseFor( 
     1473        List edges = p.parseFor( 
    14131474            "W NV<[ JHWH/ >LHJM/ GN/ B <DN=/ MN QDM/", "CLAUSE", false); 
    1414         assertEquals(1, results.length); 
    1415  
    1416         Edge[] result = results[0]; 
    1417         assertEquals(1, result.length); 
    1418         Edge CLAUSE = result[0]; 
     1475        assertEquals(1, edges.size()); 
     1476 
     1477        Edge CLAUSE = (Edge)( edges.get(0) ); 
    14191478         
    14201479        assertEquals("{CLAUSE {CLM {CONJ \"W\"}} " +