如何消除 JavaCC 中的选择冲突？

Question

我的制作规则如下：

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

在JavaCC中，NonTerminal有一个选择冲突：

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

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

这是消除选择冲突的一种方法吗？程序是否会像我的 NonTerminal 生产规则那样按照指定的方式运行？

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

Answer 1

为什么会出现问题

在 JavaCC 中，决定采用哪个分支的默认方法是查看下一个标记。如果令牌与第一选择兼容，则采用第一选择并且该决定是不可逆的。没有回溯。

所以看选择

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

并假设输入中的下一个标记是 <TOKEN>。不管后面有没有<COMMA>，都取第一个。也就是说

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

等同于

  <TOKEN> <COLON> A()

除了第一个会产生一条警告消息，因为 JavaCC 认为您编写的内容没有意义。

---

一个好的解决方案

您问题的答案是 "yes"。一种解决方案是做你所做的并分解出公共前缀

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

---

可能更好的解决方案，具体取决于

如果出于某种原因，您真的不知道要考虑什么，您也可以执行以下操作

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

在这里，解析器将在输入流中向前看。如果它看到逗号，则采用第一个选择。否则，第二个。

如果两种情况下的语义动作不同，这可能会有用。例如

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

---

非递归解决方案。

第三个选择是

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

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