testsemanticpredicates.java

ANTLR(ANother Tool for Language Recognition)它是这样的一种工具

		checkDecision(g, 2, expecting, null, null, null, null, null, 0);
	}

	public void testGatedPredHoistsAndCanBeInStopState() throws Exception {
		// I found a bug where merging stop states made us throw away
		// a stop state with a gated pred!
		Grammar g = new Grammar(
			"grammar u;\n" +
			"a : b+ ;\n" +
			"b : 'x' | {p}?=> 'y' ;");
		String expecting =
			".s0-'x'->:s2=>1\n" +
			".s0-'y'&&{p}?->:s3=>1\n" +
			".s0-EOF->:s1=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0);
	}

	public void testGatedPredInCyclicDFA() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : {p}?=> ('a')+ 'x' ;\n" +
			"B : {q}?=> ('a'|'b')+ 'x' ;");
		String expecting =
			".s0-'a'&&{(p||q)}?->.s1\n" +
			".s0-'b'&&{q}?->:s5=>2\n" +
			".s1-'a'&&{(p||q)}?->.s1\n" +
			".s1-'b'&&{q}?->:s5=>2\n" +
			".s1-'x'&&{(p||q)}?->.s2\n" +
			".s2-<EOT>&&{(p||q)}?->.s3\n" +
			".s3-{p}?->:s4=>1\n" +
			".s3-{q}?->:s5=>2\n";
		checkDecision(g, 3, expecting, null, null, null, null, null, 0);
	}

	public void testGatedPredDoesNotForceAllToBeGated() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}? C ;\n");
		String expecting =
			".s0-B->:s1=>1\n" +
			".s0-C&&{q}?->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0);
	}

	public void testGatedPredDoesNotForceAllToBeGated2() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}?=> C\n" +
			"  | B\n" +
			"  ;\n");
		String expecting =
			".s0-B->.s1\n" +
			".s0-C&&{(q&&r)}?->:s3=>2\n" +
			".s1-{p}?->:s2=>1\n" +
			".s1-{q}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0);
	}

	public void testORGatedPred() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}?=> C\n" +
			"  | {s}?=> B\n" +
			"  ;\n");
		String expecting =
			".s0-B->.s1\n" +
			".s0-C&&{(q&&r)}?->:s3=>2\n" +
			".s1-{(q&&s)}?->:s3=>2\n" +
			".s1-{p}?->:s2=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0);
	}

	/** The following grammar should yield an error that rule 'a' has
	 *  insufficient semantic info pulled from 'b'.
	 */
	public void testIncompleteSemanticHoistedContext() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | B;\n" +
			"b : {p1}? B | B ;");
		String expecting =
			".s0-B->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "B", new int[] {1}, null, 3);
	}

	/** The following grammar should yield an error that rule 'a' has
	 *  insufficient semantic info pulled from 'b'.  This is the same
	 *  as the previous case except that the D prevents the B path from
	 *  "pinching" together into a single NFA state.
	 *
	 *  This test also demonstrates that just because B D could predict
	 *  alt 1 in rule 'a', it is unnecessary to continue NFA->DFA
	 *  conversion to include an edge for D.  Alt 1 is the only possible
	 *  prediction because we resolve the ambiguity by choosing alt 1.
	 */
	public void testIncompleteSemanticHoistedContext2() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | B;\n" +
			"b : {p1}? B | B D ;");
		String expecting =
			".s0-B->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "B", new int[] {1},
					  null, 3);
	}

	public void testTooFewSemanticPredicates() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : {p1}? A | A | A ;");
		String expecting =
			".s0-A->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2,3},
					  new int[] {1,2,3}, "A",
					  null, null, 2);
	}

	public void testPredWithK1() throws Exception {
		Grammar g = new Grammar(
			"\tlexer grammar TLexer;\n" +
			"A\n" +
			"options {\n" +
			"  k=1;\n" +
			"}\n" +
			"  : {p1}? ('x')+ '.'\n" +
			"  | {p2}? ('x')+ '.'\n" +
			"  ;\n");
		String expecting =
			".s0-'x'->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings);
	}

	public void testPredWithArbitraryLookahead() throws Exception {
		Grammar g = new Grammar(
			"\tlexer grammar TLexer;\n" +
			"A : {p1}? ('x')+ '.'\n" +
			"  | {p2}? ('x')+ '.'\n" +
			"  ;\n");
		String expecting =
			".s0-'x'->.s1\n" +
			".s1-'.'->.s2\n" +
			".s1-'x'->.s1\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{p2}?->:s4=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings);
	}


	/** For a DFA state with lots of configurations that have the same
	 *  predicate, don't just OR them all together as it's a waste to
	 *  test a||a||b||a||a etc...  ANTLR makes a unique set and THEN
	 *  OR's them together.
	 */
	public void testUniquePredicateOR() throws Exception {
		Grammar g = new Grammar(
			"parser grammar v;\n" +
			"\n" +
			"a : {a}? b\n" +
			"  | {b}? b\n" +
			"  ;\n" +
			"\n" +
			"b : {c}? (X)+ ;\n" +
			"\n" +
			"c : a\n" +
			"  | b\n" +
			"  ;\n");
		String expecting =
			".s0-X->.s1\n" +
			".s1-{((a&&c)||(b&&c))}?->:s2=>1\n" +
			".s1-{c}?->:s3=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings);
	}

	// 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";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "L ID R";
		int[] insufficientPredAlts = new int[] {1};
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings);
	}

	protected void checkDecision(Grammar g,
								 int decision,
								 String expecting,
								 int[] expectingUnreachableAlts,
								 int[] expectingNonDetAlts,
								 String expectingAmbigInput,
								 int[] expectingInsufficientPredAlts,
								 int[] expectingDanglingAlts,
								 int expectingNumWarnings)
		throws Exception
	{
		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);
		// mimic actions of org.antlr.Tool first time for grammar g
		if ( g.getNumberOfDecisions()==0 ) {
			g.createNFAs();
			g.createLookaheadDFAs();
		}

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

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

		DFA dfa = g.getLookaheadDFA(decision);
		FASerializer serializer = new FASerializer(g);
		String result = serializer.serialize(dfa.startState);
		//System.out.print(result);
		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("unreachable alts mismatch", 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 ) {
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			assertNotNull("found no nondet alts; expecting: "+
										str(expectingNonDetAlts), nondetMsg);
			List nonDetAlts =
				nondetMsg.probe.getNonDeterministicAltsForState(nondetMsg.problemState);
			// compare nonDetAlts with expectingNonDetAlts
			BitSet s = new BitSet();
			s.addAll(expectingNonDetAlts);
			BitSet s2 = new BitSet();
			s2.addAll(nonDetAlts);
			assertEquals("nondet alts mismatch", s, s2);
		}
		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 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();
	}
}