第5章 自顶向下语法分析方法ppt课件.ppt
《第5章 自顶向下语法分析方法ppt课件.ppt》由会员分享,可在线阅读,更多相关《第5章 自顶向下语法分析方法ppt课件.ppt(42页珍藏版)》请在三一办公上搜索。
1、第5章 自顶向下语法分析(Top-down Syntax Analysis),语法分析的主要工作: 是识别由词法分析给出的单词序列是否是给定的正确句子(程序)。,语法分析常用的方法: 自顶向下的语法分析和自底向上的语法分析两大类。,自顶向下分析思想,自顶向下的方法: 从文法的开始符号(设为程序)开始进行分析,逐渐推导的往下构造语法树,使其树叶正好构造出所给定的源程序串。,自顶向下的主要思想: 从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功,则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。,自顶向下方法的关键: 是确定在推导过程中选择候选
2、式的问题。当进行推导时,一个非终结符可能对应多个产生式,这样我们就无法事先知道应该用哪个产生式,因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。,自顶向下的缺点:,在推导过程中,如果对文法不做限制。那么产生式的选择成为无根据的,只好一一去试所有可能的产生式,直至成功为止。这种方法的致命弱点是不断地回溯,大大影响速度。 所以自顶向下分析法又分为确定的和不确定的两种:,确定的分析方法需对文法有一定的限制,但由于实现方法简单,直观,便于手工构造或自动生成语法分析器,因此仍是目前常有的方法之一。,不确定的方法即回溯的分析方法。这种方法实际上是一种穷举的试探方法,因此效率低,代价高,因此
3、极少使用。,5.1 确定的自顶向下分析思想,例5.1若有文法GS: S pA S qB A cAd A a 若有输入串w = pccadd.,解:推导过程为:,其相应的语法树见右图:,这个文法的特点: 1每个产生式的右部都由终结符号开始。 2如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。,显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。,考察自顶向下的推导过程。,例5.2:,解:自顶向下的推导过程为:,其相应的语法树见右图:,这个文法的特点: 1产生式的右部不全是由终结符号开始。 2如果两个产生式有相同的左部,它们的右部由不同的终
4、结符或非终结符开始。 3文法中无空产生式。,小结:,在上述推导过程中,对于产生式中相同左部含有非终结符打头的右部时,在推导中选用哪个产生式是不能直接知道的。,对输入串W=ccap为输入串时,其第一个符号为c,这时从S出发选择S Ap,还是选择S Bq。其根据是要知道 A或B它们是否能推导以c打头的符号串,即它们的首符集是什么。若c是Ap的首符集的元素,且不在Bq的首符集中,则选择S Ap往下推导。反之,若c在Bq的首符集中,不在Ap的首符集中,则选择S Bq往下推导。其它情况为不确定推导或出错。,因此,在推导前有必要求出每个文法符号的首符集。,一.首符集,后继符集与选择集的定义:,定义4-1(
5、首符集定义):,设G=(VN ,VT ,P,S)是上下文无关文法,是G的任一符号串,则有:,即: FIRST()是从出发推导出的所有符号串首终结符或可能的构成的集合。,这样在文法 G2中,关于S的两个产生式虽然都以非终结符开始,但它们右部符号串可以推导出首符集合互不相交,因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。,例5.3:,若有文法G3S:SaAS dA bASA若有输入串W=abd。考察自顶向下的推导过程。,解:,相应语法树为右图:,当文法中有空产生式时,如例:,小 结:,由此可以看出,当某一非终结符的产生式中含有空产生
6、式时,它的非空产生式右部的首符号集两两不相交,并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交,则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合为: (定义5.2),定义5.2:,设G=(VN , VT ,P,S)是上下文无关文法,AVN的后继符集合为:,定义5.3:,定义选择符集合SELECT如下: 对于给出上下文无关文法的产生式A,AVN,V*,则,(一) 求FIRST(X)的算法 对每一文法符号X(VNVT),求FIRST(X).(a)若XVT,则令FIRST(X)=X;(b)若XVN,且有产生式Xa.,(aVT),则令aFIRST(X);(c) 若XVN,有
7、X,则令 FIRST(X);(d)若 XVN, y1, y2,.yi都VN,且有产生式X y1 y2.yn,三种集合的构造算法:,注:三种集合均为终结符集,(二)求 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)中所有非元素加入到FIR
8、ST()中,即 FIRST( )=FIRST(x1)- ; 若FIRST(x1)包含有,则把FIRST(x2)的所有非元素加入到 FIRST()中,即FIRST()=FIRST() (FIRST(x2)-); 若FIRST(x1)和FIRST(x2)都包含有 ,则把FIRST(x3)的所有 非元素加到FIRST()中; 照此方法继续,一直到考察到xn。 2.若FIRST(xi ),i= 1,2,n;即每个FIRST(xi )中都有。则将加 到FIRST()中。特别地, 若 = ,则FIRST()=.,(三) 求FOLLOW(A)的算法(A VN):,(a)对文法开始符号S,令# FOLLOW(
9、S).(b)若BA是一个产生式,则令FIRST()- 属于FOLLOW(A);(c) 若BA是一个产生式,或BA是一个产生 式且有FIRST(),则令FOLLOW(B)是 FOLLOW(A)的子集。即把FOLLOW(B)的所有元素 加入到FOLLOW(A)中。(d)反复使用(b)直到每个非终结符的 FOLLOW集合 不再增加为止。,(四) 求SELECT(A)的算法:,例:有文法:ETE E+TE | TFT T*FT | Fi | ( E )求其三种集合。,解:,FIRST(E)=FIRST(T)=FIRST(F)=i, ( FIRST(E)=+,FIRST(T)=*,FOLLOW(E)=F
10、OLLOW(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(i) =(,例:有文法:ETE E+TE| TFT T*FT| Fi| (E)求其三种集合
11、。,例:设有文法GS:SaAS , Sb , AbA , A ,5.2 LL(1)文法的判别,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)=ba,b 故文法 GS不是LL(1)文法。,当一个文法是LL(1)文法时,则该文法一定能够采用确定的自顶向下的分析方法进行分析。,5.3文法的等价变换,确定的自顶向下分析要求给定语言的文法必须是 LL(1)形式,然而,不一定每个语言都是
12、LL(1)文法,对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是我们讨论的主要问题。由LL(1)文法的定义可知若文法中含有左递归或含有左公共因子,则该文法肯定不是LL(1)文法,因而,我们设法消除文法中的左递归,提取左公共因子对文法进行等价变换。,更不一般地:,对A 1| 2 | | n提取左公因子为:A A A 1| 2 | | n若在i , j , k中仍含有左公共因子,可再进行提取,这样反复进行提取直到所引进的新非终结符的有关产生式均无左公共因子为止。,结论:1)不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。2)一个文法提取了左公共因子后
13、,只解决了相同左部产生式的右部FIRST集不相交问题。当改写后的文法不含有空产生式,且无左递归时,则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方法进行判断才能确定是否为LL(1)文法。,(2).消除左递归,一个文法含有下列形式的产生式之一时:1)AA , AVN, V*2)AB , BA , A,BVN, ,V*则称该文法是左递归的。然而,一个文法是左递归时,不能采取自顶向下分析法。,消除左递归方法有:a)把直接左递归改写为右递归: 设有文法产生式: AA|. 其中非空, 不以A打头。 可写为:AA AA | 一般情况下,假定关于A的产生式是: AA 1| A 2 | | A
14、 m| 1| 2 | | n 其中, i(1im)均不为空, j(1jn)均不以A打头。 则消除直接左递归后改写为: A 1 A | 2 A | | n A A 1 A | 2 A | | m A | ,例:,有文法G(E):EE +T |T TT*F | F Fi| (E)消除该文法的直接左递归。,解: ETE E+TE| TFT T*FT| Fi| (E),AA|改写为: AA AA | ,b)消除间接左递归:,对于间接左递归的消除需要先将间接左递归变为直接左递归,然后再按a)清除左递归。,以文法G6为例: (1)AaB (2)ABb (3)BAc (4)Bd,用产生式(1),(2)的右部
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第5章 自顶向下语法分析方法ppt课件 向下 语法分析 方法 ppt 课件
链接地址:https://www.31ppt.com/p-1433634.html