testdfaconversion.java

antlr最新版本V3源代码

			".s0-{'\\u0000'..'\\b', '\\n'..'\\u001F', '!'..'x', 'z'..'\\uFFFE'}->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	public void testNoSetCollapseWithActions() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (A | B {foo}) | C;");
		String expecting =
			".s0-A->:s1=>1\n" +
			".s0-B->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	public void testRuleAltsSetCollapse() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : A | B | C ;"
		);
		String expecting = // still looks like block
			" ( grammar t ( rule a ARG RET scope ( BLOCK ( ALT A <end-of-alt> ) ( ALT B <end-of-alt> ) ( ALT C <end-of-alt> ) <end-of-block> ) <end-of-rule> ) )";
		assertEquals(expecting, g.getGrammarTree().toStringTree());
	}

	public void testTokensRuleAltsDoNotCollapse() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"A : 'a';" +
			"B : 'b';\n"
		);
		String expecting =
			".s0-'a'->:s1=>1\n" +
			".s0-'b'->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	public void testMultipleSequenceCollision() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"a : (A{;}|B)\n" +
			"  | (A{;}|B)\n" +
			"  | A\n" +
			"  ;");
		String expecting =
			".s0-A->:s1=>1\n" +
			".s0-B->:s2=>1\n"; // not optimized because states are nondet
		int[] unreachableAlts = new int[] {2,3};
		int[] nonDetAlts = new int[] {1,2,3};
		String ambigInput = "A";
		int[] danglingAlts = null;
		int numWarnings = 3;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
		/* There are 2 nondet errors, but the checkDecision only checks first one :(
		The "B" conflicting input is not checked except by virtue of the
		result DFA.
<string>:2:5: Decision can match input such as "A" using multiple alternatives:
alt 1 via NFA path 7,2,3
alt 2 via NFA path 14,9,10
alt 3 via NFA path 16,17
As a result, alternative(s) 2,3 were disabled for that input,
<string>:2:5: Decision can match input such as "B" using multiple alternatives:
alt 1 via NFA path 7,8,4,5
alt 2 via NFA path 14,15,11,12
As a result, alternative(s) 2 were disabled for that input
<string>:2:5: The following alternatives are unreachable: 2,3
*/
	}

	public void testMultipleAltsSameSequenceCollision() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"a : type ID \n" +
			"  | type ID\n" +
			"  | type ID\n" +
			"  | type ID\n" +
			"  ;\n" +
			"\n" +
			"type : I | F;");
		// nondeterministic from left edge; no stop state
		String expecting =
			".s0-I..F->.s1\n" +
			".s1-ID->:s2=>1\n";
		int[] unreachableAlts = new int[] {2,3,4};
		int[] nonDetAlts = new int[] {1,2,3,4};
		String ambigInput = "I..F ID";
		int[] danglingAlts = null;
		int numWarnings = 2;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testFollowReturnsToLoopReenteringSameRule() throws Exception {
		// D07 can be matched in the (...)? or fall out of esc back into (..)*
		// loop in sl.  Note that D07 is matched by ~(R|SLASH).  No good
		// way to write that grammar I guess
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"sl : L ( esc | ~(R|SLASH) )* R ;\n" +
			"\n" +
			"esc : SLASH ( N | D03 (D07)? ) ;");
		String expecting =
			".s0-R->:s1=>3\n" +
			".s0-SLASH->:s2=>1\n" +
			".s0-{L, N..D07}->:s3=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "D07";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testTokenCallsAnotherOnLeftEdge() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"F   :   I '.'\n" +
			"    ;\n" +
			"I   :   '0'\n" +
			"    ;\n"
		);
		String expecting =
			".s0-'0'->.s1\n" +
			".s1-'.'->:s3=>1\n" +
			".s1-<EOT>->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}


	public void testSelfRecursionAmbigAlts() throws Exception {
		// ambiguous grammar for "L ID R" (alts 1,2 of a)
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a;\n" +
			"a   :   L ID R\n" +
			"    |   L a R\n" + // disabled for L ID R
			"    |   b\n" +
			"    ;\n" +
			"\n" +
			"b   :   ID\n" +
			"    ;\n");
		String expecting =
			".s0-ID->:s5=>3\n" +
			".s0-L->.s1\n" +
			".s1-ID->.s2\n" +
			".s1-L->:s4=>2\n" +
			".s2-R->:s3=>1\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "L ID R";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testIndirectRecursionAmbigAlts() throws Exception {
		// ambiguous grammar for "L ID R" (alts 1,2 of a)
		// This was derived from the java grammar 12/4/2004 when it
		// was not handling a unaryExpression properly.  I traced it
		// to incorrect closure-busy condition.  It thought that the trace
		// of a->b->a->b again for "L ID" was an infinite loop, but actually
		// the repeat call to b only happens *after* an L has been matched.
		// I added a check to see what the initial stack looks like and it
		// seems to work now.
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s   :   a ;\n" +
			"a   :   L ID R\n" +
			"    |   b\n" +
			"    ;\n" +
			"\n" +
			"b   :   ID\n" +
			"    |   L a R\n" +
			"    ;");
		String expecting =
			".s0-ID->:s4=>2\n" +
			".s0-L->.s1\n" +
			".s1-ID->.s2\n" +
			".s1-L->:s4=>2\n" +
			".s2-R->:s3=>1\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "L ID R";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testTailRecursionInvokedFromArbitraryLookaheadDecision() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b X\n" +
			"  | b Y\n" +
			"  ;\n" +
			"\n" +
			"b : A\n" +
			"  | A b\n" +
			"  ;\n");
		String expecting =
			".s0-A->.s1\n" +
				".s1-Y->:s3=>2\n" +
				".s1-{X, A}->:s2=>1\n";
		int[] unreachableAlts = new int[] {1,2};
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = null;
		int[] danglingAlts = null;
		int numWarnings = 2;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testWildcardStarK1AndNonGreedyByDefaultInParser() throws Exception {
		// no error because .* assumes it should finish when it sees R
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"s : A block EOF ;\n" +
			"block : L .* R ;");
		String expecting =
			".s0-A..L->:s2=>1\n" +
			".s0-R->:s1=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	public void testWildcardPlusK1AndNonGreedyByDefaultInParser() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"s : A block EOF ;\n" +
			"block : L .+ R ;");
		String expecting =
			".s0-A..L->:s2=>1\n" +
			".s0-R->:s1=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	// Check state table creation

	public void testCyclicTableCreation() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : A+ X | A+ Y ;");
		String expecting =
			".s0-A->:s1=>1\n" +
			".s0-B->:s2=>2\n";
	}


	// S U P P O R T

	public void _template() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : A | B;");
		String expecting =
			"\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	protected void checkDecision(Grammar g,
								 int decision,
								 String expecting,
								 int[] expectingUnreachableAlts,
								 int[] expectingNonDetAlts,
								 String expectingAmbigInput,
								 int[] expectingDanglingAlts,
								 int expectingNumWarnings)
		throws Exception
	{
		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);

		// mimic actions of org.antlr.Tool first time for grammar g
		if ( g.getNumberOfDecisions()==0 ) {
			g.createNFAs();
			g.createLookaheadDFAs();
		}
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);

		if ( equeue.size()!=expectingNumWarnings ) {
			System.err.println("Warnings issued: "+equeue);
		}

		assertEquals("unexpected number of expected problems",
				   expectingNumWarnings, equeue.size());

		DFA dfa = g.getLookaheadDFA(decision);
		assertNotNull("no DFA for decision "+decision, dfa);
		FASerializer serializer = new FASerializer(g);
		String result = serializer.serialize(dfa.startState);

		List unreachableAlts = dfa.getUnreachableAlts();

		// make sure unreachable alts are as expected
		if ( expectingUnreachableAlts!=null ) {
			BitSet s = new BitSet();
			s.addAll(expectingUnreachableAlts);
			BitSet s2 = new BitSet();
			s2.addAll(unreachableAlts);
			assertEquals("unreachable alts mismatch", s, s2);
		}
		else {
			assertEquals("number of unreachable alts", 0, unreachableAlts.size());
		}

		// check conflicting input
		if ( expectingAmbigInput!=null ) {
			// first, find nondet message
			Message msg = (Message)equeue.warnings.get(0);
			assertTrue("expecting nondeterminism; found "+msg.getClass().getName(),
					    msg instanceof GrammarNonDeterminismMessage);
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			List labels =
				nondetMsg.probe.getSampleNonDeterministicInputSequence(nondetMsg.problemState);
			String input = nondetMsg.probe.getInputSequenceDisplay(labels);
			assertEquals(expectingAmbigInput, input);
		}

		// check nondet alts
		if ( expectingNonDetAlts!=null ) {
			RecursionOverflowMessage recMsg = null;
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			List nonDetAlts = null;
			if ( nondetMsg!=null ) {
				nonDetAlts =
					nondetMsg.probe.getNonDeterministicAltsForState(nondetMsg.problemState);
			}
			else {
				recMsg = getRecursionOverflowMessage(equeue.warnings);
				if ( recMsg!=null ) {
					//nonDetAlts = new ArrayList(recMsg.alts);
				}
			}
			// compare nonDetAlts with expectingNonDetAlts
			BitSet s = new BitSet();
			s.addAll(expectingNonDetAlts);
			BitSet s2 = new BitSet();
			s2.addAll(nonDetAlts);
			assertEquals("nondet alts mismatch", s, s2);
			assertTrue("found no nondet alts; expecting: "+
					    str(expectingNonDetAlts),
					    nondetMsg!=null||recMsg!=null);
		}
		else {
			// not expecting any nondet alts, make sure there are none
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			assertNull("found nondet alts, but expecting none", nondetMsg);
		}

		assertEquals(expecting, result);
	}

	protected GrammarNonDeterminismMessage getNonDeterminismMessage(List warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = (Message) warnings.get(i);
			if ( m instanceof GrammarNonDeterminismMessage ) {
				return (GrammarNonDeterminismMessage)m;
			}
		}
		return null;
	}

	protected RecursionOverflowMessage getRecursionOverflowMessage(List warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = (Message) warnings.get(i);
			if ( m instanceof RecursionOverflowMessage ) {
				return (RecursionOverflowMessage)m;
			}
		}
		return null;
	}

	protected LeftRecursionCyclesMessage getLeftRecursionCyclesMessage(List warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = (Message) warnings.get(i);
			if ( m instanceof LeftRecursionCyclesMessage ) {
				return (LeftRecursionCyclesMessage)m;
			}
		}
		return null;
	}

	protected GrammarDanglingStateMessage getDanglingStateMessage(List warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = (Message) warnings.get(i);
			if ( m instanceof GrammarDanglingStateMessage ) {
				return (GrammarDanglingStateMessage)m;
			}
		}
		return null;
	}

	protected String str(int[] elements) {
		StringBuffer buf = new StringBuffer();
		for (int i = 0; i < elements.length; i++) {
			if ( i>0 ) {
				buf.append(", ");
			}
			int element = elements[i];
			buf.append(element);
		}
		return buf.toString();
	}

}