parser.java

Grammatica is a C# and Java parser generator (compiler compiler). It improves upon simlar tools (lik

/*
 * Parser.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.Collection;
import java.util.HashMap;

/**
 * A base parser class. This class provides the standard parser 
 * interface, as well as token handling.
 *
 * @author   Per Cederberg, <per at percederberg dot net>
 * @version  1.4
 */
public abstract class Parser {

    /**
     * The parser initialization flag.
     */
    private boolean initialized = false;

    /**
     * The tokenizer to use.
     */
    private Tokenizer tokenizer;

    /**
     * The analyzer to use for callbacks.
     */
    private Analyzer analyzer;

    /**
     * The list of production patterns. 
     */
    private ArrayList patterns = new ArrayList();

    /**
     * The map with production patterns and their id:s. This map 
     * contains the production patterns indexed by their id:s.
     */
    private HashMap patternIds = new HashMap();

    /**
     * The list of buffered tokens. This list will contain tokens that
     * have been read from the tokenizer, but not yet consumed.
     */
    private ArrayList tokens = new ArrayList();
    
    /**
     * The error log. All parse errors will be added to this log as
     * the parser attempts to recover from the error. If the error
     * count is higher than zero (0), this log will be thrown as the
     * result from the parse() method. 
     */
    private ParserLogException errorLog = new ParserLogException();

    /**
     * The error recovery counter. This counter is initially set to a
     * negative value to indicate that no error requiring recovery 
     * has been encountered. When a parse error is found, the counter
     * is set to three (3), and is then decreased by one for each 
     * correctly read token until it reaches zero (0).  
     */
    private int errorRecovery = -1;

    /**
     * Creates a new parser.
     * 
     * @param tokenizer      the tokenizer to use
     */
    Parser(Tokenizer tokenizer) {
        this(tokenizer, null);
    }

    /**
     * Creates a new parser.
     * 
     * @param tokenizer      the tokenizer to use
     * @param analyzer       the analyzer callback to use
     */
    Parser(Tokenizer tokenizer, Analyzer analyzer) {
        this.tokenizer = tokenizer;
        if (analyzer == null) {
            this.analyzer = new Analyzer();
        } else {
            this.analyzer = analyzer;
        }
    }

    /**
     * Returns the tokenizer in use by this parser.
     * 
     * @return the tokenizer in use by this parser
     * 
     * @since 1.4
     */
    public Tokenizer getTokenizer() {
        return tokenizer;
    }
    
    /**
     * Returns the analyzer in use by this parser.
     * 
     * @return the analyzer in use by this parser
     * 
     * @since 1.4
     */
    public Analyzer getAnalyzer() {
        return analyzer;
    }

    /**
     * Sets the parser initialized flag. Normally this flag is set by
     * the prepare() method, but this method allows further 
     * modifications to it.
     * 
     * @param initialized    the new initialized flag
     */
    void setInitialized(boolean initialized) {
        this.initialized = initialized;
    }

    /**
     * Adds a new production pattern to the parser. The first pattern 
     * added is assumed to be the starting point in the grammar. The 
     * patterns added may be validated 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 {

        Integer  id = new Integer(pattern.getId());
            
        if (pattern.getAlternativeCount() <= 0) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PRODUCTION_ERROR,
                pattern.getName(),
                "no production alternatives are present (must have at " +
                "least one)");
        }
        if (patternIds.containsKey(id)) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PRODUCTION_ERROR,
                pattern.getName(),
                "another pattern with the same id (" + id + 
                ") has already been added");
        }
        patterns.add(pattern);
        patternIds.put(id, pattern);
        setInitialized(false);
    }

    /**
     * Initializes the parser. All the added production patterns will
     * be analyzed for ambiguities and errors. This method also 
     * initializes internal data structures used during the parsing. 
     * 
     * @throws ParserCreationException if the parser couldn't be 
     *             initialized correctly 
     */
    public void prepare() throws ParserCreationException {
        if (patterns.size() <= 0) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PARSER_ERROR,
                "no production patterns have been added");
        }
        for (int i = 0; i < patterns.size(); i++) {
            checkPattern((ProductionPattern) patterns.get(i));
        }
        setInitialized(true);
    }

    /**
     * Checks a production pattern for completeness. If some rule in 
     * the pattern referenced an production pattern not added to this 
     * parser, a parser creation exception will be thrown.  
     * 
     * @param pattern        the production pattern to check
     * 
     * @throws ParserCreationException if the pattern referenced a 
     *             pattern not added to this parser
     */
    private void checkPattern(ProductionPattern pattern) 
        throws ParserCreationException {

        for (int i = 0; i < pattern.getAlternativeCount(); i++) {
            checkRule(pattern.getName(), pattern.getAlternative(i));     
        }
    }

    /**
     * Checks a production pattern rule for completeness. If some 
     * element in the rule referenced an production pattern not added
     * to this parser, a parser creation exception will be thrown.  
     *
     * @param name           the name of the pattern being checked 
     * @param rule           the production pattern rule to check
     * 
     * @throws ParserCreationException if the rule referenced a 
     *             pattern not added to this parser
     */
    private void checkRule(String name, ProductionPatternAlternative rule) 
        throws ParserCreationException {

        for (int i = 0; i < rule.getElementCount(); i++) {
            checkElement(name, rule.getElement(i));
        }
    }

    /**
     * Checks a production pattern element for completeness. If the
     * element references a production pattern not added to this 
     * parser, a parser creation exception will be thrown.  
     * 
     * @param name           the name of the pattern being checked 
     * @param elem           the production pattern element to check
     * 
     * @throws ParserCreationException if the element referenced a
     *             pattern not added to this parser
     */
    private void checkElement(String name, ProductionPatternElement elem) 
        throws ParserCreationException {

        if (elem.isProduction() && getPattern(elem.getId()) == null) {
            throw new ParserCreationException(
                ParserCreationException.INVALID_PRODUCTION_ERROR,
                name,
                "an undefined production pattern id (" + elem.getId() +
                ") is referenced");
        }
    }

    /**
     * Parses the token stream and returns a parse tree. This method
     * will call prepare() if not previously called. In case of a 
     * parse error, the parser will attempt to recover and throw all
     * the errors found in a parser log exception in the end.
     * 
     * @return the parse tree
     * 
     * @throws ParserCreationException if the parser couldn't be
     *             initialized correctly
     * @throws ParserLogException if the input couldn't be parsed 
     *             correctly
     * 
     * @see #prepare
     */
    public Node parse() throws ParserCreationException, ParserLogException {
        Node  root = null;

        // Initialize parser
        if (!initialized) {
            prepare();
        }

        // Parse input
        try {
            root = parseStart();
        } catch (ParseException e) {
            addError(e, true);
        }
        
        // Check for errors
        if (errorLog.getErrorCount() > 0) {
            throw errorLog;
        }

        return root;
    }

    /**
     * Parses the token stream and returns a parse tree.
     * 
     * @return the parse tree
     * 
     * @throws ParseException if the input couldn't be parsed 
     *             correctly
     */
    protected abstract Node parseStart() throws ParseException;

    /**
     * Adds an error to the error log. If the parser is in error 
     * recovery mode, the error will not be added to the log. If the
     * recovery flag is set, this method will set the error recovery 
     * counter thus enter error recovery mode. Only lexical or 
     * syntactical errors require recovery, so this flag shouldn't be
     * set otherwise.
     * 
     * @param e              the error to add
     * @param recovery       the recover flag 
     */
    void addError(ParseException e, boolean recovery) {
        if (errorRecovery <= 0) {
            errorLog.addError(e);