/* * 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);