江苏龙网

  1. 首页 > 生活 > >

怎样判断一个文法能否写成ll(1)文法

根据LL(1) 文法的定义来判断，分三步走：(1) 文法不含左递归
(2) 对文法中的任一个非终结符A的各个产生式的侯选首终结符集两两不相交，即：若
A-\u0026gt;α1|α2|…|αn ，则
First(αi)∩ First(αj) = φ ( i ≠ j )
(3) 对文法中的每个非终结符A,若它的某个首终结符集含有ε ，则
First(A)∩Follow(A) = φ
?如：判断下述文法是否是LL(1)文法：
S -\u0026gt; aAS|b
A -\u0026gt; bA|ε
(1) 该文法不含左递归
(2)First(S -\u0026gt;aAS)={a} First(S -\u0026gt;b)={b}
First(A -\u0026gt;bA)={b} First(A -\u0026gt;ε)={ε} S和A的侯选式的first集都不相交，满足条件2
(3) 由于ε∈First(A -\u0026gt;ε)
Follow(A)=First(S)={a,b}
Follow(A) ∩ First(A-\u0026gt;bA) ) ≠ φ
【怎样判断一个文法能否写成ll(1)文法】 不满足条件3，则不是LL(1)文法

■网友
先提取左公共因子，再消除左递归，这样就有可能变为LL(1)文法。然后要分别写出改写后文法的FIRST集、FOLLOW集、SELECT集，如果相同左部的SELECT集的交集不为空集，则为LL(1)文法。
■网友
非常抱歉，编译原理我还处于刚接触不多的阶段，这个问题帮不到你了
■网友
操作上说，eleminate left recursion并且left factor这个文法。如果这个文法没有歧义的话，就可以写成ll(1)文法。你要证明它是ll(1)的话，书上都有定义: 对于一个nonterminal 1. first set没有交的部分 2. 至多有一个epsilon production 3. 如果有epsilon production，则follow与first交集为空。


    推荐阅读


    上一篇：太原理工大学物联网专业咋样

    下一篇：Java中volatile怎样保证long和double的原子性操作