工学第4章编译原理课件

1、第4章 语法分析自上而下分析 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL（1）分析法4.4 递归下降分析程序构造4.5 预测分析程序第4章 语法分析自上而下分析 内容回顾句型、句子和语言的定义句型有文法GS，若S =*，且*, 则称是是文法G的一个句型句子有文法GS，若S =*，且T* , 则称是是文法G的一个句子语言由文法 G 产生的所有句子的集合 L(G)=|S=+,且T*内容回顾 最左(最右)推导在推导的任何一步=*(其中和是句型)， 都对中的最左(最右)非终结符进行替换句型分析(句子分析)识别一个符号串是否为某文法的句型(句子)的过程也就是某文法的某个推导的

2、构造过程设文法G为: E E+T|T T T*F|F F (E)|i 请问符号串i+i*i是 否为该文法的句子? 自上 而下自下而上EE + TT * FFFTiii内容回顾 术语解释分析算法(分析器、识别算法)在语言的编译实现中，把完成句型(句 子)分析的程序称为分析程序或识别程序从左到右的分析算法即总是从左到右地识别输入符号串，首 先识别符号串中的最左符号，进而依次 识别右边的一个符号内容回顾 4.1语法分析器的功能任务分析并判定输入的单词符 号串是否符合该语言的语 法规则(上下文无关文法)实质就是按照文法的产生式， 识别输入符号串是否为一 个句子(合法程序，语句， 表达式等)词法扫描器语

3、法分析器语义处理单词符号语法树4.1语法分析的功能 设计思想判断是否能从文法的开始符号出发推导出这个输入串或者,判断能否建立一棵与输入串匹配的语法分析树输入 单词符号串输出 语法分析树格式化的程序合法的表达式、语句、函数出错处理要求尽快发现错误，准确定位可能时进行恢复处理，继续语法分析4.1语法分析的功能 根据建立方法，语法分析算法可分为两大类:自上而下分析法从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导自下而上分析法从输入串开始，逐步进行归约，直至归约到文法 的开始符号两种方法反映了两种不同的语法树的构造过程自上而下从树根推导到树叶自下而上从树叶归约到树根4.

4、1语法分析的功能 4.2 自上而下分析面临的问题基本方法对任何输入串,试图从文法的开始符号出发， 自上而下地为输入串建立一棵语法树或者说，为输入串寻找一个最左推导过程本质是一种试探过程，是反复使用不同产生式 谋求匹配输入串的过程如何选择哪个产生式进行推导?4.2自上而下分析面临的问题 例 文法GS SxAy Aab|a 判断输入串 w = x a y是否为该文法的句子？SxAy试探ab失败回溯a试探成功分析结束SxAy=xay=问题产生回溯的原因是什么?4.2自上而下分析面临的问题 公共左因子产生回溯例 文法G: S xAy A ab|a无法确定非终结符A面临输入符 号a时选用哪个关于A的候选

5、式 左递归无限循环例 文法G: S Sa|abaw = abaaaSSaSa无法确定何时用Saba产生式 进行推导某些文法导致自上而下分析具有不确定性4.2自上而下分析面临的问题 4.3 LL(1)分析法为了构造不带回溯的自上而下分析算法消除文法的左递归消除回溯、提取左因子LL(1)分析条件LL(1)文法4.3 LL（1）分析法 4.3.1 左递归的消除关于非终结符P的规则直接左递归定义：若P P 、 *例如 E E + TT（含有E的左递归） T T * FF（含有T的左递归） F ( E )i 4.3 LL（1）分析法 间接左递归定义： 若P =+ P *例如 间接左递归 S Aa A S

6、b|b S =Aa=Sba 即S=+Sb用S的产生式右部替换A右部的S得： A Aab|b 变成A的产生式含有直接左递归4.3 LL（1）分析法 消除直接左递归的方法改写为等价的右递归 形如：P P 非，不以P开始 改写为：PP（P为新增加的非终结符） PP改写前产生式可产生短语 P=P= 改写后产生式可产生短语 P= P = P = 等价4.3 LL（1）分析法 E E + TTT T * FFF ( E )iE T EE + T ET F TT * F TF ( E )i4.3 LL（1）分析法 消除多个直接左递归若有多个左递归的产生式如：PP1| P2 | Pm |1| 2 |n消除左递

7、归后变为： P1P |2 P|nP P 1P | 2 P| mP| 消除左递归要求文法： 1.无回路（A =* A） 2.无空产生式（A ）4.3 LL（1）分析法 练习例如有文法：KKa | Kb| Kc | d | e 消除左递归后变为： K dK |eK K aK | bK| cK|4.3 LL（1）分析法 间接左递归消除举例 S Qcc Q Rbb R SaaS=Qc=Rbc=Sabc 是间接左递归消除方法1：将非终结符排序： R Q S将R的右部代入Q，S：Q Sababb S Qcc （不变）将Q的右部代入S：S Sabcabcbcc消除S的直接左递归： S abcSbcS|cS

8、SabcS| Q Sabab|b R Saa整理化简：删除Q，R（无用）消除左递归后得： S abcSbcS|cS SabcS| 4.3 LL（1）分析法 S Qcc Q Rbb R Saa消除方法2：将非终结符排序： S Q R将S的右部代入Q，R：Q Rbb（不变） R Qcaca|a将Q的右部代入R： R Rbcabca|ca|a消除R的直接左递归： R bcaRcaR|aR RbcaR| 整理化简：S，Q（有用）消除左递归后得： S Qcc Q Rbb R bcaRcaR|aR RbcaR| 4.3 LL（1）分析法 消除左递归算法1.以某种S顺序将文法的非终结符排列 P1，P2，,P

9、n 2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k,其中 Pj1|2|是关于Pj的所有规则; 消除Pi的直接左递归 END3.化简由2所得的文法，即去除那些从开始符号 出发永远无法到达的非终结符的产生式当非终结符的排列顺序不 同时，变换后的文法形式 可能不同，但是它们都和 原文法是等价的 4.3 LL（1）分析法 4.3.2 消除回溯、提左因子消除回溯目的对文法的任何非终结符，当它去匹配输入串 时，能够根据输入符号，准确地选择合适的 候选式去匹配若需要非终结符A去匹配输入串，A的候选式 为A1| 2 | n ，

10、 A所面临的第一 个输入符号为a时，A能准确地选择i去执行 匹配任务，则无需回溯4.3 LL（1）分析法 提取公共左因子方法对于所有形如 A12.n的规则 其中，为左因子，不以开头改写为AA 其中A为新增加的非终结符 A12.n例如 S xAy A ab|a提左因子后变换为 S xAy A aA A b|4.3 LL（1）分析法 4.3.3 LL(1)分析条件FIRST集合的定义FOLLOW集合的定义LL(1)分析条件LL(1)文法的定义4.3 LL（1）分析法 FIRST()集合的定义设G=(T，N，S，P） * FIRST()=a|=* a ，aT若=*，则FIRST() FIRST()是

11、的所有可能推导的首遇 终结符号或，是选择产生式的依据a E T E E + T ET F T T * F T F ( E )iFIRST(E) = (（E）=0（E） FIRST（TE） =（，iTE=FTE=（E）TETE=FTE=iTE4.3 LL（1）分析法 FOLLOW(A)集合的定义 A N FOLLOW(A)= aS=*Aa，aT 若S=*A，则#FOLLOW（A）#输入串的结束符 也可看作是句子的括号 #S#FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号SAaE T E E + T E T F T T * F T F ( E )i ） FOLLOW（E）S = TE =

12、 FTE =（E）TE + FOLLOW（T）S = TE = T+TE # FOLLOW（E）S =0 E 4.3 LL（1）分析法 消除回溯的条件非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选和，满足： FIRST() FIRST() = 当要求 A 匹配输入串时，A就能根据它所面 临的第一个输入符号 a，准确地指派某一个 候选去执行任务，这个候选就是那个终结首 符集含 a 的4.3 LL（1）分析法 非终结符A的自动匹配当非终结符 A 面临输入符号a，但a不属于A 的任何候选首符集，如果A有候选式A(A 的某个候选首符集包含)，可以让A自动得 到匹配，即A匹配于空字，但输

13、入符号不读 进要想让A自动匹配成功，需要考察FOLLOW(A) 4.3 LL（1）分析法 i + i # 的推导过程设有文法GETE E+TE| TFT T*FT| F(E)|i iFIRST(i)+FIRST(+TE)+FOLLOW(T)#FOLLOW(E)#FOLLOW(T)ii生成语法分析树4.3 LL（1）分析法 推导过程的分析输入输出输入：符号串(有序的) 输出：结构化的符号串(树结构)产生式的选择根据当前符号（单词）语法分析树的表示按照使用序列排列的产生式序列4.3 LL（1）分析法 无回溯的自上而下分析的文法的条件文法不含左递归对于文法的每个非终结符 A 的任何两 个不同的产生式

14、 A|1) FIRST()FIRST() = 2) =*和=*不能同时成立3) 如果=*，则 FISRT(/A)FOLLOW(A)= 满足以上条件的文法称为LL(1)文法4.3 LL（1）分析法 LL(1)分析含义第一个 L 表示从左向右扫描输入符号串第二个 L 表示生成最左推导1 表示读入一个符号可确定下一步推导对于LL（1）文法，可以对输入串进行有效的无回溯的自上而下分析。对于文法G，当面临的输入符号为a，要用非终结符A进行匹配时，假设A的所有产生式为 A1| 2 | n1)若aFIRST(i )，则指派i去执行任务2)若a不属于任何候选首符集，则： 若属于某个FIRST(i )且 aFO

15、LLOW(A)，则让A与自动匹配 否则，a的出现是一种语法错误4.3 LL（1）分析法 4.4 递归下降分析程序构造不带回溯的自上而下分析程序分析程序一组递归过程每个非终结符一个子过程LL（1）文法构造分析程序从开始符号所对应的过程开始运行子过程的功能： 对相应非终结符产生式右部进行语法分析4.4 递归下降分析程序构造 例 表达式文法的递归下降分析器消除左递归后的表达式文法G为：E TE E+TE| T FT T*FT| F (E)|i可以证明 G是一个LL（1）文法E( )E( )T( )T( )F( )5个非终结符构造5个子过程4.4 递归下降分析程序构造 递归下降分析器构造说明C语言 E

16、（ ） T; E;ETE（1）E（）：完成对 E T E的右部分析PASCAL语言procedure E;begin T; E;end;右部有非终结符时，调用该非终结符对应的子过程来完成E()if (c=+) p+; T; E; ETE（2）E（）：完成对 E +T E|的右部分析procedure E;if sym=+ then begin advance; T; E; end；+其它 非+字符 自动匹配advance：把输入指针ip下移一位sym：当前所面临的输入符号4.4 递归下降分析程序构造 C语言练习T( ) F; T; (3)T(): T F Tprocedure T;begin

17、F; T;end;TFT4.4 递归下降分析程序构造 (4)T(): T* F T|C语言练习T()if (c=*) p+; F; T; procedure T;if sym=* then begin advance; F; T; end；TF*其它 非*字符 自动匹配T4.4 递归下降分析程序构造 (5)F(): F (E)|i procedure F; begin if sym=( then begin advance; E; if sym= ) then advance else error括号不匹配 end else if sym= i then advance else error

18、F面临非（，i输入符号，语法错误 endEF()i其它 非(,i字符出现语法错误4.4 递归下降分析程序构造 的子程序F() if (c=() p+; E; if (c=) p+; else error; /*括号不匹配*/ else if (c=i) p+; else error;/*F面临非(,i输入符号， 语法错误*/ EF()i其它 非(,i字符出现法错误4.4 递归下降分析程序构造 i+i的递归下降分析过程 ii生成语法分析树i + i #匹配成功返回，指针下移自动匹配，返回自动匹配，返回自动匹配，返回匹配成功继续，指针下移匹配成功返回，指针下移分析成功结束4.4 递归下降分析程序构

19、造 递归下降分析程序优缺点分析优点：1）直观、简单、可读性好2）便于扩充缺点：1) 递归算法的实现效率低2) 处理能力相对有限3) 通用性差，难以自动生成4.4 递归下降分析程序构造 递归下降分析程序课堂练习文法G为：S (T)|a+S|a T T,S|S 消除左递归：S (T)|a+S|a T ST T ，ST|提取左因子：S (T)|aS S +S| T ST T ，ST|4个子程序：S（） S（） T（） T（） BEGIN4.4 递归下降分析程序构造 递归下降分析程序课堂练习答案（1）S (T)|aSS() if(c=() /*匹配第一候选式*/ p+; T; if(c=) p+; e

20、lse error; /*括号不匹配*/ else if(c=a) p+;S;/*匹配第二候选式*/ else error; /*语法错误*/4.4 递归下降分析程序构造 (2)S+S| S() if(c=+) p+; S; (3)T STT()S; T;(4)T,ST|T()if(c=,) p+; S; T;4.4 递归下降分析程序构造 4.5 预测分析程序实现LL(1)分析的另一种有效方法使用一张二维分析表（预测分析表）和一个分析栈（文法符号栈）联合进行控制来实现自上而下分析技术4.5 预测分析程序 预测分析表说明预测分析表实际上是一个矩阵MA,aMA，a =A i当A面临a时所应选用的候

21、选式空(error)A不可能与a匹配出现语法错误待匹配栈顶非终结符所面临输入符号4.5.1预测分析程序工作过程表达式文法的预测分析表ME，+ = E+T EE面临+时选用E+T EMT，) = TT面临）时选用T MF，* = errorF面临*时出现语法错误分析栈的说明分析栈用于存放分析过程中的文法符号topstack栈顶指针分析栈初始化时：栈底压入一个#底顶#Stoptop次栈底压入文法开始符S入栈操作push出栈操作poptop 预测分析器模型 输入缓冲区: a# X # 栈总控制程序预测分析表输出所选用产生式序列查找4.5 预测分析程序 总控程序执行时可能动作对于任何（X，a） X是栈

22、顶符号 a是面临输入符号(1) XT 且Xa#，分析成功结束，输入串是 一个合法句子(2) XT 且Xa#，X出栈，输入指针指向下一 输入符号(3) XN ，查分析表MX，a 若MX，a=Xi，X出栈，i逆序入栈，输入指针 不动 若MX，a=空，则调用error程序，进行错误处理4.5 预测分析程序 执行例子： i*i+i分析过程 栈 输入缓冲区 所用产生式0 #E i*i+i# E TE ET入栈1 #ET i*i+i# T FT 2 #ETF i*i+i# F i3 #ETi i*i+i# i出栈，a下移4 #ET *i+i# T*FT 5 #ETF* *i+i# *出栈，a下移6 #ET

23、F i+i# F i 7 #ETi i+i# i出栈，a下移4.5 预测分析程序 i*i+i 分析过程续 栈 输入缓冲区 所用产生式8 #ET +i# T 9 #E +i# E +TE10 #ET+ +i# 11 #ET i# T FT12 #ETF i# F i13 #ETi i# 14 #ET # T 15 #E # E 16 # # # = #分析成功结束输出的产生式序列形成了按最左推导生成的语法分析树4.5 预测分析程序 课堂练习一：i+i分析过程栈 输入缓冲区 所用产生式0 #E i+i# E TE1 #ET i+i# T FT2 #ETF i+i# F i 3 #ETi i+i#

24、4 #ET +i# T 5 #E +i# E +TE6 #ET+ +i# 7 #ET i# T FT 4.5 预测分析程序 i+i 分析过程续栈 输入缓冲区 所用产生式8 #ETF i# F i9 #ETi i# 10 #ET # T 11 #E # E 12 # # # = #分析成功4.5 预测分析程序 课堂练习二：i+i*i分析过程栈 输入缓冲区 所用产生式0 #E i+i*i# E TE1 #ET i+i*i# T FT2 #ETF i+i*i# F i3 #ETi i+i*i# 4 #ET +i*i# T 5 #E +i*i# E +TE6 #ET+ +i*i#7 #ET i*i#

25、T FT 4.5 预测分析程序 i+i*i 分析过程续栈 输入缓冲区 所用产生式8 #ETF i*i# F i 9 #ETi i*i# 10 #ET *i# T *FT11 #ETF* *i# 12 #ETF i# F i13 #ETi i# 14 #ET # T 15 #E # E 16 # #4.5 预测分析程序 总控程序实现算法描述BEGIN PUSH(STACK,#)；PUSH(STACK,开始符号); a=第一个输入符号； FLAG:=TRUE； WHILE FLAG DO BEGIN X=POP(STACK); IF XT THEN IF X=a THEN a=下一个符号 终结符匹

26、配 ELSE ERROR与当前输入符号不匹配 4.5 预测分析程序 ELSE IF X=# THEN IF X=a FLAG:=FALSE ELSE ERRORX=a=# 分析成功结束ELSE IF MA，a = X X1 X2Xk 把 XkX2 X1一一推进STACK栈 ELSE ERROREND OF WHILESTOP 分析成功,过程完毕END4.5 预测分析程序 4.5.2 预测分析表的构造设有文法G，预测分析表构造过程：计算所有候选式的首符集 FIRST（）计算所有非终结符A的后继符集 FOLLOW（A）构造预测分析表 M4.5 预测分析程序 FIRST()的计算法FIRST()=

27、a =* a ，aT 若 =*，则 FIRST() 计算文法符号X的FIRST（X）计算文法符号串=X1X2Xn的FIRST()4.5 预测分析程序 FIRST( X )的计算法重复以下计算，直到FIRST（X）不再增大为止：1) 若 XT，则 FIRST( X ) = X 。 例 FIRST（+）=+ FIRST（i）=i2) 若 XN，若有Xa，则将 a 加入FIRST(X)； 例 E+TE +FIRST（E） F（E）|i （，iFIRST（F）若有X ，则将加入FIRST( X )。 例 E FIRST（E）4.5 预测分析程序 若有X Y1Yi-1YiYk ，并对于某个i， 有1ji

28、-1，FIRST（Yj）， 即Y1 ，Yi-1=*， 则将所有FIRST( Yj )-FIRST( Yi )- 加入FIRST( X )中； -3)若有 X Y，且 Y N ， 则 FIRST(Y)-加入FIRST(X);例 F(E)|i FIRST(F)=（，iTFT FIRST(T)=FIRST(F)-=（，i若所有Y1,Yk=*，则将加入到 FIRST( X )。计算XY1Yi-1YiYk FIRST(X)集举例若有文法G为： X Y1 Y2 Y3 Y4 Y5 Y1 a Y2 b Y3 c Y4 d Y5 efFIRST集Y1Y2Y3Y4Y5Xa，b，c，d，e，fa,b,c,d,e,f

29、 因为Y5=*， 所以FIRST（X）=*=*因为Y5=*， 所以FIRST（X）4.5 预测分析程序 计算表达式文法FIRST(X)集举例文法G为：E T EE+ T ET F T T* F T F ( E )i先找以终结符开头的产生式FIRST( F ) = ( ,i FIRST( E ) = + ，FIRST( T ) = * , 再找右部以非终结符开头的产生式FIRST( T ) = FIRST( F )FIRST( E ) = FIRST( T )= ( ,i 4.5 预测分析程序 计算FIRST(X)集合课堂练习=a，c，d，q 文法G为：S ApBqA acA B dB先找以终结

30、符开头的产生式FIRST(A)= a ,c FIRST(B)= d ,再找右部以非终结符开头的产生式FIRST(S)= FIRST(A)-FIRST(B)-因为B=FIRST(S),因为S=*FIRST(q)4.5 预测分析程序 计算表达式文法候选式FIRST()集举例候选式的FIRST集FIRST(TE)=FIRST(T)=(,iFIRST(+TE)=+FIRST(FT)=FIRST(F)=(,iFIRST(*FT)=*FIRST(E)=(FIRST(i)=iFIRST()=文法G为：ETE E+TE| TFT T*FT| F(E)|i非终结符的FIRST集FIRST(E)=(,iFIRST

31、(E)=+,FIRST(T)=(,iFIRST(T)=*, FIRST(F)=(,i4.5 预测分析程序 计算FIRST()集合课堂练习文法G为：S ApBq A acAB dB非终结符的FIRST集FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(B)=d, 候选式的FIRST集FIRST(Ap)=FIRST(A)=a,cFIRST(Bq)=FIRST(B)- FIRST(q) =d,qFIRST(a)=aFIRST(cA)=cFIRST(dB)=dFIRST()=4.5 预测分析程序 FOLLOW(A)的计算法FOLLOW(A)= aS=*Aa，aT 若S=*A，则#F

32、OLLOW（A）重复以下计算，直到每个FOLLOW(A)不再增大为止：1)将 # 加入到 FOLLOW( S )中 例 # FOLLOW( E )2)若AB, 则将FIRST()-加入FOLLOW(B) 例 ETE FIRST(E)-加入FOLLOW(T) TFT FIRST(T)-加入FOLLOW(F)4.5 预测分析程序 3) 若 A B ，或 A B， 且 =*，即 FIRST()，AB 则将FOLLOW(A)所有元素加入FOLLOW(B) 例 E T EFOLLOW(E)加入FOLLOW(E)E T EEFOLLOW(E)加入FOLLOW(T)T F TFOLLOW(T)加入FOLLO

33、W(T)T F TFOLLOW(T)加入FOLLOW(F)T4.5 预测分析程序 计算表达式文法的FOLLOW集举例#FOLLOW（开始符号）对每个非终结符查看其在产生式右边的出现G：ETE E+TE| TFT T*FT| F(E)|i#FOLLOW(E)=FIRST(E)-FOLLOW(T)FOLLOW(E)=+,),#FOLLOW(F)=FIRST(T)-FOLLOW(T)=*,+,),#FOLLOW(E)=),#FOLLOW(E)=FOLLOW(E)=),#FOLLOW(T)=FOLLOW(T)=+,),#相同不需处理计算FOLLOW(A)集合课堂练习文法G为：S ApBq A acAB

34、 dB非终结符的FIRST集FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(B)=d, 非终结符FOLLOW集FOLLOW(S)=#FOLLOW(A)=FIRST(p)- =pFOLLOW(B)=FIRST(q)- =q4.5 预测分析程序 表达式文法是 LL(1) 文法满足条件（3）： E FIRST(+TE)=+ FOLLOW(E)=),# T FIRST(*FT)=* FOLLOW(T)=+,),# 文法G是LL（1）文法满足条件（1）：已消除左递归满足条件（2）：FIRST(+TE)=+ FIRST()= FIRST(*FT)=* FIRST()= FIRST(E)=( FIRST(i)=i 文法G：E TE E+TE | T FT T*FT | F (E)i预测分析表的构造算法(4)把所有无定义的 MA,a标上“出错标志”(1)对文法G的每个产生式 A，执行(2)和(3)(2)对每个终结符aFIRST()， 把 A 填入 MA,a(3