查找 JavaCC 语法中选择冲突的来源

Question

我有一个 JavaCC 语法，其中有一个麻烦的部分可以简化为：

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  ( "(" A() ")" | "biz" )
  ( B() | C() )*
}

void B(): {}
{ "foo" A() }

void C(): {}
{ "bar" A() }

当我编译上面的语法时，JavaCC 在第 ( B() | C() )* 行警告选择冲突。我想了解两件事。首先是为什么它认为在这个案例中存在冲突。 AFAICT 在每个点都应该能够根据当前令牌确定要采用的路径。第二个是如何摆脱警告。我似乎找不到放置 LOOKAHEAD 语句的正确位置。无论我把它放在哪里，我要么得到一个警告，说它不在一个选择点，要么我继续得到同样的警告。以下是我认为它可能喜欢的内容：

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  ( "(" A() ")" | "biz" )
  ( LOOKAHEAD(1) B() | LOOKAHEAD(1) C() )*
}

void B(): {}
{ "foo" A() }

void C(): {}
{ "bar" A() }

但这仍然会产生警告。我也尝试过各种语义前瞻语句，但没有成功。我显然遗漏了什么，但我不知道是什么。 FWIW，在 ( B() | C() )* 之后放置任何标记也“修复”了这个问题，所以我猜它与不知道如何退出该循环有关，但似乎应该只是在它不存在的时候参见“foo”或“bar”。生成的代码似乎是正确的，但如果这里有歧义，我没有看到，那显然没关系。

编辑 1..

在研究和查看 Java 语法后，我发现这让事情变得愉快：

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  ( "(" A() ")" | "biz" )
  ( 
    LOOKAHEAD(2)
    (B() | C()) 
  )*
}

void B(): {}
{ "foo" A() }

void C(): {}
{ "bar" A() }

我仍然不完全清楚为什么它需要额外的令牌来决定在循环中采用哪个选项（也许它真的不需要）。

编辑 2...

好的，我现在明白了，歧义不在B和C之间，而是在深度优先还是广度优先构建树之间。所以以下内容同样模棱两可：

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  ( "(" A() ")" | "biz" )
  (B())*
}

void B(): {}
{ "foo" A() }

从 * 切换到 ? 解决了建议的歧义。

如果我们将 B 更改为 `{ "foo" A() "end" } 这也解决了问题，因为 B 有一个明确的结尾。现在假设我们这样做：

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  ( "(" A() ")" | "biz" )
  ( B() | C() )*
}

void B(): {}
{ "foo" A() "end" }

void C(): {}
{ "bar" A() }

这里我预计 C 也会存在同样的问题，但 JavaCC 仍然报告不明确的前缀是“foo”。这只是报告错误吗？当然，在这种情况下使用 ? 是不可能的，因为那样你就无法匹配连续的 B（我们想要的）。 FWIW，此处生成的代码生成深度优先树，因为这就是我想要的，它可能足以抑制警告。

Answer 1

你的语法有歧义。考虑输入

biz foo biz foo biz EOF

我们有以下两个最左边的推导。

第一个是

    Start
 => ^^^^^ Expand
     A EOF
 =>  ^ Expand
     ( "(" A ")" | "biz") ( B | C)* EOF
 =>                ^^^^^ choose
    "biz" ( B | C )* EOF
 =>       ^^^^^^^^^^ unroll and choose the B
    "biz" B ( B | C )* EOF
 =>       ^ expand
    "biz" "foo" A ( B | C )* EOF
 =>             ^ expand
    "biz" "foo" ( "(" A ")" | "biz") ( B | C)* ( B | C )* EOF
 =>                           ^^^^^ choose
    "biz" "foo" "biz" ( B | C)* ( B | C )* EOF
 =>                   ^^^^^^^^^^ unroll and choose the B
    "biz" "foo" "biz" B ( B | C)* ( B | C )* EOF
 =>                   ^ expand
    "biz" "foo" "biz" "foo" A ( B | C)* ( B | C )* EOF
 =>                         ^ expand
    "biz" "foo" "biz" "foo" ( "(" A ")" | "biz") ( B | C)* ( B | C)* ( B | C )* EOF
 =>                                       ^^^^^ choose
    "biz" "foo" "biz" "foo" "biz" ( B | C)* ( B | C)* ( B | C )* EOF
 =>                               ^^^^^^^^^ Terminate
    "biz" "foo" "biz" "foo" "biz" ( B | C)* ( B | C )* EOF
 =>                               ^^^^^^^^^ Terminate
    "biz" "foo" "biz" "foo" "biz"( B | C )* EOF
 =>                               ^^^^^^^^^ Terminate
    "biz" "foo" "biz" "foo" "biz" EOF

对于第二次推导，一切都与第一次相同，直到解析器必须决定是否进入第二个循环。

    Start
=>*  As above
    "biz" "foo" "biz" ( B | C)* ( B | C )* EOF
=>                    ^^^^^^^^^ Terminate!! (Previously it was expand)
    "biz" "foo" "biz" ( B | C )*
=>                    ^^^^^^^^^^  Unroll and choose B
    "biz" "foo" "biz" B ( B | C )* EOF
=>                    ^ Expand
    "biz" "foo" "biz" "foo" A ( B | C )*  EOF
=>                          ^ Expand
    "biz" "foo" "biz" "foo" ( "(" A ")" | "biz") ( B | C)* ( B | C )*  EOF
=>                                        ^^^^^ Choose
    "biz" "foo" "biz" "foo" "biz" ( B | C)* ( B | C )*  EOF
=>                                ^^^^^^^^^ Terminate
    "biz" "foo" "biz" "foo" "biz"( B | C )* EOF
=>                                ^^^^^^^^^ Terminate
    "biz" "foo" "biz" "foo" "biz" EOF

从解析树的角度来看，有以下两种可能。左边的解析树来自一阶推导。右边的解析树来自第二个

Start  --> A -+---------------------------> biz <--------------+- A <-- Start
              |                                                |
              +-> B -+--------------------> foo <------+-- B <-+
                     |                                 |       |
                     +-> A -+-------------> biz <- A <-+       |
                            |                                  |
                            +-> B -+------> foo <------+-- B <-+
                                   |                   |
                                   +-> A -> biz <- A <-+

当你有选择的时候

LOOKAHEAD(3) X() | Y()

这意味着最多向前看 3 个标记来尝试确定 X() 是否错误。如果接下来的 3 个标记显示 X() 是错误的，则解析器使用 Y()，否则使用 X()。当你的语法有歧义时，再多的展望也无法解决冲突。对于不明确的输入，向前看不会帮助解析器找出哪个选择是“正确的”，哪个选择是“错误的”，因为都是“正确的”。

那么，当您输入“LOOKAHEAD”指令时，为什么 JavaCC 会停止警告。这不是因为前瞻性问题已经解决。这是因为当您放入前瞻指令时，JavaCC 总是会停止发出警告。假设您知道自己在做什么，即使您不知道。

通常处理前瞻性问题的最佳方法是重写语法，使其明确无歧义，LL(1)。

那你该怎么办？我不确定，因为我不知道你喜欢哪种解析树。如果是左边的那个，我想把 * 改成 ?将解决问题。

如果你喜欢右边的解析树，我想下面的语法就可以了

void Start(): {}
{
  A()
  <EOF>
}

void A(): {}
{
  SimpleA()
  ( B() | C() )*
}

void SimpleA() : {}
{
   "(" A() ")" | "biz" 
}

void B(): {}
{ "foo" SimpleA() }

void C(): {}
{ "bar" SimpleA() }

查找 JavaCC 语法中选择冲突的来源

Finding source of choice conflict in JavaCC grammar

javacc

ambiguity

编辑 1..

编辑 2...