发布时间 : 星期一 文章编译原理 复习资料更新完毕开始阅读
2）用定义法或关系图法计算FIRST、FOLLOW集； 3）计算各规则的SELECT集； 4）根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL(1)文法。
三、用关系图计算FIRST集
1、终结符a结点用符号本身标记，非终结符A结点用FIRST(A)标记；
2、对A→αXβ且α=*>ε，则从A到X连一条箭弧(注意：A→aB或A→a已包含在其中)；
3、凡从FIRST(A)结点出发有路径可达到的所有终结符都为FIRST(A)的成员； 4、再根据A能否推导出ε的情况，若能推导出ε，则将ε加入FIRST(A)。
四、用关系图计算FOLLOW集
1、终结符a和#结点用符号本身标记，非终结符A结点用FIRST(A)或FOLLOW (A)标记；
2、从开始符S的FOLLOW(S)到#号连一条箭弧；
3、对规则 A→αBβX且β=*>ε，则从FOLLOW(B)到FIRST(X)连一条箭弧，当X∈ＶT时，则与X相连；
4、对A→αBβ且β=*>ε，则从FOLLOW(B)到FOLLOW(A)连一条箭弧； 5、对每一个FIRST(A)结点，若有规则A→αXβ，且α=*>ε，则从FIRST(A)到FIRST(X)连一条箭弧；
6、凡从FOLLOW(A)结点出发有路径可到达的所有终结符或#，都为FOLLOW(A)的成员；
五、例题
例1：判别下列G[S]是否为LL(1)文法，要求用关系图求FIRST集和FOLLOW集。 G[S]：S → AB|bC A →ε|b B →ε|aD C → b|AD D → aS|c 解：(1)画出非终结符推导ε的情况表，如下图1所示：
(2)用关系图计算各非终结符的FIRST集，如下图2、图3所示：
图1 图2
图3
(3)用关系图求出FOLLOW集，如下图4、图5所示：
图4 图5
4)根据前述三张表计算SELECTT集如下：
(5)判别是否为LL(1)文法
由于：SELECT(S →AB)∩SELECT(S → bC)={b}≠φ，SELECT(C → b)∩SELECT(C → AD)={b}≠φ。故 G[S]不是 LL((1)文法。 例2：LL((1)文法例子。
G[E]：E → T E' E'→ + T E'｜ε T → F T' T'→ * F T'｜ε F → ( E )｜i 解：由于SELECT(E'→+TE')={+} SELECT(E'→ε)={#，)}
SELECT(T'→ * F T')={*} SELECT(T'→ε)={+，#，)} SELECT(F →( E )) ={(} SELECT(F →i)={i} SELECT( E'→+TE')∩SELECT (E'→ε) = {+}∩{#，)} =φ
SELECT (T'→ * F T') ∩SELECT (T'→ε) = {*}∩{+，#，)} =φ SELECT (F →( E ))∩SELECT (F →i) = {(}∩{i} =φ 故 G[E]是 LL((1)文法。
例3：非LL((1)文法例子。对下列文法G[S]作输入串cad的分析。 G[S]：S→cAd A→ab|a
结论：非 LL(1)文法具有不确定性。 不确定性的解决方法：
（1） 采用带回朔的（即确定的）自顶向下分析法：过于复杂，代价很高，实用编译程序几乎不用。
（2）改写文法：将非 LL((1)文法改写为等价的 LL((1)文法。 授课顺序：8
教学目的：让学生掌握非LL(1)文法到LL(1)文法的转换方法、了解递归子程序
分析法的基本原理，掌握预测分析方法及应用。
教学重点：非LL(1)文法到LL(1)文法的转换、预测分析表的构造、预测分析方法的应用
教学难点：非LL(1)文法到LL(1)文法的转换、预测分析方法的应用 授课学时：2学时
教学方式：多媒体讲授 教学内容：
5.3某些非LL(1)向LL(1)文法的等价转换
非LL(1)的文法不能用确定的自顶向下分析法。可通过消除左递归、提取左公共因子的方法将非LL(1)文法转换成LL(1)文法。 一、提取左公共因子
1、左公共因子引发的问题
文法G中有形如： A→ αβ|αγ的规则时，会导致：FIRST(αβ)与 FIRST(αγ )相交，使得：SELECT( A→ αβ)∩ SELECT( A→ αγ) ≠φ，则G必为非LL(1)文法。 2、提取左公共因子的方法
（1）特殊形式：将形如 A → αβ|αγ的规则先提取左公共因子： A → α(β|γ)， 再引进新非终结符A?，改为： A → α A?和 A? →β|γ。 （2）一般形式：将形如 A→αβ1|αβ2|…|αβn的规则改写为：A→αA?和 A'→β1|β2|…|βn。 （3）推广：将形如 A→αβ1|αβ2|…|αβn |γ1|γ2|… | γm的规则改写为：A→αA?|γ1|γ2|… | γm和 A'→β1|β2|…|βn 例1：（显式） G[S]：S→aSb|aS|ε
解：提取左公共因子：S→aS(b|ε)|ε，引进新非终结符A得：S→aSA|ε和A→b|ε 例2：（隐式）G[A]：A→ad|Bc B→aA|bB 解：作变换：A→ad|(aA|bB)c即 A→ad|aAc|bBc， 提取左公共因子得： A→a(d|Ac)|bBc引进新非终结符A?得G?[A]：A→aA?|bBc A?→d|Ac B→aA|bB。 显然，改造后的G?[A]为LL(1)文法。因为：SELECT( A→aA?) ∩ SELECT( A→bBc)=φ， SELECT(A?→d) ∩ SELECT(A?→Ac)=φ， SELECT(B→aA) ∩ SELECT(B→bB)=φ。 3、变换后的压缩
通过提取左公共因子和引进新非终结符，作变换后，可能使原来某些规则无用，必须消除掉。
例3： 对G[S]：S→aSd|Ac A→aS|b
解：通过提取左公共因子和引进新非终结符作等价变换后得：S→aSB|bc B → d|c A→aS|b。此时，A不可达，则以A为左部的规则必须消去。
二、消除左递归
1、左递归引发的问题
（1）无法根据左递归文法进行自顶向下的分析；
（2）产生回溯现象：例如文法G[S]：S→Sa|b对baa进行识别出现的问题； （3）递归分析时死循环，无法编递归子程序。 2、左递归的类型
（1）直接左递归 A → A β
（2）间接左递归 A → B β且 B → A α 其中A、B∈ＶN ， α、β∈Ｖ*。
三、左递归的消除
1、直接左递归的消除方法
将A→Aα|β替换为：A→βA?和 A? →αA?｜ε 例：表达式文法
E → E + T｜T T → T * F｜F F → ( E )｜i
消除直接左递归后为：
E→ T E? E?→ + T E?|ε T→ F T? T?→* F T?｜ε F→
( E )｜i
2、间接左递归的消除
先将间接左递归化为直接左递归，再消除。 例：G[S]：S→Ac|c A→Bb|b B→Sa|a (1)将B的定义代入A产生式得： A→Sab|ab|b (2)将A的定义代入S产生式得： S→Sabc|abc|bc|c
(3)消除直接左递归：S→abcS?|bcS?|cS? S?→abcS?|ε (4)删除“多余的”产生式：A→Sab|ab|b和B→Sa|a (5)结果G[S]： S→abcS?|bcS?|cS? S?→abcS?|ε 3、消除左递归的一般方法
将产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βn用产生式组A→β1 B|β2 B |…|βnB，B→α1 B|α2 B |…|αn B|ε代换。其中：B为新变量，相当于A?。 4、消除左递归算法描述
若非终结符排序为A1，A2....An，则：
for(i=1;i<=n;i++) { for(j=1;j<=i-1;j++) {
若Aj所有产生式为Aj→α1|α2...|αk， 则替换形如Ai→Ajβ的产生式中Aj，变为形如Ai→α1 β |α2 β...|αk β的产生式。即化间接左递归为直接左递归。 }消除Ai中一切直接左递归。 }删除无用规则。
例：G[S]：S→Qc |c Q→Rb |b R→Sa |a
解：不妨设非终结符排序为S、Q、R(非终结符排序交换时，得不同文法，但各文法相互等价)。
(1)将S产生式代入R产生式中： R→ Qca|ca|a
(2)将Q产生式代入R产生式中得：R→Rbca|bca|ca|a (3)消除左递归得： R→(bca|ca|a)M和 M→bcaM|ε
(4)删除多余的产生式，结果为G[S]： R→(bca|ca|a)M M→bcaM|ε 同样，按R、Q、S排列可有：S→(abc|bc|c)M M→abcM|ε 和按R、S、Q排列有：Q→(cab|ab|b)M M→cabM|ε
5.4确定的自顶向下分析法
常用的确定的自顶向下分析法有递归下降分析法（递归子程序法）和预测分析方法。
5.4.1递归子程序法
一、基本实现思想
对应文法中的第一个非终结符编写一个递归下过程，每个过程的功能是识别由该非终结符推出的串，当某个非终结符的规则有多条时能够按LL(1)形式唯一确定候选规则进行推导。
二、采用数据结构
递归子程序法对每个过程可能存在直接或间接调用，通常需要在入口时需要保留某些信息，出口时恢复。常用先进后出栈来处理。
三、用递归子程序法构造语法分析程序过程
(1)改造文法：消除二义性、消除左递归、提取左因子； (2)求每个候选式的FIRST集和变量的FOLLOW集；
(3)检查是不是 LL((1)文法。若不是 LL(1)，说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”。 (4)按照 LL((1)文法画语法图； (5)化简语法图；
(6)按照语法图，为每个非终结符设置一个子程序。 事实上，如果有一个恰当的文法，可以直接根据每个语法变量的产生式设计相应的程序。
四、优缺点分析