《电脑基础知识编译原理陈火旺版课件》由会员分享，可在线阅读，更多相关《电脑基础知识编译原理陈火旺版课件（32页珍藏版）》请在金锄头文库上搜索。
1、编译方法中国人民大学信息学院陈文萍1电脑基础知识编译原理 陈火旺版 第四章 语法分析自上而下分析4.1 语法分析器的功能4.2 自上而下分析面临的问题4.3 LL(1) 分析法4.4 递归下降分析程序构造4.5 预测分析程序4.6 LL(1) 分析中的错误处理2电脑基础知识编译原理 陈火旺版 4.1 语法分析器的功能语法分析器的地位分类自上而下分析自下而上分析词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析树3电脑基础知识编译原理 陈火旺版 4.2 自上而下分析定义：也称面向目标的分析方法，从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子。主旨：对任
2、何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树。本质上是一个试探过程，反复使用不同的产生式谋求匹配输入串的过程。4电脑基础知识编译原理 陈火旺版 自上而下分析的问题（1）左递归例：例文法G0S:(1) SSa(2) Sb分析baa是不是文法的句子按照自上而下的分析思想，选用产生式(1)来推导SSa，语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa此时语法树末端结点最左符号为非终结符，选用（1）继续推导SSaSaa Saaa 试图用S匹配输入串时，出现：在没有识别任何输入符号的情况下，又得重新要求S去进行新的匹配，分析过程陷入无限循环5电
3、脑基础知识编译原理 陈火旺版 自上而下分析的问题（2）回溯例：GS: SxAy， Aaba 若当前输入串为xay，首先构造的推导SxAy 匹配 进一步推导对A可选择Aab替换，得SxAy xaby xay xaby 匹配 xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探， SxAy xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。由于相同左部的产生式的右部开始符号相同而引起回溯。6电脑基础知识编译原理 陈火旺版 自上而下分析的问题（3）分析过程中，匹
4、配成功可能是暂时的。最终分析不成功，很难知道输入串中出错的确切位置。带回溯，效率低，代价高7电脑基础知识编译原理 陈火旺版 4.3 LL(1) 分析法左递归的消除消除回溯LL(1) 分析条件8电脑基础知识编译原理 陈火旺版 直接左递归的消除左递归：一个文法是含有左递归的，如果存在非终结符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 消除直接左递归后变
5、为： E TEE +TE| T FTT *FT| F (E)|i9电脑基础知识编译原理 陈火旺版 文法左递归的消除消除一个文法左递归：对文法的要求无回路( )不含以为右部的产生式消除左递归算法：（1）以某种顺序将文法非终结符排列P1 ,P2 Pn （2） for i:=1 to n dobegin for j:=1 to i-1 do 用Pi-1r| 2r| k r替代形如Pi- Pjr的规则 其中Pj- 1| 2| k是关于Pj的全部产生式; 消除Pi规则的直接左递归; end （3）化简由2得到的文法10电脑基础知识编译原理 陈火旺版 左递归的消除例，文法S Qc|c,QRb|b, RSa
6、|a1,非终结符排序为：S,Q,R2,替换规则对于S，无需替换，S Qc|c对于Q，无需替换，Q Rb|b关于R，替换为，R Rbca|bca|ca|a,消除直接左递归为 R bcaR|caR|aR，R bcaR| 非终结符的顺序不同，文法的形式可能不同，但都是等价的11电脑基础知识编译原理 陈火旺版 消除回溯不回溯，对文法的要求设G是一个不含左递归的文法，对G的所有非终结符的每个候选，它的终结首符集FIRST()为 FIRST()=a| =* a,aVT，若 =* 则规定FIRST（）若非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选和，FIRST（）FIRST()=，则可消除回
7、溯改造文法的方法：提左公因子 将产生式 1|n|1|m 变换为： B|1|m B 1|n12电脑基础知识编译原理 陈火旺版 LL(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 ETEiTE+TFFTi13电脑基础知识编译原理 陈火旺版 LL(1) 分析条件S是文法G的开始符号，对G的任何非终结，定义FOLLOW（A）=aS =* Aa且a VT , 若S =* A , 则#FOLLO
8、W(A)一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式 ，下面的条件成立： 1.文法不含左递归。 2.FIRST（）FIRST()=,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字。 3.假若 =* ，那么，FIRST（)FOLLOW（A）. 也就是， 若 =* .则所能推出的串的首符号不应在FOLLOW(A）中。14电脑基础知识编译原理 陈火旺版 LL(1) 分析条件文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号15电脑基础知识编译原理 陈火旺版 4.4 递归下降分析程序构造递归分析器：
9、不带回溯的自上而下的分析程序例：文法：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;16电脑基础知识编译原理 陈火旺版 4.4 递归下降分析程序构造PROCEDURE T;BEGINF;T END;PROCEDURE T;IF SYM=* THENBEGINADVANCE; F;T END;PROCEDURE F;IF SYM=i THEN ADVANCEELSEIF SYM=( THEN BEGINADVANCE
10、; E;IF SYM=) THEN ADVANCEELSE ERROR ENDELSE ERROR;17电脑基础知识编译原理 陈火旺版 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;18电脑基础知识编译原理 陈火旺版 4.4 递归下降分析程序构造PROCEDURE F;IF SYM=* THE
11、N ADVANCEELSEIF SYM=( THEN BEGINADVANCE; E;IF SYM=) THEN ADVANCEELSE ERROR ENDELSE ERROR;PROCEDURE T;BEGINF;WHILE SYM=* DO BEGIN ADVANCE; F; END END;19电脑基础知识编译原理 陈火旺版 4.4 LL(1)分析器LL(1)分析器的模型分析器的模型 a + b #XYZ.#LL(1)分析算法LL(1)分析表M输入缓冲区输入缓冲区分析栈分析栈输出输出20电脑基础知识编译原理 陈火旺版 LL(1)分析器分析要件输入缓冲区：存放要分析的符号串，在串的末尾加符
12、号#表示输入结束。预测分析表：看作矩阵，存放文法中非终结符A和终结符a的关系。矩阵元素MA,a 表示A对于输入符号a所采用的候选。结束标记符#作为一个终结符号。栈：分析过程中，存放当前句型中尚待分析的文法符号，包括终结符号和非终结符号。栈底用#标记结束。初始化时，把#和文法的开始符号放在栈顶。21电脑基础知识编译原理 陈火旺版 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 (4)T FT (5) T *FT (6) T (7) F (E) (8) F
13、i22电脑基础知识编译原理 陈火旺版 预测分析表的构造计算FIRST集合的方法1.若XV,则FIRST(X)=X2.若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)均
14、含有,则把加到FRIST(X)中.23电脑基础知识编译原理 陈火旺版 预测分析表的构造计算计算FOLLOWFOLLOW集集1.对于文法的开始符号S,置#于FOLLOW(S) 中;2.若 B是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若 B是一个产生式,或B是一个产生式而 =* (即FIRST()），则把FOLLOW（A）加至FOLLOW（B）中24电脑基础知识编译原理 陈火旺版 预测分析表的构造例：文法G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 非终结符的FIRST集合：F
15、IRST(E)=(,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a非终结符的FOLLOW集合：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，# FOLLOW(F)=*,，),# 25电脑基础知识编译原理 陈火旺版 预测分析表构造算法预测分析表构造算法1.对文法G的每个产生式 执行第二步和第三步；2.对每个终结符aFIRST()，把 加至A,a中，3.若 FIRST()，则对任何bFOLLOW(A)把 加至A,b中，4.把所有无定义的A,a标上“出错标志”。可以证明，一个文法G的预测分析表不含多
16、 重入口，当且仅当该文法是LL(1)的26电脑基础知识编译原理 陈火旺版 预测分析程序预测分析程序算法：首先把#然后把文法开始符号推入栈；把第一个输入符号读进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一一推进栈 ELSEERROR END OF WHILE;
17、STOP/*分析成功，过程完毕*27电脑基础知识编译原理 陈火旺版 预测分析程序分析步骤栈内容 栈顶符号 当前输入 余留串 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 # # #28电脑基础知识编译原理 陈火旺版 4.6 LL(1)分析中的错误处理发现错误栈
18、顶的终结符与当前输入符不匹配非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空应急恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。29电脑基础知识编译原理 陈火旺版 4.6 LL(1)分析中的错误处理同步符号集的选择把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续错误处理若MA,a为空，跳过输入符号a若MA,a为同步符号，弹出栈顶的非终结符栈顶终结符与输入符号不匹配，弹出栈顶的终结符30电脑基础知识编译原理 陈火旺版 4.6 LL(1)分析中的错误处理文法G E: (1) E TE (2) E +TE (3) E (4) T FT(5) T *FT (6) T (7) F (E)(8) F ii+*()#E(1)(1)syn synE(2)(3)(3)T(4)syn(4)syn synT(6)(5)(6)(6)F(8)syn syn (7)syn syn31电脑基础知识编译原理 陈火旺版 小结语法分析回顾与概述与词法分析的关系分类：自上而下，自下而上自上而下分析方法LL(1)分析法LL(1)文法条件左递归的消除回朔的消除FIRST集与FLLOW集的判定LL(1)预测分析程序预测分析表的构造分析算法错误处理32电脑基础知识编译原理 陈火旺版
