时间戳

首页 > 解决方案 > 在 JavaCC 语法中查找选择冲突的来源

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

问题描述

我有一个带有麻烦部分的 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”或“酒吧”。生成的代码似乎是正确的，但如果这里有歧义，我没有看到，那么显然这无关紧要。

编辑 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，此处生成的代码生成深度优先树，因为这是我想要的，它可能足以抑制警告。

标签： javaccambiguity

解决方案

你的语法模棱两可。考虑输入

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

推荐阅读