parser.cs

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

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