/* * Parser.cs * * 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. */using System;using System.Collections;using System.Text;namespace PerCederberg.Grammatica.Parser {    /**     * 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 bool 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 Hashtable patternIds = new Hashtable();            /**         * 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         */        internal Parser(Tokenizer tokenizer)             : this(tokenizer, null) {        }        /**         * Creates a new parser.         *          * @param tokenizer       the tokenizer to use         * @param analyzer        the analyzer callback to use         */        internal 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         */        internal void SetInitialized(bool 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 virtual void AddPattern(ProductionPattern pattern) {            if (pattern.GetAlternativeCount() <= 0) {                throw new ParserCreationException(                    ParserCreationException.ErrorType.INVALID_PRODUCTION,                    pattern.GetName(),                    "no production alternatives are present (must have at " +                    "least one)");            }            if (patternIds.ContainsKey(pattern.GetId())) {                throw new ParserCreationException(                    ParserCreationException.ErrorType.INVALID_PRODUCTION,                    pattern.GetName(),                    "another pattern with the same id (" + pattern.GetId() +                     ") has already been added");            }            patterns.Add(pattern);            patternIds.Add(pattern.GetId(), 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 virtual void Prepare() {            if (patterns.Count <= 0) {                throw new ParserCreationException(                    ParserCreationException.ErrorType.INVALID_PARSER,                    "no production patterns have been added");            }            for (int i = 0; i < patterns.Count; i++) {                CheckPattern((ProductionPattern) patterns[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) {            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) {                        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) {            if (elem.IsProduction() && GetPattern(elem.GetId()) == null) {                throw new ParserCreationException(                    ParserCreationException.ErrorType.INVALID_PRODUCTION,                    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() {            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();            /**         * 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          */        internal void AddError(ParseException e, bool recovery) {            if (errorRecovery <= 0) {                errorLog.AddError(e);            }            if (recovery) {                errorRecovery = 3;