LL(1)不能含糊
我认为这几乎是LL(1)定义的直接结果。通过矛盾尝试证明;假设你有一个不明确的LL(1)语法,并寻找可以证明是真实的而不是真实的东西。作为一个起点“你在处理输入时总是知道什么?”
由于这看起来像是一个家庭作业问题,而且实际上我还没有完成上述问题,所以我会在上面简单介绍一下。
证明没有模棱两可的语法可以是LL(1)语法。有关提示,请参阅http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf,幻灯片18-20。另见http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf,页码。 11和之前。
这是我的初稿。它可能需要一些微调,但我认为它涵盖了所有的情况。我认为许多解决方案是可能的。这是直接的证据。
(附注:很可惜SO不支持数学,例如在胶乳。)
证明
令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
注意,一个语法是LL(1)如果下式成立每对制作A的 - > B和A - > C:
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(1)的语言,其中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的规则2(1)的语法,以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)
相交,因此只能进行一个派生(非模糊)。
因此,在任何情况下,派生只能通过可用产品之一进行扩展。因此,语法并不含糊。
顺便说一句,我不确信猜测是正确的,但确实看起来很合理。 – BCS 2010-04-17 14:47:39