testdfaconversion.java

antlr最新版本V3源代码

	}

	public void testDoubleInvokeRuleLeftEdge() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b X\n" +
			"  | b Y\n" +
			"  ;\n" +
			"b : c B\n" +
			"  | c\n" +
			"  ;\n" +
			"c : C ;\n");
		String expecting =
			".s0-C->.s1\n" +
			".s1-B->.s4\n" +
			".s1-X->:s2=>1\n" +
			".s1-Y->:s3=>2\n" +
			".s4-X->:s2=>1\n" +
			".s4-Y->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
		expecting =
			".s0-C->.s1\n" +
			".s1-B->:s3=>1\n" +
			".s1-X..Y->:s2=>2\n";
		checkDecision(g, 2, expecting, null, null, null, null, 0);
	}

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

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

	public void testNoStartRule() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : A a | X;"); // single rule 'a' refers to itself; no start rule

		Tool antlr = newTool();
		antlr.setOutputDirectory(null); // write to /dev/null
		CodeGenerator generator = new CodeGenerator(antlr, g, "Java");
		g.setCodeGenerator(generator);
		generator.genRecognizer();

		Message msg = (Message)equeue.warnings.get(0);
		assertTrue("expecting no start rules; found "+msg.getClass().getName(),
				   msg instanceof GrammarSemanticsMessage);
	}

	public void testAStar_immediateTailRecursion2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : A a | A ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-A->:s3=>1\n" +
			".s1-EOF->:s2=>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 testimmediateLeftRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : a A | B;");
		Set leftRecursive = g.getLeftRecursiveRules();
		Set expectedRules = new HashSet() {{add("a");}};
		assertEquals(expectedRules, leftRecursive);
	}

	public void testIndirectLeftRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : b | A ;\n" +
			"b : c ;\n" +
			"c : a | C ;\n");
		Set leftRecursive = g.getLeftRecursiveRules();
		Set expectedRules = new HashSet() {{add("a"); add("b"); add("c");}};
		assertEquals(expectedRules, leftRecursive);
	}

	public void testLeftRecursionInMultipleCycles() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
				"s : a x ;\n" +
				"a : b | A ;\n" +
				"b : c ;\n" +
				"c : a | C ;\n" +
				"x : y | X ;\n" +
				"y : x ;\n");
		Set leftRecursive = g.getLeftRecursiveRules();
		Set expectedRules =
			new HashSet() {{add("a"); add("b"); add("c"); add("x"); add("y");}};
		assertEquals(expectedRules, leftRecursive);
	}

	public void testCycleInsideRuleDoesNotForceInfiniteRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : (A|)+ B;\n");
		// before I added a visitedStates thing, it was possible to loop
		// forever inside of a rule if there was an epsilon loop.
		Set leftRecursive = g.getLeftRecursiveRules();
		Set expectedRules = new HashSet();
		assertEquals(expectedRules, leftRecursive);
	}

	// L O O P S

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

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

	public void testAPlus() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : ( A )+ ;");
		String expecting =
			".s0-A->:s2=>1\n" +
			".s0-EOF->:s1=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback decision
	}

	public void testAPlusNonGreedyWhenDeterministic() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (options {greedy=false;}:A)+ ;\n");
		// should look the same as A+ since no ambiguity
		String expecting =
			".s0-A->:s2=>1\n" +
			".s0-EOF->:s1=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

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

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

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

	// A R B I T R A R Y  L O O K A H E A D

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


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


	public void testAOrBPlusOrAPlus() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (A|B)* X | (A)+ Y;");
		String expecting =
			".s0-A..B->:s2=>1\n" +
			".s0-X->:s1=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback (A|B)*
		expecting =
			".s0-A->:s2=>1\n" +
			".s0-Y->:s1=>2\n";
		checkDecision(g, 2, expecting, null, null, null, null, 0); // loopback (A)+
		expecting =
			".s0-A->.s1\n" +
			".s0-B..X->:s2=>1\n" +
			".s1-A->.s1\n" +
			".s1-B..X->:s2=>1\n" +
			".s1-Y->:s3=>2\n";
		checkDecision(g, 3, expecting, null, null, null, null, 0); // rule
	}

	public void testLoopbackAndExit() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (A|B)+ B;");
		String expecting =
			".s0-A->:s2=>1\n" +
			".s0-B->.s1\n" +
			".s1-A..B->:s2=>1\n" +
			".s1-EOF->:s3=>2\n"; // sees A|B as a set
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

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

	// R E S O L V E  S Y N  C O N F L I C T S

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

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

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

	public void testIndirectIFThenElseStyleAmbig() throws Exception {
		// the (c)+ loopback is ambig because it could match "CASE"
		// by entering the loop or by falling out and ignoring (s)*
		// back falling back into (cg)* loop which stats over and
		// calls cg again.  Either choice allows it to get back to
		// the same node.  The software catches it as:
		// "avoid infinite closure computation emanating from alt 1
		// of ():27|2|[8 $]" where state 27 is the first alt of (c)+
		// and 8 is the first alt of the (cg)* loop.
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"s : stat ;\n" +
			"stat : LCURLY ( cg )* RCURLY | E SEMI  ;\n" +
			"cg : (c)+ (stat)* ;\n" +
			"c : CASE E ;\n");
		String expecting =
			".s0-CASE->:s2=>1\n" +
			".s0-LCURLY..E->:s1=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "CASE";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	// S E T S

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

	public void testComplementToken() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : ~C | C {;} ;\n" +
			"b : X Y Z ;");
		String expecting =
			".s0-C->:s2=>2\n" +
			".s0-X..Z->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	public void testComplementChar() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"A : ~'x' | 'x' {;} ;\n");
		String expecting =
			".s0-'x'->:s2=>2\n" +
			".s0-{'\\u0000'..'w', 'y'..'\\uFFFE'}->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	public void testComplementCharSet() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"A : ~(' '|'\t'|'x'|'y') | 'x';\n" + // collapse into single set
			"B : 'y' ;");
		String expecting =
			".s0-'y'->:s2=>2\n" +