给定语法是否有歧义？

Question

考虑下面的语法...

bexp -> bterm | bterm ‘||’ bexp
bterm -> bfact | bfact ‘&&’ bterm
bfact -> true | false | id | ‘(‘ bexp ‘)’

假设我们用 '!' 扩展 BEXP通过如下更改 bfact 规则来否定运算符：-

bfact -> true | false | id | '(' bexp ')' | '!' bexp

我们将此扩展语法称为 BEXP2。我如何证明它是模棱两可的？

Answer 1

你可以通过找到一个有两个解析的字符串来证明它是有歧义的:)

在这种情况下，请尝试 !id&&id。是 (!id)&&id 还是 !(id&&id)

Given grammar ambiguous or not?