recursivedescentparser.cs

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

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

namespace PerCederberg.Grammatica.Parser {

    /**
     * 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.0
     */
    public class RecursiveDescentParser : Parser {

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

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

        /**
         * Creates a new parser.
         * 
         * @param tokenizer      the tokenizer to use
         * @param analyzer       the analyzer callback to use
         */
        public RecursiveDescentParser(Tokenizer tokenizer, 
                                      Analyzer analyzer) 
            : base(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 override void AddPattern(ProductionPattern pattern) {

            // Check for empty matches
            if (pattern.IsMatchingEmpty()) {
                throw new ParserCreationException(
                    ParserCreationException.ErrorType.INVALID_PRODUCTION,
                    pattern.GetName(),
                    "zero elements can be matched (minimum is one)");
            }
                
            // Check for left-recusive patterns
            if (pattern.IsLeftRecursive()) {
                throw new ParserCreationException(
                    ParserCreationException.ErrorType.INVALID_PRODUCTION,
                    pattern.GetName(),
                    "left recursive patterns are not allowed");
            }

            // Add pattern 
            base.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 override void Prepare() {
            IEnumerator  e;
            
            // Performs production pattern checks
            base.Prepare();
	        SetInitialized(false);
            
            // Calculate production look-ahead sets
            e = GetPatterns().GetEnumerator();
            while (e.MoveNext()) {
                CalculateLookAhead((ProductionPattern) e.Current);
            }
            
            // 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 override Node ParseStart() {
            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.ErrorType.UNEXPECTED_TOKEN,
                    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) {
            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) {
            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) {

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