10.9 Parser Matching Utilities

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  10.   Matching Mechanics


Figure 10.1 shows two methods that support matching: bestMatch() and completeMatch() . The bestMatch() method accepts a single assembly, puts it in a vector, and matches against the vector. Then bestMatch() returns one assembly from the output vector of assemblies, choosing the one whose index is advanced furthest. If a grammar matches only part of an input, bestMatch() returns an assembly that shows the progress made. For example, consider matching the grammar

 adjectives = ("steaming"  "hot")*; 

against the string

 "hot hot steaming hot coffee" 

The following code sends bestMatch() to a parser for adjectives , showing that the parser can match up to the word "coffee" :

 package sjm.examples.mechanics;  import sjm.parse.*; import sjm.parse.tokens.*; /**  * Show that <code>Parser.bestMatch()</code> matches a  * parser against an input as far as possible.  */ public class ShowBestMatch { public static void main(String[] args) {     Alternation a = new Alternation();     a.add(new Literal("steaming"));     a.add(new Literal("hot"));     Repetition adjectives = new Repetition(a);     TokenAssembly ta =         new TokenAssembly("hot hot steaming hot coffee");     System.out.println(adjectives.bestMatch(ta)); } } 

This prints the following:

 [hot, hot, steaming, hot]hot/hot/steaming/hot^coffee 

The bestMatch() method performs three tasks that a user of a parser typically needs: placing an assembly in a vector, matching against that vector, and choosing the longest match. Here is the code for this method:

 /**   * Returns an assembly with the greatest possible number of  * elements consumed by matches of this parser.  */ public Assembly bestMatch(Assembly a) {     Vector initialState = new Vector();     initialState.addElement(a);     Vector finalState = matchAndAssemble(initialState);     return best(finalState); } 

Here is the supporting method, best() :

 /**   * Returns the most-matched assembly in a collection.  */ public Assembly best(Vector v) {     Assembly best = null;     Enumeration e = v.elements();     while (e.hasMoreElements()) {         Assembly a = (Assembly) e.nextElement();         if (!a.hasMoreElements()) {             return a;         }         if (best == null) {             best = a;         }else             if (   a.elementsConsumed() >                 best.elementsConsumed()) {                 best = a;             }     }     return best; } 

You usually want to require that a parser consume all of the input text. For example, an arithmetic parser recognizes

 3 * 4 + 5 and more 

as an arithmetic expression followed by unrecognizable text. To ensure that the best match is a complete match, the Parser class provides a completeMatch() method. Here is the code for completeMatch() :

 /**   * Returns either null or a completely matched version of  * the supplied assembly.  */ public Assembly completeMatch(Assembly a) {     Assembly best = bestMatch(a);     if (best != null && !best.hasMoreElements()) {         return best;     }     return null; } 

This method returns either a complete match or null . Here is an example:

 package sjm.examples.mechanics;   import sjm.parse.*; import sjm.parse.tokens.*; import sjm.examples.arithmetic.*; /**  * This class shows that <code>Parser.completeMatch()</code>  * returns a complete match or null.  */ public class ShowCompleteMatch { public static void main(String[] args)     throws ArithmeticException {     Parser p = ArithmeticParser.start();     TokenAssembly ta =         new TokenAssembly("3 * 4 + 5 and more");     System.out.println(p.bestMatch(ta));     System.out.println(p.completeMatch(ta)); } } 

Running this class prints the following:

 [17.0]3.0/*/4.0/+/5.0^and/more null 

This shows that bestMatch() matches as much input as possible, whereas completeMatch() returns null unless the parser can match all of the input.


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