自上而下语法分析.ppt

自上而下 语法分析 编 译 技 术 之 四 主讲 鲁 斌 1 v高级语言的语法结构适合用上下无关文法描述， 因此，我们将上下文无关文法作为语法分析的基 础 v本章和下一章，我们将介绍编译程序构造中的一 些典型的语法分析方法 2 1 语法分析器功能 v语法分析是编译过程的核心部分。它的任务是在词法分析 识别出单词符号串的基础上，分析并判定程序的语法结构 是否符合语法规则 v下图表明了语法分析器在编译程序中的地位 v按照语法分析树的建立方法，我们可以粗略地把语法分析 方法分为两类：一类是自上而下分析法，另一类为自下而 上分析法 源程序词法分析器 单词符号 取下一 单词符号 语法分析器 语法 分析树 后续部分 符 号 表 3 例：自顶向下构造最左推导（aabbaa) SaASa A SbA SS ba A S aS bSA a a b a aSbAS aabAS aabbaS aabbaa aAS S 4 2 自上而下分析面临的问题 v自上而下分析的一般方法：对任何输入串，用一 切可能的方法从文法开始符号（根结）出发，自 上而下地为输入串建立一棵语法树，或寻找一个 最左推导 v这种分析过程本质上是一种试探过程，是反复使 用不同产生式谋求匹配输入串的过程 5 v例4.1：假定有文法(4.1) SxAy A*|* 分析输入串x*y（记为）。 S x A y S x A y * * * S x A y (a)(b)(c) 6 v由上例看到，自上而下分析法存在许多困难和缺 点 n文法的左递归性PP使分析陷入无限循环 n回溯的不确定性，要求我们将已经完成工作推倒重来 n虚假匹配问题 n难于知道出错位置 n效率低，代价高，实践价值不大 v因此，为解决这些问题我们要消除左递归和回溯 + 7 3 LL(1) 分析法 3.1 左递归的消除 3.2 消除回溯、提左因子 3.3 LL（1）分析条件 8 3.1 左递归的消除 v一般而言，假定P关于的全部产生式是 PP1| P2| Pm| 1| 2 | | n 其中，每个都不等于，而每个都不以P开头， 那么，消除P的直接左递归性就是把这些规则改写 成： P | 1 P| 2 P| n P P1P| 2P| | mP| 9 v例4.2：文法 EE+T|T TT*F|F F(E)|i 消去直接左递归： ETE E+TE| TFT （4.2） T*FT| F(E)|i v直接左递归和非直接左递归的消除方法均在必须掌握之列 10 v若一个文法不含回路（PP），也不含以为右 部的产生式，则消除一切左递归的算法是： v把文法G的所有非终结符排序：P1, P2, , Pn vFOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k 其中Pj1|2|k是关于Pj的所有规则； 消除关于Pi规则的直接左递归性 END v化简上述文法 * 11 例4.3：考虑文法：SQc|c Q Rb|b R Sa|a 消除左递归。 解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入 到Q中有关的候选式： Q Sab|ab|b 现在Q同样不含直接左递归，把它带入S的有关候选式： S Sabc|abc|bc|c 经消除S的直接左递归后我们们得到整个文法 S abcS|bcS|cS S abcS| Q Sab|ab|b R Sa|a 由于关于Q,R的规则式多余的则可化简得到： S abcS|bcS|cS SabcS| 12 3.2 消除回溯、提左因子 v令G是一个不含左递归的文法，对G 的所有的非 终结符号的每个候选定义它的终结首符集 FIRST()为： FIRST()=a| *a,aVT v若* ，则规定 FIRST()。 换句话说 FIRST()是的所有可能推导的开头终结符或可 能的 13 v如果非终结符A 的所有候选首符集两两不相交， 即A的任何两个不同的候选i和j FIRST(i) FIRST(j) = 那么，当要求A匹配输入串时，A 就能根据它所 面临的第一个输入符号a，准确地指派某个候选前 去执行任务。这个候选就是那个终结首符集含a 的 14 v如何把一个文法改造成任何终结首符集的所有候选首符集 两两不相交呢？其办法是提取公共左因子 v假定关于A 的规则是 A1| 2| |n| 1| 2| |m （其中每个不以开头） 那末，可以把这些规则改写成： A A| 1| 2| |m A 1 | 2 | | n 15 例：有产生式 B bBcA|b 由于FIRST(bBcA) FIRST(b) =b ，则需要 提取公共左因子，将产生式改写成： B bC C BcA| 16 3.3 LL（1）分析条件 v问题 例4.4：考虑文法4.2，对输入串i+i进行自上而下分析 E F E T T (b) i+i IP i+i IP (a) ET E i+i IP (c) F T T E E i E F E T T (d) i+i IP i E i+i F E IP T T (e) i + E T i FT ETE E+TE| TFT T*FT| F(E)|i 17 v假定S是文法G开始符号，对任何非终结符A定义 ： FOLLOW(A) = a | S* Aa, aVT v若S* A， 则规定# FOLLOW(A). 也就是说 ，FOLLOW(A)是所有句型中出现在紧接A之后的 终结符或# v因此，当非终结符A面临输入符号a，且a不属于A 的任意候选首符集但A的某个候选首符集包含时 ，只有当aFOLLOW(A)，才可能允许A自动匹 配 18 v判断某给定文法是否为LL(1)文法其条件为： v文法不含左递归 v对于文法中每个非终结符A的各个产生式的候选首符集 两两不相交。即，若 A 1 | 2 | n 则： FIRST(i) FIRST(j) = （i j ) v对文法中每一个终结符A，若它存在某个候选首符集包 含，则 FIRST(A) FLLOW(A)= v一个文法若满足以上条件，则称该文法G为LL(1) 文法 19 v对于LL(1)文法，可以对其输入串进行有效的无回 溯的自上而下分析。假设要用非终结符A匹配，输 入符号a，A的所有产生式为 A 1 | 2 | n n若a FIRST(i)，则指派i执行匹配任务 n若a不属于任何一个候选首符集，则 u若FIRST(i)且aFLLOW(A)，则让A与自动匹配 u否则，a的出现是一种语法错误 20 4.4 递归下降分析程序构造 v当一个文法满足LL(1)条件时，我们就可以构造一 个不带回溯的自上而下分析程序，这个分析程序 由一组递归过程组成，每个过程对应文法的一个 非终结符。这样一个分析程序称为递归下降分析 器 21 v例如，文法4.2的每个非终结符所对应 的递归过程如下： PROCEDURE E; PROCEDURE T; BEGIN BEGIN T;E F;T END; END; PROCEDURE E; PROCEDURE T; IF SYM=+ THEN IF SYM=* THEN BEGIN BEGIN ADVANCE; ADVANCE; T;E F;T END; END; PROCEDURE F; IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR; ETE E+TE| TFT T*FT| F(E)|i 22 v在本节中我们对巴科斯范式进行了扩充： （1）用花括号表示闭包运算* ( 2）用0n表示可以任意重复0次至n 次， 00= （3）用方括号表示01，即表示的出现可有可无 v例如：“实数”可定义为 decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign+|- 23 v例4.5：文 法 EE+T|T TT*F|F F(E)|i 可表示成 ET+T TF*F F(E)|i T T+ （ E F F* T i E） F v用语法图表示： 24 PROCEDURE E; BEGIN T; WHILE SYM=+ DO BEGIN ADVANCE; T END END; PROCEDURE T; BEGIN F; WHILE SYM=* DO BEGIN ADVANCE; F END END; PROCEDURE F; 同前。 ET+T TF*F F(E)|i 25 5 预测分析程序 v使用高级语言的递归过程描述递归下降分析器， 只有当具有实现这种过程的编译系统时才有实际 意义 v实现LL(1)分析的另一种有效方式是使用一张分析 表和一个栈进行联合控制。我们现在介绍的预测 分析程序就是属于这种类型的LL(1)分析器 26 5.1预测分析程序工作过程 v预测分析表是一个MA, a形式的矩阵 v对于任何(X,a)，总控程序执行下述动作之一 n若X=a=#，则分析成功，停止 n若X=a#，则把X从STACK栈顶逐出，让a指向下一个输入符号 n若X是一个非终结符，则依据分析表M中的不同内容作不同处理 a# 输入串 总控程序 预测分析表M x# 输出 27 v预测分析器的总控程序： 置 ip指向 w#的第一个符号；令X为栈顶符号，a是 ip所指向的符号 BEGIN push(st,#); push(st,S); FLAG:=TRUE; WHILE FLAG DO BEGIN IF XVT THEN IF X=a THEN pop(st); ip:=ip+1 ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF Mx,a=XX1X2Xk THEN pop(st);push(st,Xk);push(st,X1) ELSE ERROR、 END OF WHILE; STOP END 28 i1 + i2 * i3 #输入 预测分析 控制程序 # E E T T F i E T + T F i ETE FTE i1TE i1E i1+TE i1+FTE i1+i2TE 栈 ETE E+TE| TFT T*FT| F(E) | i 29 例：输入串为i1+i2，利用分析表进行预测分析。 符号栈 输入串 MX,b 1 #E i1+i2# E TE 2 #ET i1+i2# T FT 3 #ETF i1+i2# F i 4 #ET i i1+i2# 匹配 5 # ET +i2# T 6 #E +i2# E +TE 7 #ET+ +i2# 匹配 8 # ET i2# T FT 9 #ETF i2# F i 10 #ETi i2# 匹配 11 #ET # T 12 #E # E 13 # # 接受 ETE E+TE| TFT T*FT| F(E) | i I+*()# ETETE E+TE TFTFT T*FT Fi(E) 30 v计算FIRST集 n若XV,则FIRST(X)=X n若XVN,且有产生式Xa，则把a加入到FIRST(X)中; 若X也是一条产生式,则把也加到FIRST(X)中 n若XY是一个产生式且YVN,则把FIRST(Y)中的所有 非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产 生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何 j,1j i-1, FIRST(Yj)都含有 (即Y1Y(i-1) =* ),则把FIRST(Yi)中的所有非元素都加到FIRST(X)中; 特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把 加到FRIST(X)中 5.2 预测分析表的构造 31 v求First(), =X1X2Xn n置FIRST()=FIRST(X1) n若对任何1ji-1, FIRST(Xj)，则把 FIRST(Xi)加入FIRST()中 n特别是,若所有的FIRST(Xj)均含有, 1jn，则把 加到FRIST()中 v显然，若= ，则FIRST()= 32 v计算FOLLOW集 n对于文法的开始符号S,置#于FOLLOW(S)中 n若 B是一个产生式,则把FIRST()加至 FOLLOW(B)中 n若B是一个产生式,或B是一个产生式而 =* (即FIRST()），则把FOLLOW（A）加至 FOLLOW（B）中 33 例4.7 对于文法 ETE E +TE| T FT T *FT| F (E)| i 我们构造每个非终结符的FIRST和FOLLOW集合 解：FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E) = +, FOLLOW(E) = ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T) = *, FOLLOW(T) =+ , ), # FIRST(F) = (, i FOLLOW(F) =*, +, ) , # 在这里我们要注意FOLLOW(F)的求解过程其中： v因为T FT，所以FIRST(T) =*应加入FOLLOW(F)中 v因为T ,所以将FOLLOW(T)=+, ), #加到FOLLOW(F)中 34 v构造分析表M的算法是： v对文法G的每个产生式A执行第二步和第三步； v对于每个终结符aFIRST()，把A加到MA,a 中； v若FIRST() ，则对任何的b FOLLOW(A)把 A加至MA,b中； v把所有无定义的MA,a标上“出错标志” v一个文法G的预测分析表M不含多重定义入口，当且仅 当该文法为LL(1)的 35 例4.8：构造文法4.2的分析表。 ETE FIRST(TE) = (, i E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T FT FIRST(FT) = (, i T *FT | FIRST(*FT)=* FOLLOW(T)=+,)， F (E) | i FIRST(E)=( FIRST(i)=i ETE E+TE| TFT T*FT| F(E) | i i+*()# ETETE E +TE TFTFT T *FT F i ( E ) 36 i+*()# ETETE E +TE TFTFT T *FT F i ( E ) 符号栈 #E #ET #ETF #ETi #ET #E #ET+ #ET #ETF #ETi #ET #ETF* #ETF #ETi #ET #E # 输入串 i+i*i# i+i*i# i+i*i# i+i*i# +i*i# +i*i# +i*i# i*i# i*i# i*i# *i# *i# i# i# # # # 产生式/动作 ETE TFT F i 匹配匹配 T E +TE 匹配匹配 T FT F i 匹配匹配 T *FT 匹配匹配 F i 匹配匹配 T E 接受接受 例：输入 i+i*i ETE E+TE| TFT T*FT| F(E) | i 37 v例4.9：已知文法GA为 AaABe|a BBb|d v试给出与GA等价的LL(1)文法GA v构造GA的预测分析表，并给出输入串aade#的分析过程 解： 文法GA不是LL(1)文法的原因是： n产生式AaABe|a，使得 FIRST(aABe)FIRST(a)=a n产生式BBb|d含有左递归 要构造与GA等价的LL(1)文法，就要消除上述两种问题 38 将AaABe|a修改为：AaC CABe| 将BBb|d修改为： BdB BbB| 因此得到文法GA： AaC BdB BbB| CABe| 求每一个非终结符的FIRST集： FIRST(A)=a FIRST(B)=d FIRST(B)=b, FIRST(C)=a, 求每一个非终结符的FOLLOW集： FOLLOW(A)=#FIRST(Be)=#, d FOLLOW(B)=FIRST(e)=e FOLLOW(B)=FOLLOW(B)=e FOLLOW(C)=FOLLOW(A)= #, d 对BbB|，有FIRST(B)FOLLOW(B)=b, e= 对CABe|，有FIRST(C)FOLLOW(C)= a, #, d= 而文法的其他产生式都只有一个非的右部，因而满足LL(1)文法的要 求，即分析过程中不会出现回溯。 所以文法GA就是所求的与原文法等价的LL(1)文法。 39 v构造GA的预测分析表 对AaC， FIRST(aC)=a, MA, a=” AaC” 对BdB， FIRST(dB)=d, MB, d=”BdB” 对BbB|， FIRST(bB)=b, MB, b=”BbB” FOLLOW(B)=e, MB, e=” B” 对CABe|， FIRST(ABe)=a, MC, a=”CABe” FOLLOW(C)=#, d, MC, #=”C”, MC, d=”C” 40 v所以得到的LL(1)分析表是： abde# AAaC B BdB B BbBB CCABe CC 41 v对输入串aade#的分析 过程如下： 步骤符号栈输入串 产生式/ 动作 1 #A aade#AaC 2 #Ca aade#匹配 3 #C ade#CABe 4 #eBA ade#AaC 5 #eBCa ade#匹配 6 #eBC de#C 7 #eB de#BdB 8 #eBd de#匹配 9 #eB e#B 10 #e e#匹配 11 # #接受 42 例题与习题解答 例1：试构造与下列文法GS等价的无左递归文法。 GS: SSa|Nb|c (1) N Sd|Ne|f (2) 解：以S,N为序,对于（1）我们引入新非终结符S 则： S NbS |cS 1 SaS| 2 将 S代入 （2） N Ne |NbSd |cSd |f 引入新非终结符N N cSdN |fN 3 N eN |bSdN | 4 43 例2：文法G的规则集为; P begin d : X end X d : X | sY Y : sY | 做出该文法LL(1)分析表。 解： 非终结符只有 P , X ,Y 只有FIRST(Y)含有，则需要求出 FOLLOW(Y)且 FOLLOW(Y) =FOLLOE(X)=end 则有LL(1)表： begin d : end s # P begin d : X end X d : X sY Y :sY 练 习 44 例3：给出语言L=1na0n1ma0m|n0, m=0 的LL(1)文法GS并 说明其理由。 解：观察句子,发现可分成两部分 1na0n 和 1ma0m两部分中符号 的个数n和m没有制约关系。则可改造成下列文法： S AB A 1A0 |1a0 B 1B0 |a 对于产生式 A 1A0 |1a0 两个候选式 FIRST(1A0)FIRST(1a0)=1 所以上边文法不是 LL(1)文法：需左提公因子，得到： S AB A 1C C A0 |a0 B 1B0 |a 此文法满足LL(1)文法的要求。 45 例4：文法GS： S(L) | a L L,S | S 请消除左递归，并构造LL(1)预测分析表，并说明对输入串(a，(a， a)的分析过程。 解：将所给文法消除左递归得G： S (L) | a L SL L ,SL | 根据文法G有： FIRST(S) =