10.2 Parser Matching

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  10.   Matching Mechanics


The main goals of a parser are to match text and to use assemblers to build a result in an assembly. Matching is what differentiates, say, a sequence from an alternation from a repetition. As you'll soon see, a parser that contains alternations or repetitions does not always know which way or how many times to perform a match. The solution used in this book is to add all possible alternatives into an output set. Some alternative algorithms for matching are faster, but they impose constraints on allowable grammars. For a thorough analysis of approaches to matching, see Compilers [Aho et al.].

Each parser in the hierarchy beneath Parser implements matching in a different way. Figure 10.1 shows the aspects of the Parser class that relate to establishing an assembler and to matching.

Figure 10.1. Parser matching and assembling. The methods bestMatch() and completeMatch() hide the fact that the Parser class's matching algorithm works with a set (or Vector ) of assemblies.


The Parser hierarchy relies on the Vector class for managing sets of assemblies. To be compatible with early versions of Java that did not have a Set class, the classes in sjm.parse use Vector as if it were Set . The Parser class provides two static methods that facilitate the manipulation of vectors. The add() method appends the elements of a second vector to the first vector in its parameter list. The elementClone() method returns a vector that contains clones of the elements of a given vector. Subclasses use these methods in implementing match() .

The match() method, which is abstract, and the matchAndAssemble() method form the heart of matching. The mechanics of matching are different for every subclass of Parser , but the collaboration of parsers, assemblies, and assemblers is the same for every parser. So even though every subclass of Parser must implement match() , only Parser itself has a matchAndAssemble() method.

The matchAndAssemble() method follows the template method pattern [Gamma et al.], implementing an algorithm but deferring some steps to subclasses. Specifically, this method accepts a vector of input assemblies, applies the abstract match() method against these, and applies the parser's assembler against each result. Here is the code for matchAndAssemble() :

 /**   * Match this parser against an input state, and then  * apply this parser's assembler against the resulting  * state.  *  */ public Vector matchAndAssemble(Vector in) {     Vector out = match(in);     if (assembler != null) {         Enumeration e = out.elements();         while (e.hasMoreElements()) {             assembler.workOn((Assembly) e.nextElement());         }     }     return out; } 

This method establishes the mechanics of matching and then assembling, although it relies on the abstract match() method, which subclasses must implement.


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

Similar book on Amazon

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