How do I remove a choice conflict in JavaCC?

Question

My production rules are as follows:

OtherNonTerminal := NonTerminal | {}
NonTerminal := <TOKEN>:A() | <TOKEN>:A(), Nonterminal()

In JavaCC, NonTerminal has a choice conflict:

void OtherNonTerminal() : {}
{
    Nonterminal() | {}
}

void Nonterminal() : {}
{
    <TOKEN> <COLON> A()
|
    <TOKEN> <COLON> A() <COMMA> Nonterminal()
}

Would this be one way to get rid of the choice conflict and will the program worked as specified like my NonTerminal production rule?

void Nonterminal() : {}
{
    <TOKEN> <COLON> A() (<COMMA> NonTerminal())? 
}

Answer 1

Why is there a problem

In JavaCC, the default method of deciding which branch to take is by looking at the next token. It that token is compatible with the first choice, the first choice is taken and that decision is not reversible. There is no backtracking.

So look at the choice

void Nonterminal() : {}
{
    <TOKEN> <COLON> A()
|
    <TOKEN> <COLON> A() <COMMA> Nonterminal()
}

and suppose the next token in the input is <TOKEN>. The first choice will be taken regardless of whether there is a <COMMA> later on. In other words

  <TOKEN> <COLON> A()
| <TOKEN> <COLON> A() <COMMA> Nonterminal()

is equivalent to

  <TOKEN> <COLON> A()

Except the first will produce a warning message since JavaCC sees that what you have written doesn't make sense.

---

A good solution

The answer to your question is "yes". One solution is to do what you did and factor out the common prefix

void Nonterminal() : {}
{
    <TOKEN> <COLON> A() (<COMMA> NonTerminal())? 
}

---

A solution that might be better, depending

If, for some reason, you really don't what to factor, you can also do the following

void Nonterminal() : {}
{
    LOOKAHEAD( <TOKEN> <COLON> A() <COMMA>)
    <TOKEN> <COLON> A() <COMMA> Nonterminal()
|
    <TOKEN> <COLON> A()
}

Here, the parser will look ahead in input stream. If it sees the comma, the first choice is taken. Otherwise, the second.

This might be useful if the semantic actions are different in the two cases. E.g.

  LOOKAHEAD( <TOKEN> <COLON> A() <COMMA>)
  <TOKEN> {doSomething();} <COLON> A() <COMMA> Nonterminal()
|
  <TOKEN> {doSomethingDifferent();} <COLON> A()

---

A nonrecursive solution.

A third alternative is

void Nonterminal() : {}
{
    Foo() (<COMMA>  Foo() )*
}

void Foo() : {}
{
    <TOKEN> <COLON> A()
}