recursivedescentparser.java

Grammatica是一个C#和Java的语法分析程序生成器(编译器的编译器)。它可以用LL(k)语法创建可读的和带有注释的源代码。它也支持创建一个运行时语法分析器

/*
 * RecursiveDescentParser.java
 *
 * This work is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2 of the License,
 * or (at your option) any later version.
 *
 * This work is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 *
 * As a special exception, the copyright holders of this library give
 * you permission to link this library with independent modules to
 * produce an executable, regardless of the license terms of these
 * independent modules, and to copy and distribute the resulting
 * executable under terms of your choice, provided that you also meet,
 * for each linked independent module, the terms and conditions of the
 * license of that module. An independent module is a module which is
 * not derived from or based on this library. If you modify this
 * library, you may extend this exception to your version of the
 * library, but you are not obligated to do so. If you do not wish to
 * do so, delete this exception statement from your version.
 *
 * Copyright (c) 2003 Per Cederberg. All rights reserved.
 */

package net.percederberg.grammatica.parser;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

/**
 * A recursive descent parser. This parser handles LL(n) grammars, 
 * selecting the appropriate pattern to parse based on the next few
 * tokens. The parser is more efficient the fewer look-ahead tokens
 * that is has to consider.
 *
 * @author   Per Cederberg, <per at percederberg dot net>
 * @version  1.2
 */
public class RecursiveDescentParser extends Parser {

    /**
     * The map of pattern look-ahead sets. The map is indexed by the
     * production pattern object. 
     */
    private HashMap lookAheads = new HashMap();

    /**
     * Creates a new parser.
     * 
     * @param tokenizer      the tokenizer to use
     */
    public RecursiveDescentParser(Tokenizer tokenizer) {
        super(tokenizer);
    }

    /**
     * Creates a new parser.
     * 
     * @param tokenizer      the tokenizer to use
     * @param analyzer       the analyzer callback to use
     */
    public RecursiveDescentParser(Tokenizer tokenizer, Analyzer analyzer) {
        super(tokenizer, analyzer);
    }

    /**
     * Adds a new production pattern to the parser. The pattern will 
     * be added last in the list. The first pattern added is assumed 
     * to be the starting point in the grammar. The pattern will be
     * validated against the grammar type to some extent.
     * 
     * @param pattern        the pattern to add
     * 
     * @throws ParserCreationException if the pattern couldn't be 
     *             added correctly to the parser
     */
    public void addPattern(ProductionPattern pattern) 
        throws ParserCreationException {

        // Check for empty matches
        if (pattern.isMatchingEmpty()) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PRODUCTION_ERROR,
                pattern.getName(),
                "zero elements can be matched (minimum is one)");
        }
                
        // Check for left-recusive patterns
        if (pattern.isLeftRecursive()) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PRODUCTION_ERROR,
                pattern.getName(),
                "left recursive patterns are not allowed");
        }

        // Add pattern 
        super.addPattern(pattern);
    }

    /**
     * Initializes the parser. All the added production patterns will
     * be analyzed for ambiguities and errors. This method also 
     * initializes the internal data structures used during the 
     * parsing. 
     * 
     * @throws ParserCreationException if the parser couldn't be 
     *             initialized correctly 
     */
    public void prepare() throws ParserCreationException {
        Iterator  iter;

        // Performs production pattern checks
        super.prepare();
        setInitialized(false);

        // Calculate production look-ahead sets
        iter = getPatterns().iterator();
        while (iter.hasNext()) {
            calculateLookAhead((ProductionPattern) iter.next());
        }

        // Set initialized flag
        setInitialized(true);
    }

    /**
     * Parses the input stream and creates a parse tree.
     * 
     * @return the parse tree
     * 
     * @throws ParseException if the input couldn't be parsed 
     *             correctly
     */
    protected Node parseStart() throws ParseException {
        Token      token;
        Node       node;
        ArrayList  list;
        
        node = parsePattern(getStartPattern());
        token = peekToken(0); 
        if (token != null) {
            list = new ArrayList(1);
            list.add("<EOF>");
            throw new ParseException(
                ParseException.UNEXPECTED_TOKEN_ERROR,
                token.toShortString(),
                list,
                token.getStartLine(),
                token.getStartColumn());
        }
        return node;
    }

    /**
     * Parses a production pattern. A parse tree node may or may not
     * be created depending on the analyzer callbacks.
     * 
     * @param pattern        the production pattern to parse
     * 
     * @return the parse tree node created, or null
     * 
     * @throws ParseException if the input couldn't be parsed 
     *             correctly
     */
    private Node parsePattern(ProductionPattern pattern) 
        throws ParseException {

        Token                         token = peekToken(0);
        ProductionPatternAlternative  alt;
        ProductionPatternAlternative  defaultAlt;

        defaultAlt = pattern.getDefaultAlternative(); 
        for (int i = 0; i < pattern.getAlternativeCount(); i++) {
            alt = pattern.getAlternative(i);
            if (defaultAlt != alt && isNext(alt)) {
                return parseAlternative(alt);
            }
        }
        if (defaultAlt == null || !isNext(defaultAlt)) {
            throwParseException(findUnion(pattern));
        }
        return parseAlternative(defaultAlt);
    }
    
    /**
     * Parses a production pattern alternative. A parse tree node may 
     * or may not be created depending on the analyzer callbacks.
     * 
     * @param alt            the production pattern alternative
     * 
     * @return the parse tree node created, or null
     * 
     * @throws ParseException if the input couldn't be parsed 
     *             correctly
     */
    private Node parseAlternative(ProductionPatternAlternative alt) 
        throws ParseException {

        Production  node;
        
        node = new Production(alt.getPattern());
        enterNode(node);
        for (int i = 0; i < alt.getElementCount(); i++) {
            try {
                parseElement(node, alt.getElement(i));
            } catch (ParseException e) {
                addError(e, true);
                nextToken();
                i--;
            }
        }
        return exitNode(node);
    }

    /**
     * Parses a production pattern element. All nodes parsed may or
     * may not be added to the parse tree node specified, depending
     * on the analyzer callbacks.
     *
     * @param node           the production parse tree node  
     * @param elem           the production pattern element to parse
     * 
     * @throws ParseException if the input couldn't be parsed 
     *             correctly
     */
    private void parseElement(Production node, 
                              ProductionPatternElement elem)
        throws ParseException {

        Node  child;

        for (int i = 0; i < elem.getMaxCount(); i++) {
            if (i < elem.getMinCount() || isNext(elem)) {
                if (elem.isToken()) {
                    child = nextToken(elem.getId());
                    enterNode(child);
                    addNode(node, exitNode(child));
                } else {
                    child = parsePattern(getPattern(elem.getId()));
                    addNode(node, child);
                }
            } else {
                break;
            }
        }
    }
    
    /**
     * Checks if the next tokens match a production pattern. The 
     * pattern look-ahead set will be used if existing, otherwise 
     * this method returns false.
     * 
     * @param pattern        the pattern to check
     * 
     * @return true if the next tokens match, or
     *         false otherwise
     */
    private boolean isNext(ProductionPattern pattern) {
        LookAheadSet  set = pattern.getLookAhead();

        if (set == null) {
            return false;
        } else {
            return set.isNext(this);
        }
    }

    /**
     * Checks if the next tokens match a production pattern 
     * alternative. The pattern alternative look-ahead set will be
     * used if existing, otherwise this method returns false.
     *
     * @param alt            the pattern alternative to check
     *  
     * @return true if the next tokens match, or
     *         false otherwise
     */
    private boolean isNext(ProductionPatternAlternative alt) {
        LookAheadSet  set = alt.getLookAhead();

        if (set == null) {
            return false;
        } else {
            return set.isNext(this);
        }
    }
    
    /**
     * Checks if the next tokens match a production pattern element. 
     * If the element has a look-ahead set it will be used, otherwise
     * the look-ahead set of the referenced production or token will
     * be used.
     *
     * @param elem           the pattern element to check
     *  
     * @return true if the next tokens match, or
     *         false otherwise
     */
    private boolean isNext(ProductionPatternElement elem) {