自顶向下语法分析方法市公开课获奖课件

1、 第5章 自顶向下语法分析办法语法分析主要工作： 是辨认由词法分析给出单词序列是否是给定正确句子（程序）。语法分析惯用办法： 自顶向下语法分析和自底向上语法分析两大类。第1页第1页自顶向下分析思想自顶向下办法： 从文法开始符号（设为程序）开始进行分析，逐步推导往下结构语法树，使其树叶正好结构出所给定源程序串。自顶向下主要思想： 从开始符出发导出句型并一个符号一个符号地与给定终止符串进行匹配。假如所有匹配成功，则表示开始符号可推导出给定终止符串。因此鉴定给定终止符号串是正确句子。自顶向下办法关键： 是拟定在推导过程中选择候选式问题。当进行推导时，一个非终止符也许相应多个产生式，这样我们就无法事先

2、知道应当用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能拟定应当用产生式。第2页第2页自顶向下缺点: 在推导过程中，假如对文法不做限制。那么产生式选择成为无依据，只好一一去试所有也许产生式，直至成功为止。这种办法致命弱点是不断地回溯，大大影响速度。 因此自顶向下分析法又分为拟定和不拟定两种： 拟定分析办法需对文法有一定限制，但由于实现办法简朴，直观，便于手工结构或自动生成语法分析器，因此仍是当前常有办法之一。 不拟定办法即回溯分析办法。这种办法事实上是一个穷举试探办法，因此效率低，代价高，因此很少使用。第3页第3页5.1 拟定自顶向下分析思想例5.1若有文法GS： S pA S qB

3、 A cAd A a 若有输入串w = pccadd. 解：推导过程为：其相应语法树见右图：SS这个文法特点： 1每个产生式右部都由终止符号开始。 2假如两个产生有相同左部，那么它们右部由不同终止符开始。显然对于这样推导中完全能够依据当前输入符号决定选择哪个产生式往下推导。因此分析过程是唯一。pcAdcAdpccAddcAdpccaddapApA考察自顶向下推导过程。第4页第4页例5.2：若有文法G2S： S Ap S Bq A a A cA B b B dB 若有输入串w = ccap。考察自顶向下推导过程。 解：自顶向下推导过程为：其相应语法树见右图：SS这个文法特点： 1产生式右部不全是

4、由终止符号开始。 2假如两个产生有相同左部，它们右部由不同终止符或非终止符开始。 3文法中无空产生式。ccApcAAppAAcApcccapa第5页第5页小结： 在上述推导过程中，对于产生式中相同左部含有非终止符打头右部时，在推导中选取哪个产生式是不能直接知道。 对输入串W=ccap为输入串时，其第一个符号为c，这时从S出发选择S Ap，还是选择S Bq。其依据是要知道 A或B它们是否能推导以c打头符号串，即它们首符集是什么。若c是Ap首符集元素，且不在Bq首符集中，则选择S Ap往下推导。反之，若c在Bq首符集中，不在Ap首符集中，则选择S Bq往下推导。其它情况为不拟定推导或犯错。 因此，

5、在推导前有必要求出每个文法符号首符集。第6页第6页一.首符集，后继符集与选择集定义：定义4-1（首符集定义）： 设G=(VN ，VT ，P，S）是上下文无关文法，是G任一符号串，则有：FIRST（）=a | * a,a VT， 、 V* 尤其地，若 * ，则要求 FIRST()即： FIRST()是从出发推导出所有符号串首终止符或也许构成集合。第7页第7页这样在文法 G2中，关于S两个产生式即使都以非终止符开始，但它们右部符号串能够推导出首符集合互不相交，因此可依据当前输入符号是属于哪个产生式右部首符号集合而决定选择相应产生式进行推导。因此是拟定自顶向下分析。 有文法G2S： S Ap S B

6、q A a A cA B b B dB 第8页第8页例5.3:若有文法G3S:SaAS dA bASA若有输入串W=abd。考察自顶向下推导过程。解：相应语法树为右图：SSaAaAabASbASabSabdd当文法中有空产生式时,如例：第9页第9页小 结： 由此能够看出，当某一非终止符产生式中含有空产生式时，它非空产生式右部首符号集两两不相交，并与在推导过程中紧跟该非终止符右边也许出现终止符集也不相交，则仍可结构拟定自顶向下分析。为此可定义一个文法符号后继符集合为： （定义5.2） 从上述推导过程中我们能够在第二步到第三步推导中，即abAS abS时，因当前面临输入符号为d，而最左非终止符A产

7、生式右部开始集合都不包括d，但有，因此对于d匹配自然认为只能依赖于在也许推导过程中A后面符号。因此这时选取产生式A 往下推导，而当前A后面符号为S，S产生式右部开始符号包括了d，因此匹配。 第10页第10页FOLLOW(A)=a|S * A且aVT ,a FIRST(), VT*,V*或 FOLLOW(A)=a | S * Aa ,aVT定义5.2:尤其地，若S * A,则#FOLLOW(A)(这里#不是文法中符号，而一个尤其表示输入串结束符或称句子括号如 #输入串#）表示：所有在句型中紧挨着A出现终止符或#均是 FOLLOW(A)元素。 因此当文法中含有形如： A和 A产生式时，其中AVN

8、,V*,当和不同时推导出空串时，设 * ， ，则当FIRST() (FIRST()FOLLOW(A)=时，对于非终止符A替换仍可唯一地确定候选。设G=(VN , VT ,P,S)是上下文无关文法，AVN后继符集合为：*第11页第11页定义5.3：定义选择符集合SELECT下列： 对于给出上下文无关文法产生式A,AVN,V*，则 SELECT(A) =FIRST()， 当 时FIRST()FOLLOW(A)，不然*第12页第12页（一） 求FIRST(X)算法 对每一文法符号X(VNVT），求FIRST(X).(a)若XVT,则令FIRST(X)=X;(b)若XVN,且有产生式Xa.,(aVT)

9、，则令aFIRST(X);(c) 若XVN,有X，则令 FIRST(X);(d)若 XVN, y1, y2,.yi都VN,且有产生式X y1 y2.yn, 三种集合结构算法：注：三种集合均为终止符集 当y1, y2,.yi-1 都 * 时，（其中1in),则FIRST(y1)-,FIRST(y2)-,.,FIRST(yi-1 )-,FIRST(yi)都包括在 FIRST(X)中。(e)当(d)中所有yi * (i= 1,2,.,n), 则 FIRST(X)=FIRST(y1)FIRST(y2).FIRST(yn)重复使用上述（b)(d) 步直到每个符号FIRST集合不再增长为止。第13页第13

10、页（二）求 FIRST()算法（= x1 x2 . xn):1.若n=0,即=,则令FIRST()=;2.不然，对1in,求FIRST(xi)3.若n=1,则令 FIRST()=FIRST(x1);4.若n2且对一切j=1,2,.,i-1都有FIRST(xj). 则令FIRST(xi )- = FIRST(),其中2in; 若对一切 j=1,2,n都有FIRST(xj),则令FIRST()或：1.把FIRST(x1)中所有非元素加入到FIRST()中，即 FIRST( )=FIRST(x1)- ; 若FIRST(x1)包括有，则把FIRST(x2)所有非元素加入到 FIRST()中，即FIRS

11、T()=FIRST() (FIRST(x2)-); 若FIRST(x1)和FIRST(x2)都包括有 ，则把FIRST(x3)所有 非元素加到FIRST()中； 照此办法继续，始终到考察到xn。 2.若FIRST(xi ),i= 1,2,n;即每个FIRST(xi )中都有。则将加 到FIRST()中。尤其地， 若 = ，则FIRST()=.第14页第14页(三) 求FOLLOW(A)算法(A VN):(a)对文法开始符号S，令# FOLLOW(S).(b)若BA是一个产生式，则令FIRST()- 属于FOLLOW(A);(c) 若BA是一个产生式，或BA是一个产生 式且有FIRST()，则令

12、FOLLOW(B)是 FOLLOW(A)子集。即把FOLLOW(B)所有元素 加入到FOLLOW(A)中。(d)重复使用(b)直到每个非终止符 FOLLOW集合 不再增长为止。第15页第15页(四) 求SELECT(A)算法： (a)求FIRST()； (b)若 FIRST(),则令SELECT(A)=FIRST() 不然求FOLLOW(A), 并令SELECT(A)=FIRST() FOLLOW(A).例：有文法：ETE E+TE | TFT T*FT | Fi | ( E )求其三种集合。第16页第16页解：FIRST(E)=FIRST(T)=FIRST(F)=i, ( FIRST(E)=

13、+,FIRST(T)=*,FOLLOW(E)=FOLLOW(E)= ),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#SELECT(ETE)=FIRST(T)=i,( SELECT(E+TE)=FIRST(+TE)=+SELECT(E)=FIRST()FOLLOW(E)=,),#SELECT(TFT)=FIRST(F)=i,(SELECT(T*FT)=FIRST(*FT)=*SELECT(T)=FIRST()FOLLOW(T)=,+,),#SELECT(Fi)=FIRST(i)=iSELECT(F(E)=FIRST(E) =(例：有文法：ETE E+TE

14、| TFT T*FT| Fi| (E)求其三种集合。第17页第17页例：设有文法GS：SaAS ， Sb ， AbA ， A 5.2 LL(1)文法判别定义5.4：一个上下文无关文法是LL(1)文法充分必要条件是每个非终止符A两个不同产生式，A ,A ；满足 SELECT(A ) SELECT(A )= 。 其中， 、 不能同时 * 。SELECT(SaAS)=FIRST(aAS)=a SELECT(Sb)=b SELECT(AbA)=b SELECT(A)=FIRST()FOLLOW(A)=a,b,SELECT(SaAS)SELECT(Sb)=ab= SELECT(AbA)SELECT(A)

15、=ba,b 故文法 GS不是LL(1)文法。 当一个文法是LL(1)文法时，则该文法一定能够采用拟定自顶向下分析办法进行分析。第18页第18页5.3文法等价变换 拟定自顶向下分析要求给定语言文法必须是 LL(1)形式，然而，不一定每个语言都是LL(1)文法，对一个语言非LL(1)文法是否能变换为等价LL(1)形式以及如何变换是我们讨论主要问题。由LL(1)文法定义可知若文法中含有左递归或含有左公共因子，则该文法必定不是LL(1)文法，因而，我们设法消除文法中左递归，提取左公共因子对文法进行等价变换。1.提取左公共因子 若文法中含有形如：A | 产生式，这造成了对相同产生式右部FIRST集相交。

16、即有SELECT(A ) SELECT(A )不满足LL(1)文法充要条件。等价互换为： A (| ) A A A | 第19页第19页更普通地:对A 1| 2 | | n提取左公因子为：A A A 1| 2 | | n若在i , j , k中仍含有左公共因子，可再进行提取，这样重复进行提取直到所引进新非终止符相关产生式均无左公共因子为止。结论：1）不一定每个文法左公共因子都能在有限环节内替换成无左公共因子文法。2）一个文法提取了左公共因子后，只处理了相同左部产生式右部FIRST集不相交问题。当改写后文法不含有空产生式，且无左递归时，则改写后文法是LL(1)文法。不然还需用LL(1)文法判别办

17、法进行判断才干拟定是否为LL(1)文法。第20页第20页2.消除左递归 一个文法含有下列形式产生式之一时：1)AA , AVN, V*2)AB , BA , A,BVN, ,V*则称该文法是左递归。然而，一个文法是左递归时，不能采用自顶向下分析法。消除左递归办法有：a)把直接左递归改写为右递归： 设有文法产生式：AA|. 其中非空， 不以A打头。 可写为：AA AA | 普通情况下，假定关于A产生式是： AA 1| A 2 | | A m| 1| 2 | | n 其中， i(1im)均不为空， j(1jn)均不以A打头。 则消除直接左递归后改写为： A 1 A | 2 A | | n A A

18、1 A | 2 A | | m A | 第21页第21页例：有文法G(E)：EE +T |T TT*F | F Fi| (E)消除该文法直接左递归。解： ETE E+TE| TFT T*FT| Fi| (E)AA|改写为： AA AA | 第22页第22页b)消除间接左递归： 对于间接左递归消除需要先将间接左递归变为直接左递归，然后再按a)清除左递归。以文法G6为例： (1)AaB (2)ABb (3)BAc (4)Bd用产生式(1)，(2)右部代替产生式(3)中非终止A得到左部为B产生式: (1)BaBc (2)BBbc (3)Bd消除左递归后得到： BaBcB|dB BbcB|再把本来其余

19、产生式AaB,ABb加入，最后得到等价文法为:(1) AaB(2) ABb(3) B(aBc|d)B(4) BbcB|第23页第23页c)消除文法中一切左递归算法设非终止符按某种规则排序为A1, A2, An 。For i:=1 to n do begin For j:=1 to i-1 do begin 若Aj所有产生式为： Aj 1| 2 | | n 替换形如Ai Aj 产生式为： Ai 1 |2 | |n end 消除Ai中一切直接左递归 end第24页第24页5.4 不拟定自顶向下分析思想 当文法不满足 LL(1)时，则不能用拟定自顶向下分析，但有时可用不拟定自顶向下分析法，也就是带回

20、溯自顶向下分析法。 引起回溯原因是在文法中当关于某个非终止符产生式有多个候选时，而面临当前输入符无法拟定选取唯一产生式，从而引起回溯，有三种情况：2。由于相同左部非终止符右部能 * 且该非终止符FOLLOW集合中含有其右部FIRST集合元素。 带回溯自顶向下分析是一个试探过程，当分析不成功是则推翻分析退回到适当位置再重新试探其余候选也许推导。这样需要统计推导每步所选过产生式，直到把所有也许推导序列都试空仍不成功才干拟定输入串是不是该文法句子而报错。 由于在编辑程序真正实现时往往是边分析边插入语义动作，因而带回溯分析代价高，效率很低，在实用编译程序中几乎不用。1。由于相同左部产生式右部 FIRS

21、T集交集不为空而引起回溯。3。由于文法含有左递归而引起回溯。第25页第25页5.5 拟定自顶向下分析办法5.5.1 递归下降法（递归子程序法） 在程序语言语法定义中有许多采用递归定义。我们在对它进行语法分析时，编译处理程序也采用递归方式，可使其结构简朴易读。但由于频繁地调用子程序大大地减少了分析速度。一、递归下降法主要思想是：对每个非终止符按其产生式结构写出相应语法分析子程序。由于文法递归相应子程序也递归，子程序结构与产生式结构几乎一致。因此称此种办法称为递归子程序法或递归下降法。二、用程序表示递归子程序内部结构： 设A是一个非终止符：A1 A2 An第26页第26页则写 (A) if cha

22、rfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示调用处理符号串i子程序。对文法加限制：1。任一非终止符B都不是左递归，不然会产生死循环。2。对A任意两个右部i , j ,有：first(i)first(j)= First(i)表示i所能导出串第一个符号集合。显然，每个ifirst(i)是互不相同，不然则无法判断应执行哪个(i )。对A任一右部i 设为： i = y1 y2 yn则定义( i) begin(y1);(y2);(yn) end其中y

23、j可分为下列两种情况（j=1,n):1) yjVT,则 ( yj) if char yj then ERROR else READ(char)2) yjVN,则(yj)表示调用关于yj递归子程序。A1 A2 An第27页第27页例1.设有文法G: A aABa BbBb | a则有(A) if char=a then (aABa) else ERROR if char=a then begin(a);(A);(B);(a) end else ERROR if char=a then begin if chara then ERROR else READ(char); (A); (B); if

24、chara then ERROR else READ(char) end else ERROR 第28页第28页(B) if char = b then (bBb) else if char=a then (a) else ERROR if char=b then begin if charb then ERROR else READ(char); (B); if charb then ERROR else READ(char) end else if char=a then if char a then ERROR else READ(char) else ERROR if char =b

25、then begin (b); (B); (b) end else if char=a then (a) else ERROR BbBb | a第29页第29页关于表示式处理： =| + =| * =| () = i | i() 例2：E: procedure E; begin T; while char=+ do begin READ(char); T end end即：ET | E +T TF | T *F FP | (E) P i | i (E)为了处理以便，把上述文法变为： ET+T TF*F FP| (E) Pi| i(E)第30页第30页T: procedure T; begin

26、F; while char = * do begin READ(char); F end endE: procedure E; begin T; while char=+ do begin READ(char); T end endF: procedure F; begin if char =( then begin READ(char); E; if char ) then ERROR else READ(char) end else P endET+TTF*FFP| (E)P i| i(E)第31页第31页P: procedure P begin if char i then ERROR

27、else begin READ(char); if char =( then begin READ(char); E; if char ) then ERROR else READ(char) end end end ET+TTF*FFP| (E)P i| i(E)第32页第32页5.5.2 预测分析办法（LL办法） LL(k)文法是采用拟定自左至右扫描（输入串）和自顶向下分析技术最大一类文法。LL系指：自左向右扫描（输入串），自上而下进行最左推导。 普通来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下办法进行分析过程中，假如每步仅利用当前非终止符（事实上此时它已位于分析栈顶）和

28、至多向前查看k个输入符号就能唯一 决定采用什么动作，那么这个文法称为LL(K)文法。 对于大多数程序设计语言而言。K=0或1就足够了。因此我们将主要讨论k1情形。第33页第33页一、LL(1)办法分析过程 从实现角度来说，上述替换过程需要花较多时间，由于它除了把一个候选式替换掉x1,还需要x2 xn统统进行移位处理,这时很麻烦。我们处理办法是用栈来保留x1x2 xn,并且是把xn作为栈底， x1作为栈顶，那么上述替换动作就简朴了，只需在栈顶进行替换。即去掉x1把候选式符号串按逆序方式压入栈中即可。 设分析当前格局为（x1x2 . xn#, y1y2 . ym#)，其中xi表示句型后端部分，诸y

29、j表示输入流后端部分（终止符串）。则也许有下述动作之一：1.替换：当x1VN时，则选相应候选式去替换x1 。2.匹配：当x1VT时，它与y1进行匹配，其结果为两种也许，如 果匹配成功，则去掉x1和y1（即只指针后移一位）不然报错。3.接受：当格局为(#, #）时，汇报分析成功结束。第34页第34页bBc#bbbdc# Bc#bbbdc# aBc#abbbdc# 例：设有文法：SaBc|bB BbB|d 且给定输入串abbbdc，看其自顶向下分析过程。栈：流： 替 S#abbbdc# 匹 替 匹 Bc#bbdc# 替 bBc#bbdc# 匹 Bc#bdc# 替 bBc#bdc# 匹Bc#dc#

30、替 dc#dc# 匹c#c# 匹# 接受结束第35页第35页二、LL(1)办法实现： LL(1)办法在实现时用到一个LL(1)分析矩阵和一个分析栈以及预测分析总控程序。 分析矩阵元素MA,a中下标A为非终止符，a为终止符或句子结束标识#，矩阵元素MA,a内容为一条关于A产生式。 它表明当用非终止符A向下推导而当前输入符为a时，所应采用候选式。当矩阵元素为空时，则表示用A往下推导时碰到了不应当出现符号，即A与a不能匹配。因此应当转向犯错处理。 预测分析程序见下图：第36页第36页流程图：# S 进栈，读输入流一符号 a栈顶元素出栈并送X对产生式右部x1 x2xn按逆序即xnxn-1x1 压入栈中读入符号 aXVT?X=a?MX,a为产生式？X=# ?犯错处理X=a?犯错处理结束yyy