parsing - 不确定的、不友好的语法？

Question

根据维基百科 GLR 的描述，它们“处理非确定性和模棱两可的语法”。 我可以想象一个模棱两可的语法，就像悬空的 else 问题一样，但是什么是不模棱两可的非确定性 CF 语法？

Answer 1

几乎任何非 LR(k) 语法都是不确定的，但不一定是模棱两可的。明显的例子是当你有一些可以用两种方式解析的任意大的构造时，哪个是正确的取决于大构造之后的东西。例如：

S ::= A x | B y
A ::= A a | a
B ::= B a | a

但是，如果可以组合解析大型构造的两种方法，则通常可以对此类非确定性语法进行修改以使其具有确定性（就像S ::= A x | A y上述语法一样，它是解析相同语言的确定性方法。）

更有趣的是本质上是非确定性的 LANGUAGES——即该语言没有确定性语法。为此，在任意大的构造中需要有一些东西需要与后面的内容相匹配。例如：

S ::= X x | Y y
X ::= a X a | x
Y ::= a Y a | y