10.5 Sequence Matching

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  10.   Matching Mechanics


A Sequence parser holds a collection of parsers that must each, in turn , match against an assembly. Matching is the main service that the Sequence class provides, as Figure 10.4 shows.

Figure 10.4. The Sequence class. Sequence implements match() so that matching succeeds only if all the parsers in its collection match in succession.


When a sequence matches, it matches against an input collection of assemblies. To perform the match, the sequence matches its first subparser against each assembly in the collection. The result is a new collection of assemblies, all having one property in common: They all are assemblies that have just survived a match of the first subparser. If the input collection is a variable in and you call the first subparser p1 , the new state of the match is

 state1 = p1.match(in); // pseudocode 

Here, state1 is a collection of assemblies that have all matched p1 . Continuing down the path , calling the second subparser p2 , you could write

 state2 = p2.match(state1); // also pseudocode 

Here, state2 is a collection of assemblies that have all matched p1 and p2 . You could also write

 state2 = p2.match(p1.match(state1)); 

If the sequence has three subparsers ” p1 , p2 , and p3 ”you could write

 out = p3.match(p2.match(p1.match(state))); 

To continue this approach, you must loop over all the subparsers of the sequence. Here is the pseudocode for this:

 out = in;  for each subparser p[i] {     out = p[i].match(out); } return out; 

This pseudocode overwrites out in each pass, with the intermediate result of matching one subparser against the previous intermediate result. The actual code for this Sequence.match() is not much different:

 public Vector match(Vector in) {      Vector out = in;     Enumeration e = subparsers.elements();     while (e.hasMoreElements()) {         Parser p = (Parser) e.nextElement();         out = p.matchAndAssemble(out);         if (out.isEmpty()) {             return out;         }     }     return out; } 


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net