编译原理：第五章语法分析2

1、 1. 什麽是LL(1)分析法？ 5.3.1 LL(1)分析法基本概念 5.3 LL(1)分析法 LL(1) 分析法的基本要点有三： 利用一个分析表，登记如何选择产生式的知识； 利用一个分析栈，记录分析过程； 此分析法要求文法必须是 LL(1)文法。 LL(1)分析法是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的 1）之意； LL(1)分析法又称预测分析法，与递归子程序法同属于自顶向下确定性语法分析方法; 2. LL(1)分析过程示例 G(Z)：Z-dAZ | bAc A-aA | 栈 当前符号 剩余序列 栈操作 选择推导产生式后，为什麽要逆序压栈? 当栈顶为A,当前单词为c

2、时，为什么选择 A ?讨论逆序压栈# c A# c# c A# c# c A b A aba c # 选择 ZbAcba c #匹配 bac # 选择AaAac #匹配 a c# 选择A c#匹配 c#正确结束 Z查分析表 对符号串： = bac # 的分析过程： d A Z # c b a分析表： 设有文法G(Z), # 栈底标记和结束标记;#栈结束： 若 栈顶符=a 且 当前符为a； 则 pop,NEXT(w);# Z 开始：栈 ; NEXT(w)；当前符 w= # 重复执行 、 ，直到栈中只剩 # 为止： 即：栈调整：# a# 即：栈调整：# A# a 3. LL(1)分析法算法概要 若

3、 栈顶符=A 且 当前符 w=a 且 有产生式： Aa， 则 POP,PUSH(a)R ; 逆序压栈! 否则，错误处理！5.3.2 LL(1)文法及其判定1. 首符号集合、后继符集合与选择符集合 设 G(Z)=(VN, VT, Z, P)，A- P，则 first() , first()follow(A), select(A-)=*【注】 (可空), (不可空)； 若 = 则 first()= ； 设 #为输入串的结束符，则 #follow(Z); =*first()= t| t，tVT =*follow(A)= t| Z At，tVT =*【注】 求 follow(A) 要点： 查所有右部含

4、有A的产生式: B - A 若 不空时 , 则 first()follow(A) ； 若 取空时 , 则 follow(B)follow(A) ； 若 = 时 , 则 follow(B)follow(A)。select()= first(dAZ)=d select()= first(bcA)=bselect()= first(aA)=a select()= first()follow(A)= b,d，# 即： B - AG(Z)： Z - dAZ | bcA A - aA | 【例5.4】 求文法产生式的选择集合:则有： 产生式序号 【定义】 LL(1)文法是指文法中，具有相同左部的各产生式，

5、其选择集合不相交。 select()= d ；2. LL(1)文法及其判定 LL(1)文法可确保 递归子程序法 和 LL(1)分析法 的正确运用。【例5.5】 G(Z)： Z - dAZ | bcA A - aA | select()= bselect()= a ；即： db= 又 ab,d,#= select()= b,d，# G(Z) 是 LL(1)文法。 LL(1)分析法示例：【例5.6】 G(Z)：Z - Z b | a 【注】上述文法可进行等价变换，消除左递归得： select()= a select()= a 选择集合相交 具有左递归的文法，一定不是LL(1)文法！ G(Z)是LL

6、(1)文法，可以用 LL(1)分析法。 select()= b select()= # 选择集合不相交G(Z)： Z - aA , A - bA | 列： 终结符 | #5.3.3 LL(1)分析器设计(实现) 应用时，可用下列函数查表，获取相应产生式： L(栈顶符，当前符）= 产生式序号【结构设计】. LL(1)分析表的构造: LL(1)控制程序+LL(1)分析表LL(1)分析表是存储文法选择集合的知识表。 行： 非终结符表项：产生式序号 Z # a A d A Z # c b a如 G(Z)：Z - aAb | AcA select()=a; 【算法设计】 A - dA | i则 L( A

7、 , a ):=A - i 求文法选择集合，确认 LL(1)文法； 依次取产生式：select()=d;select()=c,d ; select()= b,c,#;是 LL(1)文法,LL(1)分析表：不相交不相交若 a select( ) i NEXT(w)ynerrnynnerr PUSH(#),PUSH(Z) POP(x)y开始结束xVTnerryxVNw = #x = wy查LL(1)分析表: L( x ,w )= ? 空？. LL(1)分析法控制程序：PUSH ( iR ）把产生式 i 右部逆序压栈把栈顶符弹入到变量x中! LL(1)分析法综合示例：【例5.7】 G(E)： E -

8、 T | E 1 T T - F | T 2 F F - i | ( E ) 此文法含左递归，不是LL(1)文法;经文法变换（消除左递归）后可得：G(E): E - T E E- 1 T E | T - F T T- 2 F T | F - i | ( E ) 其中： 1( + ,- ) , 2 ( * ,/ ) 这是LL(1)文法吗?select()=first(TE)= i,( 1.求G(E) 的选择集合： 三对选择集合两两不相交，G(E): E - T E E- 1 T E | T - F T T- 2 F T | F - i | ( E ) E -E-T -T-F -select()=

9、first(1TE)= 1 select()=follow(E)= ),# select()=first(FT)= i,( select()=first(2FT)= 2 select()=follow(T)= 1 ,),# select()=first(i)= i select()=first(E)= ( G(E)是 LL(1) 文法。(接上页) 2.构造 LL(1) 分析表： 花括号内是求得的选择集合！ F T T E E ) ( # 2 1 iT- 2 FT 2 | 1,),# F - i i | (E) ( E - TE i,( E- 1 TE 1| ),# T - FT i,( G(E

10、):(接上页) 符号串 a+b# 的LL(1)分析过程：查分析表： 操 作剩余序列 w x 分析栈# ( + 匹配成功 ) b # + 1# E T 1 : PUSH(ET1) b # + E# E : PUSH ( ) + b # + T# E T : PUSH(i) + b # a F T F ( a 匹配成功 ) + b # a i i : PUSH(TF) + b # a T E T ：PUSH(ET) a + b # a E# E : PUSH(TF) b # b T# E T ok # # : PUSH ( ) # # T # E T : PUSH ( ) # E# E ( b 匹配成功) # b i i : PUSH（i） # b F T F# E# E T# E # E T练习题：【