时间戳

首页 > 解决方案 > 如何消除 JavaCC 中的选择冲突？

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

问题描述

我的生产规则如下：

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

标签： javaparsingrecursioncompiler-constructionjavacc

解决方案

为什么会出现问题

在 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 认为您编写的内容没有意义。

一个很好的解决方案

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

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

推荐阅读