[电脑基础知识]编译原理 - 陈火旺版 - 第四章ppt课件

1、编译方法中国人民大学信息学院陈文萍第四章 语法分析自上而下分析 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1) 分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL(1) 分析中的错误处置4.1 语法分析器的功能 语法分析器的位置 分类 自上而下分析 自下而上分析词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析树4.2 自上而下分析 定义：也称面向目的的分析方法，从文法的开场符号出发企图推导出与输入的单词串完全相匹配的句子。 主旨：对任何输入串，试图用一切能够的方法，从文法开场符号着手，自上而下地为输入串构造一棵

2、语法树。本质上是一个试探过程，反复运用不同的产生式谋求匹配输入串的过程。 自上而下分析的问题1 左递归 例：例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子 按照自上而下的分析思想，选用产生式(1)来推导SSa， 语法树末端结点最左符号为非终结符，所以选用1继续 推导SSaSaa 此时语法树末端结点最左符号为非终结符，选用1 继续推导SSaSaa Saaa 试图用S匹配输入串时，出现：在没有识别任何输入符号的情况下，又得重新要求S去进展新的匹配，分析过程堕入无限循环自上而下分析的问题2 回溯 例：GS: SxAy， Aaba 假设当前输入串为xay，首先构造的推导SxA

3、y 匹配 进一步推导对A可选择Aab交换，得SxAy xaby xay xaby 匹配 xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的交换重新选用下一个产生式Aa进展试探， SxAy xay输入串中当前符a得到匹配，指针向前挪动到y，与语法树中y匹配，匹配胜利。 由于一样左部的产生式的右部开场符号一样而引起回溯。自上而下分析的问题3 分析过程中，匹配胜利能够是暂时的。 最终分析不胜利，很难知道输入串中出错确实切位置。 带回溯，效率低，代价高4.3 LL(1) 分析法 左递归的消除 消除回溯 LL(1) 分析条件直接左递归的消除左递归：一个文法是含有左递归的，假设

4、存在非终结符P，P = P形如：P P|，其中不为 ，不以P打头 消除直接左递归改写为：P P，PP| 普通来说，假设P P1|P2|Pm|1|2|n，i不为 ，i不以P打头，消除直接左递归就把规那么改写为： P 1P|2P|nP P 1P|2P|mP| 例：E E+T|T，T T*F|F，F (E)| i 消除直接左递归后变为： E TEE +TE| T FTT *FT| F (E)|i文法左递归的消除 消除一个文法左递归：对文法的要求 无回路( ) 不含以为右部的产生式 消除左递归算法： 1以某种顺序将文法非终结符陈列P1 ,P2 Pn 2 for i:=1 to n dobegin fo

5、r j:=1 to i-1 do 用Pi-1r| 2r| k r替代形如Pi- Pjr的规那么 其中Pj- 1| 2| k是关于Pj的全部产生式; 消除Pi规那么的直接左递归; end 3化简由2得到的文法PP左递归的消除 例，文法S Qc|c,QRb|b, RSa|a 1,非终结符排序为：S,Q,R 2,交换规那么 对于S，无需交换，S Qc|c 对于Q，无需交换，Q Rb|b 关于R，交换为，R Rbca|bca|ca|a,消除直接左递归为 R bcaR|caR|aR，R bcaR| 非终结符的顺序不同，文法的方式能够不同，但都是等价的消除回溯 不回溯，对文法的要求 设G是一个不含左递归的

6、文法，对G的一切非终结符的每个候选，它的终结首符集FIRST()为 FIRST()=a| =* a,aVT，假设 =* 那么规定FIRST 假设非终结符A的一切候选首符集两两不相交，即A的任何两个不同候选和，FIRSTFIRST()=，那么可消除回溯 改造文法的方法：提左公因子 将产生式 1|n|1|m 变换为： B|1|m B 1|nLL(1) 分析条件 例如：文法：E TE，E +TE| ，T FT，T *FT| ，F (E)|i输入串i+i，语法分析树FIRST(TE)=，i FIRST(+TE)=+FIRST(FT)=，iFIRST(*FT)=*FIRST(E)=(FIRST(i)=i

7、 ETEiTE+TFFTiLL(1) 分析条件 S是文法G的开场符号，对G的任何非终结，定义FOLLOWA=aS =* Aa且a VT , 假设S =* A , 那么#FOLLOW(A) 一个文法G是LL1的，当且仅当对于G的每一个非终结符的任何两个不同产生式 ，下面的条件成立： 1.文法不含左递归。 2.FIRSTFIRST()=,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字。 3.假假设 =* ，那么，FIRST)FOLLOWA. 也就是， 假设 =* .那么所能推出的串的首符号不应在FOLLOW(A中。LL(1) 分析条件 文法是LL(1)的 第一个L 从左到右扫

8、描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号4.4 递归下降分析程序构造 递归分析器：不带回溯的自上而下的分析程序 例：文法：E TE，E +TE| ，T FT，T *FT| ，F (E)|i递归子程序为：PROCEDURE E;BEGIN T;EEND;PROCEDURE E;IF SYM=+ THENBEGIN ADVANCE; T;E END;4.4 递归下降分析程序构造PROCEDURE T;BEGINF;T END;PROCEDURE T;IF SYM=* THENBEGINADVANCE; F;T END;PROCEDURE F;IF SYM=i THEN ADVA

9、NCEELSEIF SYM=( THEN BEGINADVANCE; E;IF SYM=) THEN ADVANCEELSE ERROR ENDELSE ERROR;4.4 递归下降分析程序构造 扩展的巴科斯范式 用a表示闭包运算a* 用 表示a可恣意反复0次到n次， 用a表示 ，即a的出现可有可无 例如，文法 E T|E+T，T F|T*F，F (E)|I可以表示成 E T+T，T F*F，F (E)|IPROCEDURE E; BEGINT;WHILE SYM=+ DO BEGIN ADVANCE; T END END;000aa0na01a4.4 递归下降分析程序构造PROCEDURE

10、F;IF SYM=* THEN ADVANCEELSEIF SYM=( THEN BEGINADVANCE; E;IF SYM=) THEN ADVANCEELSE ERROR ENDELSE ERROR;PROCEDURE T;BEGINF;WHILE SYM=* DO BEGIN ADVANCE; F; END END;4.4 LL(1)分析器 LL(1)分析器的模型分析器的模型 a + b #XYZ.#LL(1)分析算法LL(1)分析表M输入缓冲区输入缓冲区分析栈分析栈输出输出LL(1)分析器 分析要件 输入缓冲区：存放要分析的符号串，在串的末尾加符号#表示输入终了。 预测分析表：看作矩

11、阵，存放文法中非终结符A和终结符a的关系。矩阵元素MA,a 表示A对于输入符号a所采用的候选。终了标志符#作为一个终结符号。 栈：分析过程中，存放当前句型中尚待分析的文法符号，包括终结符号和非终结符号。栈底用#标志终了。初始化时，把#和文法的开场符号放在栈顶。LL(1)预测分析表i+*()#E(1)(1)E(2)(3) (3)T(4)(4)T(6) (5)(6) (6)F(8)(7)例：G E: (1) E TE (2) E +TE (3) E T FT (5) T *FT (6) T (7) F (E) (8) F i预测分析表的构造 计算FIRST集合的方法 1.假设XV,那么FIRST(

12、X)=X 2.假设XVN,且有产生式Xa，那么把a参与到FIRST(X)中;假设X也是一条产生式,那么把也加到FIRST(X)中. 3.假设XY是一个产生式且YVN,那么把FIRST(Y)中的一切非元素都加到FIRST(X)中;假设X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) =* ),那么把FIRST(Yj)中的一切非元素都加到FIRST(X)中;特别是,假设一切的FIRST(Yj , j=1,2,K)均含有,那么把加到FRIST(X)中.预测分析表的构造 计算计算FOLLOWFOLL

13、OW集集 1.1.对于文法的开场符号对于文法的开场符号S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ; 2.2.假设假设 B B是一个产生式是一个产生式, ,那么把那么把 FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ; 3.3.假设假设 B B是一个产生式是一个产生式, ,或或BB是一个产生式而是一个产生式而 = =* * ( (即即FIRST()FIRST()，那么把，那么把FOLLOWFOLLOWA A加加至至FOLLOWFOLLOWB B中中预测分析表的构造 例：文法G E: (1) E TE (2) E +TE (3) E

14、(4) T FT (5) T *FT (6) T (7) F (E) (8) F a 非终结符的FIRST集合：FIRST(E)=(,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a非终结符的FOLLOW集合：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，# FOLLOW(F)=*,，),# 预测分析表构造算法预测分析表构造算法1.对文法G的每个产生式 执行第二步和第三步；2.对每个终结符aFIRST()，把 加至A,a中，3.假设 FIRST()，那么对任何bFOLLOW(A)把 加至A,b中

15、，4.把一切无定义的A,a标上“出错标志。可以证明，一个文法G的预测分析表不含多 重入口，当且仅当该文法是LL(1)的预测分析程序预测分析程序算法：首先把#然后把文法开场符号推入栈；把第一个输入符号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,a=X X1X2.XK THEN 把XK，X K-1,.,X1一一推进栈 EL

16、SEERROR END OF WHILE; STOP/*分析胜利，过程终了*预测分析程序分析步骤栈内容 栈顶符号 当前输入 余留串 MX,a 1 #E E i +i# E TE2 #ET T i +i# T FT3 #ETF F i +i# F i4 #ETi i i +i#5 # ET T + i# T 6 #E E + i# E +TE7 #ET+ + + i#8 # ET T i # T FT 9 #ETF F i # F i10 #ETi i i #11 #ET T # T 12 #E E # E 13 # # #4.6 LL(1)分析中的错误处置 发现错误 栈顶的终结符与当前输入符不匹配 非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空 应急恢复战略 跳过输入串中的一些符号直至遇到“同步符号为止。4.6 LL(1)分析中的错误处置 同步符号集的选择 把FOLLOW(A)中的一切符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号，把A从栈中弹出，可使分析继续 错误处置 假设MA,a为空，跳过输入符号a 假设MA,a为同步符号，弹出栈顶的非终结符 栈顶终结符与输入符号不匹配，弹出栈顶的终结符4.6 LL(1)分析中的错误处置文法G E: (1)