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