TestDFAConversion.java

/*
 * [The "BSD license"]
 *  Copyright (c) 2010 Terence Parr
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.antlr.test;

import org.antlr.Tool;
import org.antlr.analysis.DFA;
import org.antlr.analysis.DecisionProbe;
import org.antlr.analysis.Label;
import org.antlr.codegen.CodeGenerator;
import org.antlr.misc.BitSet;
import org.antlr.tool.*;
import org.junit.Test;

import java.util.*;

import static org.junit.Assert.*;

public class TestDFAConversion extends BaseTest {

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

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

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

	@Test public void testAB_or_AC_k1() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"options {k=1;}\n"+
			"a : A B | A C;");
		String expecting =
			".s0-A->:s1=>1\n";
		int[] unreachableAlts = new int[] {2};
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "A" ;
		int[] danglingAlts = new int[] {2};
		int numWarnings = 2; // ambig upon A
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	@Test public void testselfRecurseNonDet() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : A a X | A a Y;");
		List<Integer> altsWithRecursion = Arrays.asList(1, 2);
		assertNonLLStar(g, altsWithRecursion);
	}

	@Test public void testRecursionOverflow() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a Y | A A A A A X ;\n" + // force recursion past m=4
			"a : A a | Q;");
		List<String> expectedTargetRules = Arrays.asList("a");
		int expectedAlt = 1;
		assertRecursionOverflow(g, expectedTargetRules, expectedAlt);
	}

	@Test public void testRecursionOverflow2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a Y | A+ X ;\n" + // force recursion past m=4
			"a : A a | Q;");
		List<String> expectedTargetRules = Arrays.asList("a");
		int expectedAlt = 1;
		assertRecursionOverflow(g, expectedTargetRules, expectedAlt);
	}

	@Test public void testRecursionOverflowWithPredOk() throws Exception {
		// overflows with k=*, but resolves with pred
		// no warnings/errors
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : (a Y)=> a Y | A A A A A X ;\n" + // force recursion past m=4
			"a : A a | Q;");
		String expecting =
			".s0-A->.s1\n" +
			".s0-Q&&{synpred1_t}?->:s11=>1\n" +
			".s1-A->.s2\n" +
			".s1-Q&&{synpred1_t}?->:s10=>1\n" +
			".s2-A->.s3\n" +
			".s2-Q&&{synpred1_t}?->:s9=>1\n" +
			".s3-A->.s4\n" +
			".s3-Q&&{synpred1_t}?->:s8=>1\n" +
			".s4-A->.s5\n" +
			".s4-Q&&{synpred1_t}?->:s6=>1\n" +
			".s5-{synpred1_t}?->:s6=>1\n" +
			".s5-{true}?->:s7=>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);
	}

	@Test public void testRecursionOverflowWithPredOk2() throws Exception {
		// must predict Z w/o predicate
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : (a Y)=> a Y | A A A A A X | Z;\n" + // force recursion past m=4
			"a : A a | Q;");
		String expecting =
			".s0-A->.s1\n" +
			".s0-Q&&{synpred1_t}?->:s11=>1\n" +
			".s0-Z->:s12=>3\n" +
			".s1-A->.s2\n" +
			".s1-Q&&{synpred1_t}?->:s10=>1\n" +
			".s2-A->.s3\n" +
			".s2-Q&&{synpred1_t}?->:s9=>1\n" +
			".s3-A->.s4\n" +
			".s3-Q&&{synpred1_t}?->:s8=>1\n" +
			".s4-A->.s5\n" +
			".s4-Q&&{synpred1_t}?->:s6=>1\n" +
			".s5-{synpred1_t}?->:s6=>1\n" +
			".s5-{true}?->:s7=>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);
	}

	@Test public void testCannotSeePastRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		List<Integer> altsWithRecursion = Arrays.asList(1, 2);
		assertNonLLStar(g, altsWithRecursion);
	}

	@Test public void testSynPredResolvesRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : (y X)=> y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		String expecting =
			".s0-B->.s4\n" +
			".s0-L->.s1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{synpred1_t}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testSynPredMissingInMiddle() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : (A)=> X\n" +
			"    | X\n" +  // assume missing synpred is true also
			"	 | (C)=> X" +
			"    ;\n");
		String expecting =
			".s0-X->.s1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{synpred2_t}?->:s4=>3\n" +
			".s1-{true}?->:s3=>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);
	}

	@Test public void testAutoBacktrackAndPredMissingInMiddle() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"options {backtrack=true;}\n"+
			"x   : (A)=> X\n" +
			"    | X\n" +  // assume missing synpred is true also
			"	 | (C)=> X" +
			"    ;\n");
		String expecting =
			".s0-X->.s1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +  // gen code should have this as (A)=>
			".s1-{synpred2_t}?->:s3=>2\n" + // gen code should have this as (X)=>
			".s1-{synpred3_t}?->:s4=>3\n"; // gen code should have this as (C)=>
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	@Test public void testSemPredResolvesRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : {p}? y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		String expecting =
			".s0-B->.s4\n" +
			".s0-L->.s1\n" +
			".s1-{p}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{p}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testSemPredResolvesRecursion2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x\n" +
			"options {k=1;}\n" +
			"   : {p}? y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		String expecting =
			".s0-B->.s4\n" +
			".s0-L->.s1\n" +
			".s1-{p}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{p}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testSemPredResolvesRecursion3() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x\n" +
			"options {k=2;}\n" + // just makes bigger DFA
			"   : {p}? y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		String expecting =
			".s0-B->.s6\n" +
			".s0-L->.s1\n" +
			".s1-B->.s5\n" +
			".s1-L->.s2\n" +
			".s2-{p}?->:s3=>1\n" +
			".s2-{true}?->:s4=>2\n" +
			".s5-{p}?->:s3=>1\n" +
			".s5-{true}?->:s4=>2\n" +
			".s6-X->:s3=>1\n" +
			".s6-Y->:s4=>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);
	}

	@Test public void testSynPredResolvesRecursion2() throws Exception {
		// k=* fails and it retries/succeeds with k=1 silently
		// because of predicate
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"statement\n" +
			"    :     (reference ASSIGN)=> reference ASSIGN expr\n" +
			"    |     expr\n" +
			"    ;\n" +
			"expr:     reference\n" +
			"    |     INT\n" +
			"    |     FLOAT\n" +
			"    ;\n" +
			"reference\n" +
			"    :     ID L argument_list R\n" +
			"    ;\n" +
			"argument_list\n" +
			"    :     expr COMMA expr\n" +
			"    ;");
		String expecting =
			".s0-ID->.s1\n" +
			".s0-{FLOAT, INT}->:s3=>2\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>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);
	}

	@Test public void testSynPredResolvesRecursion3() throws Exception {
		// No errors with k=1; don't try k=* first
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"statement\n" +
			"options {k=1;}\n" +
			"    :     (reference ASSIGN)=> reference ASSIGN expr\n" +
			"    |     expr\n" +
			"    ;\n" +
			"expr:     reference\n" +
			"    |     INT\n" +
			"    |     FLOAT\n" +
			"    ;\n" +
			"reference\n" +
			"    :     ID L argument_list R\n" +
			"    ;\n" +
			"argument_list\n" +
			"    :     expr COMMA expr\n" +
			"    ;");
		String expecting =
			".s0-ID->.s1\n" +
			".s0-{FLOAT, INT}->:s3=>2\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>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);
	}

	@Test public void testSynPredResolvesRecursion4() throws Exception {
		// No errors with k=2; don't try k=* first
		// Should be ok like k=1 'except bigger DFA
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"statement\n" +
			"options {k=2;}\n" +
			"    :     (reference ASSIGN)=> reference ASSIGN expr\n" +
			"    |     expr\n" +
			"    ;\n" +
			"expr:     reference\n" +
			"    |     INT\n" +
			"    |     FLOAT\n" +
			"    ;\n" +
			"reference\n" +
			"    :     ID L argument_list R\n" +
			"    ;\n" +
			"argument_list\n" +
			"    :     expr COMMA expr\n" +
			"    ;");
		String expecting =
			".s0-ID->.s1\n" +
			".s0-{FLOAT, INT}->:s4=>2\n" +
			".s1-L->.s2\n" +
			".s2-{synpred1_t}?->:s3=>1\n" +
			".s2-{true}?->:s4=>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);
	}

	@Test public void testSynPredResolvesRecursionInLexer() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"A :     (B ';')=> B ';'\n" +
			"  |     B '.'\n" +
			"  ;\n" +
			"fragment\n" +
			"B :     '(' B ')'\n" +
			"  |     'x'\n" +
			"  ;\n");
		String expecting =
			".s0-'('->.s1\n" +
			".s0-'x'->.s4\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{synpred1_t}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testAutoBacktrackResolvesRecursionInLexer() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar t;\n"+
			"options {backtrack=true;}\n"+
			"A :     B ';'\n" +
			"  |     B '.'\n" +
			"  ;\n" +
			"fragment\n" +
			"B :     '(' B ')'\n" +
			"  |     'x'\n" +
			"  ;\n");
		String expecting =
			".s0-'('->.s1\n" +
			".s0-'x'->.s4\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{synpred1_t}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testAutoBacktrackResolvesRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n" +
			"options {backtrack=true;}\n"+
			"x   : y X\n" +
			"    | y Y\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		String expecting =
			".s0-B->.s4\n" +
			".s0-L->.s1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n" +
			".s4-{synpred1_t}?->:s2=>1\n" +
			".s4-{true}?->:s3=>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);
	}

	@Test public void testselfRecurseNonDet2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : P a P | P;");
		// nondeterministic from left edge
		String expecting =
			".s0-P->.s1\n" +
			".s1-EOF->:s3=>2\n"+
			".s1-P->:s2=>1\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "P P";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	@Test public void testIndirectRecursionLoop() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : b X ;\n"+
			"b : a B ;\n");

		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);

		Set<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules =
			new HashSet<String>() {{add("a"); add("b");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));

		assertEquals(1, equeue.errors.size());
		Message msg = equeue.errors.get(0);
		assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(),
				    msg instanceof LeftRecursionCyclesMessage);
		LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg;

		// cycle of [a, b]
		Collection<? extends Collection<? extends Rule>> result = cyclesMsg.cycles;
		Set<String> expecting = new HashSet<String>() {{add("a"); add("b");}};
		assertEquals(expecting, ruleNames2(result));
	}

	@Test public void testIndirectRecursionLoop2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : i b X ;\n"+ // should see through i
			"b : a B ;\n" +
			"i : ;\n");

		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);

		Set<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules =
			new HashSet<String>() {{add("a"); add("b");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));

		assertEquals(1, equeue.errors.size());
		Message msg = equeue.errors.get(0);
		assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(),
				    msg instanceof LeftRecursionCyclesMessage);
		LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg;

		// cycle of [a, b]
		Collection<? extends Collection<? extends Rule>> result = cyclesMsg.cycles;
		Set<String> expecting = new HashSet<String>() {{add("a"); add("b");}};
		assertEquals(expecting, ruleNames2(result));
	}

	@Test public void testIndirectRecursionLoop3() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : i b X ;\n"+ // should see through i
			"b : a B ;\n" +
			"i : ;\n" +
			"d : e ;\n" +
			"e : d ;\n");

		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);

		Set<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules =
			new HashSet<String>() {{add("a"); add("b"); add("e"); add("d");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));

		assertEquals(1, equeue.errors.size());
		Message msg = equeue.errors.get(0);
		assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(),
				    msg instanceof LeftRecursionCyclesMessage);
		LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg;

		// cycle of [a, b]
		Collection<? extends Collection<? extends Rule>> result = cyclesMsg.cycles;
		Set<String> expecting = new HashSet<String>() {{add("a"); add("b"); add("d"); add("e");}};
		assertEquals(expecting, ruleNames2(result));
	}

	@Test public void testifThenElse() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : IF s (E s)? | B;\n" +
			"slist: s SEMI ;");
		String expecting =
			".s0-E->:s1=>1\n" +
			".s0-SEMI->:s2=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "E";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
		expecting =
			".s0-B->:s2=>2\n" +
			".s0-IF->:s1=>1\n";
		checkDecision(g, 2, expecting, null, null, null, null, 0);
	}

	@Test public void testifThenElseChecksStackSuffixConflict() throws Exception {
		// if you don't check stack soon enough, this finds E B not just E
		// as ambig input
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"slist: s SEMI ;\n"+
			"s : IF s el | B;\n" +
			"el: (E s)? ;\n");
		String expecting =
			".s0-E->:s1=>1\n" +
			".s0-SEMI->:s2=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "E";
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 2, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
		expecting =
			".s0-B->:s2=>2\n" +
			".s0-IF->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

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

	@Test
    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->.s2\n" +
			".s1-X->:s3=>1\n" +
			".s1-Y->:s4=>2\n" +
			".s2-X->:s3=>1\n" +
			".s2-Y->:s4=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
		expecting =
			".s0-C->.s1\n" +
            ".s1-B->:s2=>1\n" +
            ".s1-X..Y->:s3=>2\n";
		checkDecision(g, 2, expecting, null, null, null, null, 0);
	}

	@Test 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);
	}

	@Test
    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);
	}

	@Test 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 = equeue.warnings.get(0);
		assertTrue("expecting no start rules; found "+msg.getClass().getName(),
				   msg instanceof GrammarSemanticsMessage);
	}

	@Test
    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->:s2=>1\n" +
            ".s1-EOF->:s3=>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);
	}

	@Test public void testimmediateLeftRecursion() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : a ;\n" +
			"a : a A | B;");
		Set<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules = new HashSet<String>() {{add("a");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));
	}

	@Test 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<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules = new HashSet<String>() {{add("a"); add("b"); add("c");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));
	}

	@Test 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<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<String> expectedRules =
			new HashSet<String>() {{add("a"); add("b"); add("c"); add("x"); add("y");}};
		assertEquals(expectedRules, ruleNames(leftRecursive));
	}

	@Test 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<Rule> leftRecursive = g.getLeftRecursiveRules();
		Set<Rule> expectedRules = new HashSet<Rule>();
		assertEquals(expectedRules, leftRecursive);
	}

	// L O O P S

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

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

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

	@Test 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->:s1=>1\n" +
			".s0-EOF->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	@Test public void testAPlusNonGreedyWhenNonDeterministic() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (options {greedy=false;}:A)+ A+ ;\n");
		// should look the same as A+ since no ambiguity
		String expecting =
			".s0-A->:s1=>2\n"; // always chooses to exit
		int[] unreachableAlts = new int[] {1};
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "A";
		int[] danglingAlts = null;
		int numWarnings = 2;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	@Test public void testAPlusGreedyWhenNonDeterministic() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (options {greedy=true;}:A)+ A+ ;\n");
		// should look the same as A+ since no ambiguity
		String expecting =
			".s0-A->:s1=>1\n"; // always chooses to enter loop upon A
		// turns off 1 of warnings. A can never exit loop now
		int[] unreachableAlts = new int[] {2};
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

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

	@Test 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
	}

	@Test 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

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

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


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

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

	@Test 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

	@Test 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);
	}

	@Test 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);
	}

	@Test 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);
	}

	@Test 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-E..RCURLY->: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

	@Test 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);
	}

	@Test 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);
	}

	@Test 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'..'\\uFFFF'}->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	@Test 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" +
			".s0-{'\\u0000'..'\\b', '\\n'..'\\u001F', '!'..'x', 'z'..'\\uFFFF'}->:s1=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, 0);
	}

	@Test 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);
	}

	@Test 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());
	}

	@Test 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);
	}

	@Test 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
*/
	}

	@Test 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-F..I->.s1\n" +
			".s1-ID->:s2=>1\n";
		int[] unreachableAlts = new int[] {2,3,4};
		int[] nonDetAlts = new int[] {1,2,3,4};
		String ambigInput = "F..I ID";
		int[] danglingAlts = null;
		int numWarnings = 2;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, danglingAlts, numWarnings);
	}

	@Test 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-D03..N->:s2=>2\n" +
			".s0-R->:s3=>3\n" +
			".s0-SLASH->:s1=>1\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);
	}

	@Test 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);
	}


	@Test 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);
	}

	@Test 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);
	}

	@Test 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");
		List<Integer> altsWithRecursion = Arrays.asList(1, 2);
		assertNonLLStar(g, altsWithRecursion);
	}

	@Test 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);
	}

	@Test 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);
	}

	@Test public void testGatedSynPred() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : (X)=> X\n" +
			"    | Y\n" +
			"    ;\n");
		String expecting =
			".s0-X&&{synpred1_t}?->:s1=>1\n" + // does not hoist; it gates edges
			".s0-Y->: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);

		Set<String> preds = g.synPredNamesUsedInDFA;
		Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}};
		assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds);
	}

	@Test public void testHoistedGatedSynPred() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : (X)=> X\n" +
			"    | X\n" +
			"    ;\n");
		String expecting =
			".s0-X->.s1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" + // hoists into decision
			".s1-{true}?->:s3=>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);

		Set<String> preds = g.synPredNamesUsedInDFA;
		Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}};
		assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds);
	}

	@Test public void testHoistedGatedSynPred2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : (X)=> (X|Y)\n" +
			"    | X\n" +
			"    ;\n");
		String expecting =
			".s0-X->.s1\n" +
			".s0-Y&&{synpred1_t}?->:s2=>1\n" +
			".s1-{synpred1_t}?->:s2=>1\n" +
			".s1-{true}?->:s3=>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);

		Set<String> preds = g.synPredNamesUsedInDFA;
		Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}};
		assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds);
	}

	@Test public void testGreedyGetsNoErrorForAmbig() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : IF s (options {greedy=true;} : E s)? | B;\n" +
			"slist: s SEMI ;");
		String expecting =
			".s0-E->:s1=>1\n" +
			".s0-SEMI->: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);
		expecting =
			".s0-B->:s2=>2\n" +
			".s0-IF->:s1=>1\n";
		checkDecision(g, 2, expecting, null, null, null, null, 0);
	}

	@Test public void testGreedyNonLLStarStillGetsError() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"x   : ( options {greedy=true;}\n" +
			"	   : y X\n" +
			"      | y Y\n" +
			"	   )\n" +
			"    ;\n" +
			"y   : L y R\n" +
			"    | B\n" +
			"    ;");
		List<Integer> altsWithRecursion = Arrays.asList(1, 2);
		assertNonLLStar(g, altsWithRecursion);
	}

	@Test public void testGreedyRecOverflowStillGetsError() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"s : (options {greedy=true;} : a Y | A A A A A X) ;\n" + // force recursion past m=4
			"a : A a | Q;");
		List<String> expectedTargetRules = Arrays.asList("a");
		int expectedAlt = 1;
		assertRecursionOverflow(g, expectedTargetRules, expectedAlt);
	}


	// Check state table creation

	@Test 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

	private 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 assertNonLLStar(Grammar g, List<Integer> expectedBadAlts) {
		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.buildNFA();
			g.createLookaheadDFAs(false);
		}
		NonRegularDecisionMessage msg = getNonRegularDecisionMessage(equeue.errors);
		assertTrue("expected fatal non-LL(*) msg", msg!=null);
		List<Integer> alts = new ArrayList<Integer>(msg.altsWithRecursion);
		Collections.sort(alts);
		assertEquals(expectedBadAlts,alts);
	}

	protected void assertRecursionOverflow(Grammar g,
										   List<String> expectedTargetRules,
										   int expectedAlt) {
		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.buildNFA();
			g.createLookaheadDFAs(false);
		}
		RecursionOverflowMessage msg = getRecursionOverflowMessage(equeue.errors);
		assertTrue("missing expected recursion overflow msg"+msg, msg!=null);
		assertEquals("target rules mismatch",
					 expectedTargetRules.toString(), msg.targetRules.toString());
		assertEquals("mismatched alt", expectedAlt, msg.alt);
	}

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

    @Test
    public void testWildcardInTreeGrammar2() throws Exception {
        Grammar g = new Grammar(
            "tree grammar t;\n" +
            "a : ^(A X Y) | ^(A . .) ;\n");
        String expecting =
            ".s0-A->.s1\n" +
            ".s1-DOWN->.s2\n" +
            ".s2-X->.s3\n" +
            ".s2-{A, Y}->:s6=>2\n" +
            ".s3-Y->.s4\n" +
            ".s3-{DOWN, A..X}->:s6=>2\n" +
            ".s4-DOWN->:s6=>2\n" +
            ".s4-UP->:s5=>1\n";
        int[] unreachableAlts = null;
        int[] nonDetAlts = new int[] {1,2};
        String ambigInput = null;
        int[] danglingAlts = null;
        int numWarnings = 1;
        checkDecision(g, 1, expecting, unreachableAlts,
                      nonDetAlts, ambigInput, danglingAlts, numWarnings);
    }

    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.buildNFA();
			g.createLookaheadDFAs(false);
		}
		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<Integer> 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!=null?unreachableAlts.size():0);
		}

		// check conflicting input
		if ( expectingAmbigInput!=null ) {
			// first, find nondet message
			Message msg = equeue.warnings.get(0);
			assertTrue("expecting nondeterminism; found "+msg.getClass().getName(),
					    msg instanceof GrammarNonDeterminismMessage);
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			List<Label> 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<Integer> 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<Message> warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = warnings.get(i);
			if ( m instanceof GrammarNonDeterminismMessage ) {
				return (GrammarNonDeterminismMessage)m;
			}
		}
		return null;
	}

	protected NonRegularDecisionMessage getNonRegularDecisionMessage(List<Message> errors) {
		for (int i = 0; i < errors.size(); i++) {
			Message m = errors.get(i);
			if ( m instanceof NonRegularDecisionMessage ) {
				return (NonRegularDecisionMessage)m;
			}
		}
		return null;
	}

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

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

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

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

	protected Set<String> ruleNames(Collection<? extends Rule> rules) {
		Set<String> x = new HashSet<String>();
		for (Rule r : rules) {
			x.add(r.name);
		}
		return x;
	}

	protected Set<String> ruleNames2(Collection<? extends Collection<? extends Rule>> rules) {
		Set<String> x = new HashSet<String>();
		for (Collection<? extends Rule> s : rules) {
			x.addAll(ruleNames(s));
		}
		return x;
	}
}