java - 如何消除 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 中，决定采用哪个分支的默认方法是查看下一个标记。如果该 token 与第一选择兼容，则采用第一选择，并且该决定不可逆转。没有回溯。

所以看看选择

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

并假设输入中的下一个标记是 <TOKEN> 。无论是否有 <COMMA> 都会选择第一个选择稍后的。换句话说

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

相当于

  <TOKEN> <COLON> A()

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

<小时/>

一个好的解决方案

您的问题的答案是"is"。一种解决方案是执行您所做的操作并提取公共(public)前缀

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()
}