LL(1)不能含糊不清

Question

怎么能证明没有LL(1)语法可以模棱两可？

我知道什么是模棱两可的语法,但无法证明上述定理/引理.

Answer 1

我认为这几乎是LL(1)定义的直接结果.尝试通过矛盾证明; 假设你有一个含糊不清的LL(1)语法,并寻找你可以证明是真实而不是真实的东西.作为一个起点"你在处理输入时总是知道什么？"

因为这似乎是一个家庭作业问题而且我实际上还没有完成问题,而不是我在上面勾画出来,我会停在那里.

Answer 2

这是我在证明中的第一稿.它可能需要一些微调,但我认为它涵盖了所有情况.我认为很多解决方案是可行的.这是一个直接的证据.

(旁注:遗憾的是,SO不支持数学,例如在LaTeX中.)

证明

设T和N为终端和非终端符号集.

让以下举行

MaybeEmpty(s) = true <=> s ->* empty
First(s) = X containing all x for which there exists Y such that s ->* xY
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ

请注意,如果以下每个产品对A - > B和A - > C保持以下,则语法为LL(1):

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C))
2. (First(B) intersect First(C)) = empty
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty

考虑一种LL为(LL)的语言,用A -> B和A -> C.也就是说有一些终端串TZ允许不同的解析树进行多次推导.

假设左派生到达S ->* TAY ->* TZ.下一步可能是TAY -> TBY,或TAY -> TCY.因此,如果两者兼而有之BY ->* Z,语言就会模棱两可CY ->* Z.(注意,由于A是任意非终端,如果不存在这种情况,则该语言是非模糊的.)

案例1:Z =空

根据LL(1)语法的规则1,B和C中的至多一个可以导出空(非模糊情况).

情况2:Z非空,B和C都不为空

通过LL(1)语法的规则2,B和C中的至多一个可以允许进一步的推导,因为Z的前导终端不能同时存在(First(B)并且First(C)是非模糊的情况).

情况3:Z非空,或者是MaybeEmpty(B)或者MaybeEmpty(C)

注意LL(1)语法的规则1,B和C不能都导出空.因此假设这MaybeEmpty(C)是真的.

这给出了两个子案例.

案例3A:CY -> Y; 和案例3b:,CY ->* DY其中D不为空.

在3a中我们必须在BY ->* Z和之间CY -> Y ->* Z做出选择,但请注意First(Y) subset-of Follow(A).由于Follow(A)不相交First(B),因此只能进行一次推导(非模糊).

在3b中我们必须在BY ->* Z和之间CY ->* DY ->* Z做出选择,但请注意First(D) subset-of First(C).由于First(C)不相交First(B),因此只能进行一次推导(非模糊).

因此,在每种情况下,推导只能通过可用产品之一进行扩展.因此语法不含糊.