编译技术语法分析

1、编译原理,第四章 语法分析自上而下分析,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表 格 管 理,出 错 处 理,目标代码生成器,第四章 语法分析自上而下分析,本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。,上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN

2、)* 开始符S至少必须在某个产生式的左部出现一次。,例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成： E i E E+E E E*E E (E),定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (VT VN)* 。 如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 例：对文法(1) E (E) (E+E) (i+E) (i+i),4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(程序)。,.,语法分析的方法

3、： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约,G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻

4、找匹配的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。,4.2.1 自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,例4.1 假定有文法G(S): (1) SxAy (2) A*|* 分析输入串x*

5、y(记为)。,例 假定有文法GS: SSb Sa L=abn | n1 W=abbb S S b S b,当某个非终结符有多个产生式候选时，可能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,含有左递归的文法将使自上而下的分析陷入无限循环。,4.2.2 左递归的消除、回溯的消除,构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯,4.2.2 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 PP | 其中不以P开头。 我们

6、可以把P的规则等价地改写为如下的非直接左递归形式： PP PP|,左递归变右递归,一般而言，假定P关于的全部产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P1P | 2P | | nP P1P | 2P | | mP | ,左递归变右递归,例 文法G(E): EET | T TT*F | F F(E) | i 经消去直接左递归后变成： ETE E+TE | TFT T*FT | F(E) | i,(4.2),PP1 | P2 | | Pm | 1 | 2|n P1P | 2P | | nP

7、P1P | 2P | | mP | ,例如文法G(S): SQc|c QRb|b RSa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc,一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。,消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k ; (其中Pj1|2|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号

8、出发永远无法到达的非终结符的产生规则。,例 考虑文法G(S) SQc|c QRb|b RSa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规则变为 QSab | ab | b,例 考虑文法G(S) SQc|c QRb|b RSa|a 令它的非终结符的排序为R、Q、S。 Q的规则变为 QSab | ab | b 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 SSabc | abc | bc | c,例 考虑文法G(S) SQc|c QRb|b RSa|a S变成 SSabc | abc | bc | c 消除S的直接左递归后：

9、SabcS | bcS | cS SabcS | QSab |ab | b RSa|a,例 考虑文法G(S) SQc|c QRb|b RSa|a 消除S的直接左递归后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a 关于Q和R的规则已是多余的，化简为： SabcS | bcS | cS SabcS | (4.4),注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。 例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： SQc | c QRb | b RbcaR | caR |

10、a R (4.5) R bca R | 文法(4.4)和(4.5)的等价性是显然的。,4.2.4 消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 A 1 | 2 | | n,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)FIRST( j) 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前

11、去执行任务。这个候选就是那个终结首符集含a的。,提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成 AA | 1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,ETE E+TE | TFT T*FT | F(E) | i i + i,4.2.4 LL(1)分析条件,i + i,IP,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,G(E): ETE

12、 E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,G(E): ETE E+TE

13、| TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,

14、IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,S T+,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,4.2.4 LL(1)分析条件,构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1| 2| n 则 FIRST( i)FIRST( j) (ij) 3. 对文法中的每个

15、非终结符A，若它存在某个候选首符集包含，则 FIRST( i)FOLLOW(A)= i=1,2,.,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A 1 | 2 | | n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。,4.2.6 构造FIRST(),若* 则规定

16、FIRST() 直观上说文法符号串 的开始符号集是由推导出的开头的终结符（包括）组成。,例文法GS:,SAp SBq Aa AcA Bb BdB,FIRST(Ap)=a,c FIRST(Bq)=b,d FIRST(a)=a FIRST(cA)=c FIRST(b)=b FIRST(dB)=d,由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析,对每一文法符号XVTVN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)

17、X。 2. 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。,3. 若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。,对文法G的任何符号串=X1X2Xn构造集合FIRST()。 1. 置FIRST()FIRST(X

18、1)； 2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若则FIRST()。,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i | x 构造每个非终结符的FIRST：,First集(3),First集(2),First集(1),E,T,T,F,i,x,E,*,(,i,x,First集(0),*, ,(,i,x,4.2.6 构造FOLLOW(A),若有S=* A，则规定 # FOLLOW(A) （注： # 输入串#，#做为输入串的结

19、束符） 直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,例 文法G S: SaA|d AbAS|,由 S=* S 得 # FOLLOW(S) 由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW(S)=#,a,d,由S=* aA 得 # FOLLOW(A) 由S=* abAS=* abAaA 得 a FOLLOW(A) =* abAd 得 d FOLLOW(A) FOLLOW(A)=#,a,d,对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，

20、置于FOLLOW(S)中； 2. 若AB是一个产生式，则把FIRST()加至FOLLOW(B)中；,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i | x 构造每个非终结符的FOLLOW集：,Follow集(2),Follow集(1),E,T,T,F,E,*,Follow集(0),+,#,),*,+,#,),例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 构造每个非终结符的FIRST和FOLLOW集合：,FIRST(E) =(,i FIRST(E)=+, FIRST(T) =(,i FIRST(T)=*, FI

21、RST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F) =*,+,),#,4.2.7 预测分析程序,一、预测分析程序工作原理 if(a FIRST(i) 用Ai推导 else if(a FOLLOW(A)用A推导 else 语法错误 预测分析程序或LL(1)分析法： 总控程序 分析表 MA，a矩阵，A VN ，a VT 是终结符或， 分析栈 STACK 用于存放文法符号,总控程序,分析表,输入串,分析栈 STACK,预测分析程序的工作图,输出流,总控程序根据现行栈顶符号X和当前输入符

22、号a，执行下列三种动作之一: 1. 若Xa，则宣布分析成功，停止分析。 2. 若Xa ，则把X从STACK栈顶逐出，让a指向下一个输入符号。,匹配成功,3. 若X是一个非终结符，则查看分析表M。 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。 若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR。,推导,预测分析程序流程,上托栈顶符放入X,N,Y,Y,N,N,N,N,Y,Y,Y,把#和文法开始符压入分析栈； 当前输入符送a

23、,把产生式右部反序进栈,XVT ?,X=# ?,X=a ?,X=a?,读下一输入符到a,MX,a有产生式？,出错,结束,出错,预测分析程序工作过程,预测分析程序的总控程序： BEGIN 首先把然后把文法开始符号推进STACK栈； 把第一个输入符号读进a； FLAG:=TRUE; WHILE FLAG DO BEGIN 把STACK栈顶符号上托出去并放在X中； IF XVT THEN IF X= a THEN 把下一输入符号读进a ELSE ERROR,匹配成功,ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX

24、1X2XkTHEN 把Xk,Xk-1,X1一一推进STACK栈 /* 若X1X2Xk=，不推什么进栈 */ ELSE ERROR END OF WHILE; STOP /*分析成功，过程完毕*/ END,分析成功,推导,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 输入串为i1*i2+i3，利用分析表进行预测分析：,步骤符号栈输入串所用产生式 0#Ei1*i2+i3# 1#ETi1*i2+i3# ETE 2#ETFi1*i2+i3# TFT 3#ETii1*i2+i3# Fi,步骤符号栈输入串所用产生式 3#ETii1*i2+i3# Fi 4#ET*

25、i2+i3# 5#ETF*i2+i3# T*FT 6#ETF i2+i3# 7#ETii2+i3# Fi,步骤符号栈输入串所用产生 7#ETii2+i3# Fi 8#ET+i3# 9#E+i3# T 10#ET+i3# E+TE 11#ETi3#,步骤符号栈输入串所用产生 11#ETi3# 12#ETF i3# TFT 13#ETii3# Fi 14#ET# 15#E# T 16# E,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A) 构造分析表MA，a,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 构造每个非终结符的FIRST和FO

26、LLOW集合：,FIRST(E) =(,i FIRST(E)=+, FIRST(T) =(,i FIRST(T)=*, FIRST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F) =*,+,),#,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。 1. 对文法G的每个产生式A执行第2步和第3步； 2. 对每个终结符a FIRST()，把A加至MA，a中； 3. 若FIRST()，则对任何bFOLLOW(A)

27、把A加至MA，b中。 4. 把所有无定义的MA，a标上“出错标志”。,如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。 可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。,G(S): S iCtS | iCtSeS | a C b 提取左因子之后，改写成： G(S): S iCtSS | a S eS | C b,最近匹配原则,4.2.10 递归下降分析程序构造,构造不带回溯的自上而下分析程序 要消除文法的左递归性 克服回溯,实现思想： 对文法中的每个非终结符编写一个递归过程，识别由该非终结

28、符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的FIRST集或FOLLOW集（A ）可唯一确定选择哪个产生式进行匹配。 当识别到终结符时，与当前输入符号匹配，并读取下一输入符； 当识别到非终结符时，则调用该非终结符相应的过程。,例 算术表达式文法G:,ETE E+TE TFT T*FT F(E)i,判断G是LL(1)文法,1 判断是否可以应用递归子程序法,2 构造文法G的递归下降分析器 定义： 当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。,组成

29、： 递归下降分析器由一个主程序MAIN和每个非终结符对应的一个递归过程组成。 用到的一些子过程： 过程GETNEXT负责读入下一个TOKEN字 过程ERROR负责报告语法错误 约定： 变量TOKEN存放已读入的TOKEN字 过程进入时变量TOKEN存放了一个待匹配的TOKEN字 退出过程时，变量TOKEN中仍存放着一个待匹配的TOKEN字。,非终结符相应的分析子程序的构造方法 对于每个非终结符U，编写一个相应的子程序P(U); 对于产生式Ux1 | x2 |xn，x1,.xn都 关于U的子程序P(U)按如下方法构造： if TOKEN in first(x1) then p(x1) else

30、if TOKEN in first(x2) then p(x2) else . if TOKEN in first(xn) then p(xn) else ERROR,如果U还有空产生式U ,则算法中的语句： if TOKEN in first(xn) then p(xn) else ERROR 改写为 if TOKEN in first(xn) then p(xn) else if TOKEN not in follow(U) then ERROR 对于符号串x=y1y2yn；p(x)的含义为： begin p(y1);p(y2);p(yn) end 如果yiVN，则P(yi)就代表调用yi

31、的子程序；yiVT，则P(yi)为形如下述语句的一段程序 if TOKEN=yi then GETNEXT(TOKEN) else ERROR,(1) program MAIN; /* 主程序 */ begin GETNEXT (TOKEN); E (TOKEN); /* 转匹配ETE */ if TOKEN # then ERROR end.,构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(2) procedure E (TOKEN); /*匹配ETE*/ begin T (TOKEN); /*转匹配TFT*/ E (TOKEN) /*转匹配E+TE*/ end;

32、,(3) procedure E (TOKEN); /*匹配E+TE*/ begin if TOKEN=+ then /*选择产生式E+TE*/ begin GETNEXT (TOKEN); /*匹配+,读下一个TOKEN字*/ T (TOKEN); /*转匹配TFT*/ E (TOKEN) /*转匹配E+TE*/ end else /*E对应的语句*/ if TOKEN) and TOKEN# then ERROR end;,(5) procedure T (TOKEN); /* 匹配T*FT */ begin if TOKEN = * then /* 选择产生式T*FT */ begin GETNEXT (TOKEN); /* 匹配*，读下一TOKEN字 */ F (TOKEN); /* 转匹配F(E)i */ T (TOKEN) /* 转匹配T*FT */ end else /* T对应的语句*/ if TOKEN+ and TOKEN) and TOKEN# then ERROR end;,(4) procedure T (TOKEN); /*匹配TFT */ begin F (TOKEN); /*转匹配F(E)i*/ T (TOKE