testnfaconstruction.java

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

			"c : (A|B) (A|B) ;\n" +
			"d : ( A | B )* ;\n" +
			"e : ( A | B )? ;");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2->.s3\n" +
			".s3->.s4\n" +
			".s4-A..B->.s5\n" +
			".s5->.s3\n" +
			".s5->.s6\n" +
			".s6->:s7\n" +
			":s7-EOF->.s8\n";
		checkRule(g, "a", expecting);
		expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s10->.s11\n" +
			".s11-B->.s12\n" +
			".s12->.s6\n" +
			".s2->.s3\n" +
			".s3->.s10\n" +
			".s3->.s4\n" +
			".s4-A->.s5\n" +
			".s5->.s6\n" +
			".s6->.s3\n" +
			".s6->.s7\n" +
			".s7->:s8\n" +
			":s8-EOF->.s9\n";
		checkRule(g, "b", expecting);
		expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-A..B->.s3\n" +
			".s3-A..B->.s4\n" +
			".s4->:s5\n" +
			":s5-EOF->.s6\n";
		checkRule(g, "c", expecting);
		expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2->.s3\n" +
			".s2->.s9\n" +
			".s3->.s4\n" +
			".s4-A..B->.s5\n" +
			".s5->.s3\n" +
			".s5->.s6\n" +
			".s6->:s7\n" +
			".s9->.s6\n" +
			":s7-EOF->.s8\n";
		checkRule(g, "d", expecting);
		expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2->.s3\n" +
			".s2->.s8\n" +
			".s3-A..B->.s4\n" +
			".s4->.s5\n" +
			".s5->:s6\n" +
			".s8->.s5\n" +
			":s6-EOF->.s7\n";
		checkRule(g, "e", expecting);
	}

	public void testNotSet() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"tokens { A; B; C; }\n"+
			"a : ~A ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-B..C->.s3\n" +
			".s3->:s4\n" +
			":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);

		String expectingGrammarStr =
			"1:8: parser grammar P;\n" +
			"a : ~ A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testNotSingletonBlockSet() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"tokens { A; B; C; }\n"+
			"a : ~(A) ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-B..C->.s3\n" +
			".s3->:s4\n" +
			":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);

		String expectingGrammarStr =
			"1:8: parser grammar P;\n" +
			"a : ~ A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testNotCharSet() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : ~'3' ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-{'\\u0000'..'2', '4'..'\\uFFFE'}->.s3\n" +
			".s3->:s4\n" +
			":s4-<EOT>->.s5\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
				"A : ~ '3' ;\n"+
				"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testNotBlockSet() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : ~('3'|'b') ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFE'}->.s3\n" +
			".s3->:s4\n" +
			":s4-<EOT>->.s5\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
			"A : ~ ('3'|'b');\n" +
			"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testNotSetLoop() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : ~('3')* ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2->.s3\n" +
			".s2->.s9\n" +
			".s3->.s4\n" +
			".s4-{'\\u0000'..'2', '4'..'\\uFFFE'}->.s5\n" +
			".s5->.s3\n" +
			".s5->.s6\n" +
			".s6->:s7\n" +
			".s9->.s6\n" +
			":s7-<EOT>->.s8\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
			"A : (~ '3' )* ;\n" +
			"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testNotBlockSetLoop() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : ~('3'|'b')* ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2->.s3\n" +
			".s2->.s9\n" +
			".s3->.s4\n" +
			".s4-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFE'}->.s5\n" +
			".s5->.s3\n" +
			".s5->.s6\n" +
			".s6->:s7\n" +
			".s9->.s6\n" +
			":s7-<EOT>->.s8\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
			"A : (~ ('3'|'b'))* ;\n" +
			"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testSetsInCombinedGrammarSentToLexer() throws Exception {
		// not sure this belongs in this test suite, but whatever.
		Grammar g = new Grammar(
			"grammar t;\n"+
			"A : '{' ~('}')* '}';\n");
		String result = g.getLexerGrammar();
		String expecting =
			"lexer grammar t;\n" +
			"\n" +
			"// $ANTLR src \"<string>\" 2\n"+
			"A : '{' ~('}')* '}';\n";
		assertEquals(result, expecting);
	}

	public void testLabeledNotSet() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"tokens { A; B; C; }\n"+
			"a : t=~A ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-B..C->.s3\n" +
			".s3->:s4\n" +
			":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);

		String expectingGrammarStr =
			"1:8: parser grammar P;\n" +
			"a : t=~ A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testLabeledNotCharSet() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : t=~'3' ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-{'\\u0000'..'2', '4'..'\\uFFFE'}->.s3\n" +
			".s3->:s4\n" +
			":s4-<EOT>->.s5\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
				"A : t=~ '3' ;\n"+
				"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testLabeledNotBlockSet() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : t=~('3'|'b') ;\n");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFE'}->.s3\n" +
			".s3->:s4\n" +
			":s4-<EOT>->.s5\n";
		checkRule(g, "A", expecting);

		String expectingGrammarStr =
			"1:7: lexer grammar P;\n" +
			"A : t=~ ('3'|'b');\n" +
			"Tokens : A ;";
		assertEquals(expectingGrammarStr, g.toString());
	}

	public void testEscapedCharLiteral() throws Exception {
		Grammar g = new Grammar(
				"grammar P;\n"+
				"a : '\\n';");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-'\\n'->.s3\n" +
			".s3->:s4\n" +
			":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);
	}

	public void testEscapedStringLiteral() throws Exception {
		Grammar g = new Grammar(
				"grammar P;\n"+
				"a : 'a\\nb\\u0030c\\'';");
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s2-'a\\nb\\u0030c\\''->.s3\n" +
			".s3->:s4\n" +
			":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);
	}

	// AUTO BACKTRACKING STUFF

	public void testAutoBacktracking_RuleBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : 'a'{;}|'b';"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s1->.s8\n" +
				".s10->.s5\n" +
				".s2-{synpred1}?->.s3\n" +
				".s3-'a'->.s4\n" +
				".s4->.s5\n" +
				".s5->:s6\n" +
				".s8->.s9\n" +
				".s9-'b'->.s10\n" +
				":s6-EOF->.s7\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_RuleSetBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : 'a'|'b';"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s2-'a'..'b'->.s3\n" +
				".s3->:s4\n" +
				":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_SimpleBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'{;}|'b') ;"
		);
		String expecting =
			".s0->.s1\n" +
			".s1->.s2\n" +
			".s10-'b'->.s11\n" +
			".s11->.s6\n" +
			".s2->.s3\n" +
			".s2->.s9\n" +
			".s3-{synpred1}?->.s4\n" +
			".s4-'a'->.s5\n" +
			".s5->.s6\n" +
			".s6->:s7\n" +
			".s9->.s10\n" +
			":s7-EOF->.s8\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_SetBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'|'b') ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s2-'a'..'b'->.s3\n" +
				".s3->:s4\n" +
				":s4-EOF->.s5\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_StarBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'{;}|'b')* ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s11->.s12\n" +
				".s12-{synpred2}?->.s13\n" +
				".s13-'b'->.s14\n" +
				".s14->.s7\n" +
				".s15->.s8\n" +
				".s2->.s15\n" +
				".s2->.s3\n" +
				".s3->.s11\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'->.s6\n" +
				".s6->.s7\n" +
				".s7->.s3\n" +
				".s7->.s8\n" +
				".s8->:s9\n" +
				":s9-EOF->.s10\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_StarSetBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'|'b')* ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s10->.s7\n" +
				".s2->.s10\n" +
				".s2->.s3\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'..'b'->.s6\n" +
				".s6->.s3\n" +
				".s6->.s7\n" +
				".s7->:s8\n" +
				":s8-EOF->.s9\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_StarBlock1Alt() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a')* ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s10->.s7\n" +
				".s2->.s10\n" +
				".s2->.s3\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'->.s6\n" +
				".s6->.s3\n" +
				".s6->.s7\n" +
				".s7->:s8\n" +
				":s8-EOF->.s9\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_PlusBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'{;}|'b')+ ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s11->.s12\n" +
				".s12-{synpred2}?->.s13\n" +
				".s13-'b'->.s14\n" +
				".s14->.s7\n" +
				".s2->.s3\n" +
				".s3->.s11\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'->.s6\n" +
				".s6->.s7\n" +
				".s7->.s3\n" +
				".s7->.s8\n" +
				".s8->:s9\n" +
				":s9-EOF->.s10\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_PlusSetBlock() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'|'b')+ ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s2->.s3\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'..'b'->.s6\n" +
				".s6->.s3\n" +
				".s6->.s7\n" +
				".s7->:s8\n" +
				":s8-EOF->.s9\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_PlusBlock1Alt() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a')+ ;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s2->.s3\n" +
				".s3->.s4\n" +
				".s4-{synpred1}?->.s5\n" +
				".s5-'a'->.s6\n" +
				".s6->.s3\n" +
				".s6->.s7\n" +
				".s7->:s8\n" +
				":s8-EOF->.s9\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_OptionalBlock2Alts() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a'{;}|'b')?;"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s10-{synpred2}?->.s11\n" +
				".s11-'b'->.s12\n" +
				".s12->.s6\n" +
				".s13->.s6\n" +
				".s2->.s3\n" +
				".s2->.s9\n" +
				".s3-{synpred1}?->.s4\n" +
				".s4-'a'->.s5\n" +
				".s5->.s6\n" +
				".s6->:s7\n" +
				".s9->.s10\n" +
				".s9->.s13\n" +
				":s7-EOF->.s8\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_OptionalBlock1Alt() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a')?;"
		);
		String expecting =
				".s0->.s1\n" +
					".s1->.s2\n" +
					".s2->.s3\n" +
					".s2->.s9\n" +
					".s3-{synpred1}?->.s4\n" +
					".s4-'a'->.s5\n" +
					".s5->.s6\n" +
					".s6->:s7\n" +
					".s9->.s6\n" +
					":s7-EOF->.s8\n";
		checkRule(g, "a", expecting);
	}

	public void testAutoBacktracking_ExistingPred() throws Exception {
		Grammar g = new Grammar(
				"grammar t;\n" +
				"options {backtrack=true;}\n"+
				"a : ('a')=> 'a' | 'b';"
		);
		String expecting =
			".s0->.s1\n" +
				".s1->.s2\n" +
				".s1->.s8\n" +
				".s10->.s5\n" +
				".s2-{synpred1}?->.s3\n" +
				".s3-'a'->.s4\n" +
				".s4->.s5\n" +
				".s5->:s6\n" +
				".s8->.s9\n" +
				".s9-'b'->.s10\n" +
				":s6-EOF->.s7\n";
		checkRule(g, "a", expecting);
	}



	private void checkRule(Grammar g, String rule, String expecting)
    {
        g.createNFAs();
        State startState = g.getRuleStartState(rule);
        FASerializer serializer = new FASerializer(g);
        String result = serializer.serialize(startState);

        //System.out.print(result);
        assertEquals(expecting, result);
    }

}