llkanalyzer.java

SRI international 发布的OAA框架软件

package antlr_oaa;

/* ANTLR Translator Generator
 * Project led by Terence Parr at http://www.jGuru.com
 * Software rights: http://www.antlr.org/RIGHTS.html
 *
 * $Id: LLkAnalyzer.java,v 1.1 2002/11/08 17:37:56 agno Exp $
 */

import antlr_oaa.collections.impl.BitSet;
import antlr_oaa.collections.impl.Vector;

/**A linear-approximate LL(k) grammar analzyer.
 *
 * All lookahead elements are sets of token types.
 *
 * @author  Terence Parr, John Lilley
 * @see     antlr_oaa.Grammar
 * @see     antlr_oaa.Lookahead
 */
public class LLkAnalyzer implements LLkGrammarAnalyzer {
	// Set "analyzerDebug" to true
	public boolean DEBUG_ANALYZER = false;
	private AlternativeBlock currentBlock;
	protected Tool tool = null;
	protected Grammar grammar = null;
	// True if analyzing a lexical grammar
	protected boolean lexicalAnalysis = false;
	// Used for formatting bit sets in default (Java) format
	CharFormatter charFormatter = new JavaCharFormatter();

	/** Create an LLk analyzer */
	public LLkAnalyzer(Tool tool_) {
		tool = tool_;
	}

	/** Return true if someone used the '.' wildcard default idiom.
	 *  Either #(. children) or '.' as an alt by itself.
	 */
	protected boolean altUsesWildcardDefault(Alternative alt) {
		AlternativeElement head = alt.head;
		// if element is #(. blah) then check to see if el is root
		if (head instanceof TreeElement &&
			((TreeElement) head).root instanceof WildcardElement ) {
			return true;
		}
		if (head instanceof WildcardElement && head. next instanceof BlockEndElement) {
			return true;
		}
		return false;
	}

	/**Is this block of alternatives LL(k)?  Fill in alternative cache for this block.
	 * @return true if the block is deterministic
	 */
	public boolean deterministic(AlternativeBlock blk) {
		/** The lookahead depth for this decision */
		int k=1;	// start at k=1
		if ( DEBUG_ANALYZER ) System.out.println("deterministic("+blk+")");
		boolean det = true;
		int nalts = blk.alternatives.size();
		AlternativeBlock saveCurrentBlock = currentBlock;
		Alternative wildcardAlt = null;
		currentBlock = blk;

		/* don't allow nongreedy (...) blocks */
		if ( blk.greedy==false && !(blk instanceof OneOrMoreBlock) && !(blk instanceof ZeroOrMoreBlock) ) {
			tool.warning("Being nongreedy only makes sense for (...)+ and (...)*", grammar.getFilename(), blk.getLine());
		}

		// SPECIAL CASE: only one alternative.  We don't need to check the
		// determinism, but other code expects the lookahead cache to be
		// set for the single alt.
		if ( nalts==1 ) {
			AlternativeElement e = blk.getAlternativeAt(0).head;
			currentBlock.alti = 0;
			blk.getAlternativeAt(0).cache[1] = e.look(1);
			blk.getAlternativeAt(0).lookaheadDepth = 1;	// set lookahead to LL(1)
			currentBlock = saveCurrentBlock;
			return true;	// always deterministic for one alt
		}

	outer:
		for (int i=0; i<nalts-1; i++) {
			currentBlock.alti = i;
			currentBlock.analysisAlt = i;	// which alt are we analyzing?
			currentBlock.altj = i+1;		// reset this alt.  Haven't computed yet,
			// but we need the alt number.
		inner:
			// compare against other alternatives with lookahead depth k
			for (int j=i+1; j<nalts; j++) {
				currentBlock.altj = j;
				if ( DEBUG_ANALYZER ) System.out.println("comparing "+i+" against alt "+j);
				currentBlock.analysisAlt = j;	// which alt are we analyzing?
				k = 1;	// always attempt minimum lookahead possible.
				
				// check to see if there is a lookahead depth that distinguishes
				// between alternatives i and j.
				Lookahead[] r = new Lookahead[grammar.maxk+1];
				boolean haveAmbiguity;
				do {
					haveAmbiguity = false;
					if ( DEBUG_ANALYZER ) System.out.println("checking depth "+k+"<="+grammar.maxk);
					Lookahead p,q;
					p = getAltLookahead(blk, i, k);
					q = getAltLookahead(blk, j, k);

					// compare LOOK(alt i) with LOOK(alt j).  Is there an intersection?
					// Lookahead must be disjoint.
					if ( DEBUG_ANALYZER ) System.out.println("p is "+p.toString(",", charFormatter, grammar));
					if ( DEBUG_ANALYZER ) System.out.println("q is "+q.toString(",", charFormatter, grammar));
					// r[i] = p.fset.and(q.fset);
					r[k] = p.intersection(q);
					if ( DEBUG_ANALYZER ) System.out.println("intersection at depth "+k+" is "+r[k].toString());
					if ( !r[k].nil() ) {
						haveAmbiguity = true;
						k++;
					}
					// go until no more lookahead to use or no intersection
				} while ( haveAmbiguity && k <= grammar.maxk );

				Alternative ai = blk.getAlternativeAt(i);
				Alternative aj = blk.getAlternativeAt(j);
				if ( haveAmbiguity ) {
					det = false;
					ai.lookaheadDepth = NONDETERMINISTIC;
					aj.lookaheadDepth = NONDETERMINISTIC;

					/* if ith alt starts with a syntactic predicate, computing the
					 * lookahead is still done for code generation, but messages
					 * should not be generated when comparing against alt j.
					 * Alternatives with syn preds that are unnecessary do
					 * not result in syn pred try-blocks.
					 */
					if ( ai.synPred != null ) {
						if ( DEBUG_ANALYZER ) {
							System.out.println("alt "+i+" has a syn pred");
						}
						// The alt with the (...)=> block is nondeterministic for sure.
						// If the (...)=> conflicts with alt j, j is nondeterministic.
						// This prevents alt j from being in any switch statements.
						// move on to next alternative=>no possible ambiguity!
						//						continue inner;
					}

					/* if ith alt starts with a semantic predicate, computing the
					 * lookahead is still done for code generation, but messages
					 * should not be generated when comparing against alt j.
					 */
					else if ( ai.semPred != null ) {
						if ( DEBUG_ANALYZER ) {
							System.out.println("alt "+i+" has a sem pred");
						}
					}

					/* if jth alt is exactly the wildcard or wildcard root of tree,
					 * then remove elements from alt i lookahead from alt j's lookahead.
					 * Don't do an ambiguity warning.
					 */
					else if ( altUsesWildcardDefault(aj) ) {
						// System.out.println("removing pred sets");
						// removeCompetingPredictionSetsFromWildcard(aj.cache, aj.head, grammar.maxk);
						wildcardAlt = aj;
					}
					
					/* If the user specified warnWhenFollowAmbig=false, then we
					 * can turn off this warning IFF one of the alts is empty;
					 * that is, it points immediately at the end block.
					 */
					else if ( !blk.warnWhenFollowAmbig &&
							  (ai.head instanceof BlockEndElement ||
							   aj.head instanceof BlockEndElement) )
						{
							// System.out.println("ai.head pts to "+ai.head.getClass());
							// System.out.println("aj.head pts to "+aj.head.getClass());
						}

					/* If they have the generateAmbigWarnings option off for the block
					 * then don't generate a warning.
					 */
					else if ( !blk.generateAmbigWarnings ) {
					}

					/* If greedy=true and *one* empty alt shut off warning. */
					else if ( blk.greedySet && blk.greedy &&
							  ((ai.head instanceof BlockEndElement &&
								!(aj.head instanceof BlockEndElement)) ||
							   (aj.head instanceof BlockEndElement &&
								!(ai.head instanceof BlockEndElement))) ) {
						// System.out.println("greedy set to true; one alt empty");
					}
					
						
					/* We have no choice, but to report a nondetermism */
					else {
						tool.errorHandler.warnAltAmbiguity(
										   grammar,
										   blk,			// the block
										   lexicalAnalysis,// true if lexical
										   grammar.maxk,	// depth of ambiguity
										   r,				// set of linear ambiguities
										   i,				// first ambiguous alternative
										   j				// second ambiguous alternative
														   );
					}
				}
				else {
					// a lookahead depth, k, was found where i and j do not conflict
					ai.lookaheadDepth = Math.max(ai.lookaheadDepth,k);
					aj.lookaheadDepth = Math.max(aj.lookaheadDepth,k);
				}
			}
		}

		// finished with block.

		// If had wildcard default clause idiom, remove competing lookahead
		/*
		  if ( wildcardAlt!=null ) {
		  removeCompetingPredictionSetsFromWildcard(wildcardAlt.cache, wildcardAlt.head, grammar.maxk);
		  }
		*/

		currentBlock = saveCurrentBlock;
		return det;
	}

	/**Is (...)+ block LL(1)?  Fill in alternative cache for this block.
	 * @return true if the block is deterministic
	 */
	public boolean deterministic(OneOrMoreBlock blk) {
		if ( DEBUG_ANALYZER ) System.out.println("deterministic(...)+("+blk+")");
		AlternativeBlock saveCurrentBlock = currentBlock;
		currentBlock = blk;
		boolean blkOk = deterministic((AlternativeBlock)blk);
		// block has been checked, now check that what follows does not conflict
		// with the lookahead of the (...)+ block.
		boolean det = deterministicImpliedPath(blk);
		currentBlock = saveCurrentBlock;
		return det&&blkOk;
	}

	/**Is (...)* block LL(1)?  Fill in alternative cache for this block.
	 * @return true if the block is deterministic
	 */
	public boolean deterministic(ZeroOrMoreBlock blk) {
		if ( DEBUG_ANALYZER ) System.out.println("deterministic(...)*("+blk+")");
		AlternativeBlock saveCurrentBlock = currentBlock;
		currentBlock = blk;
		boolean blkOk = deterministic((AlternativeBlock)blk);
		// block has been checked, now check that what follows does not conflict
		// with the lookahead of the (...)* block.
		boolean det = deterministicImpliedPath(blk);
		currentBlock = saveCurrentBlock;
		return det&&blkOk;
	}

    /**Is this (...)* or (...)+ block LL(k)?
     * @return true if the block is deterministic
     */
    public boolean deterministicImpliedPath(BlockWithImpliedExitPath blk) {
		/** The lookahead depth for this decision considering implied exit path */
		int k;
		boolean det = true;
		Vector alts = blk.getAlternatives();
		int nalts = alts.size();
		currentBlock.altj = -1;	// comparing against implicit optional/exit alt

		if ( DEBUG_ANALYZER ) System.out.println("deterministicImpliedPath");
		for (int i=0; i<nalts; i++) {		// check follow against all alts
			Alternative alt = blk.getAlternativeAt(i);
			
			if ( alt.head instanceof BlockEndElement ) {
				tool.warning("empty alternative makes no sense in (...)* or (...)+", grammar.getFilename(), blk.getLine());
			}
			
			k = 1;							// assume eac alt is LL(1) with exit branch
			// check to see if there is a lookahead depth that distinguishes
			// between alternative i and the exit branch.
			Lookahead[] r = new Lookahead[grammar.maxk+1];
			boolean haveAmbiguity;
			do {
				haveAmbiguity = false;
				if ( DEBUG_ANALYZER ) System.out.println("checking depth "+k+"<="+grammar.maxk);
				Lookahead p;
				Lookahead follow = blk.next.look(k);
				blk.exitCache[k] = follow;
				currentBlock.alti = i;
				p = getAltLookahead(blk, i, k);

				if ( DEBUG_ANALYZER ) System.out.println("follow is "+follow.toString(",", charFormatter, grammar));
				if ( DEBUG_ANALYZER ) System.out.println("p is "+p.toString(",", charFormatter, grammar));
				//r[k] = follow.fset.and(p.fset);
				r[k] = follow.intersection(p);
				if ( DEBUG_ANALYZER ) System.out.println("intersection at depth "+k+" is "+r[k]);
				if ( !r[k].nil() ) {
					haveAmbiguity = true;
					k++;
				}
				// go until no more lookahead to use or no intersection
			} while ( haveAmbiguity && k <= grammar.maxk );

			if ( haveAmbiguity )
				{
					det = false;
					alt.lookaheadDepth = NONDETERMINISTIC;
					blk.exitLookaheadDepth = NONDETERMINISTIC;
					Alternative ambigAlt = blk.getAlternativeAt(currentBlock.alti);

					/* If the user specified warnWhenFollowAmbig=false, then we
					 * can turn off this warning.
					 */
					if ( !blk.warnWhenFollowAmbig ) {
					}

					/* If they have the generateAmbigWarnings option off for the block
					 * then don't generate a warning.
					 */
					else if ( !blk.generateAmbigWarnings ) {
					}

					/* If greedy=true and alt not empty, shut off warning */
					else if ( blk.greedy==true && blk.greedySet &&
							  !(ambigAlt.head instanceof BlockEndElement) ) {
						if ( DEBUG_ANALYZER ) System.out.println("greedy loop");
					}

					/* If greedy=false then shut off warning...will have
					 * to add "if FOLLOW break"
					 * block during code gen to compensate for removal of warning.
					 */
					else if( blk.greedy==false &&
							 !(ambigAlt.head instanceof BlockEndElement) ) {
						if ( DEBUG_ANALYZER ) System.out.println("nongreedy loop");
						// if FOLLOW not single k-string (|set[k]| can
						// be > 1 actually) then must warn them that
						// loop may terminate incorrectly.
						// For example, ('a'..'d')+ ("ad"|"cb")
						if ( !lookaheadEquivForApproxAndFullAnalysis(blk.exitCache, grammar.maxk) ) {
							tool.warning(new String[] {
								"nongreedy block may exit incorrectly due",
									"\tto limitations of linear approximate lookahead (first k-1 sets",
									"\tin lookahead not singleton)."},
								grammar.getFilename(), blk.getLine());
						}
					}

					// no choice but to generate a warning
					else {
						tool.errorHandler.warnAltExitAmbiguity(
															   grammar,
															   blk,		// the block
															   lexicalAnalysis,	// true if lexical
															   grammar.maxk,	// depth of ambiguity
															   r,		// set of linear ambiguities
															   i		// ambiguous alternative
															   );
					}		
				}