【教学课件】第5章自顶向下的语法分析方法.ppt
《【教学课件】第5章自顶向下的语法分析方法.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第5章自顶向下的语法分析方法.ppt(85页珍藏版)》请在三一办公上搜索。
1、第5章 自顶向下的语法分析方法,语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)。目前语法分析常用的方法有:1、自顶向下(自上而下)分析2、自底向上(自下而上)分析,自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子,若输入串是给定文法的句子,则必能推出,反之必然出错。,回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。,句型、句子、语言的定义 句型:有文法G S,若S x,且x V*则称x是文法G S的句型。符号 表示经过0步或若干步的推导。句子:有文法GS,若S x,且xV
2、T*,则称x是文法G S的句子。例:GS:S0S1,S01可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。,句型的分析 句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。,最左(最右)推导:在推导的任何一步,都是对中的最左(右)非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,句型分析的有关问题 如何选择使用哪个产生式进行推导?假定要被替换的最左非终结符号是V,且左部为V的规则有n条:VA1|A2|An,那么如何确定用哪个右部去替换V呢?如何识别可归约的串?在自下而上的分析方法中,在分析程序工作的
3、每一步,都是从当前串中寻找一个子串,看它是否能归约到文法的某个非终结符号,该子串称为“可归约串”。,5.1 确定的自顶向下分析思想,确定的自顶向下分析方法:首先要解决从某文法的开始符号出发,对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.,这个文法有以下两个特点:每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终 结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导,因此分析过程是唯一确定的。,文法的特点是:产生式的右部不全是由终
4、结符开始。如果两个产生式有相同的左部,它们的右部是由不同的 终结 符或非终结符开始。文法中无空产生式。,对于产生式中相同左部含有非终结符开始的产生式时,在推导过程中选用哪个产生式不像例5.1文法那样直观,对于 W=ccap 为输入串时,其第一个符号是c,这时从S出发选择 SAp 还是选择 SBq,需要知道,Ap或Bq它们的开始终结符号集合是什么?因为c是包含在Ap的开始终结符号集合中,且不包含在Bq的开始终结符号集合中,则选择 SAp 往下进行推导。,S Ap|BqA a|cA B b|dB,一个文法符号串的终结符的首符集定义如下:定义5.1 设G=(VT,VN,S,P)是上下文无关文法FIR
5、ST()=a|a,aVT,,V*若,则规定FIRST()不难求出在例5.2文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d因此有 FIRST(Ap)(FIRST(Bq)=这样文法G中,两个产生式有相同的左部,它们的右部是由不同的终结 符或非终结符开始。但它们右部的符号串可能推导出的First集不相交,因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导,因此仍能构造确定的自顶向下分析。,G2:S Ap|BqA a|cA B b|dB,文法的特点是:文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中,因当前面临输入符号为d,而最
6、左非终结符A的产生式右部的开始符号集合都不包含d,但有,因此对于d 的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号,所以这时选用产生式A往下推导,而当前A后面的符号为S,S产生式右部的开始的终结符号集合包含了d,所以可匹配。,当一个文法中相同左部非终结符的右部存在能 的情况则必须知道该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。为此,我们定义一个文法非终结符的后跟符号的集合如下:,定义5.2:设 G=(VT,VN,S,P)是上下文无关 文法,AVN,S是开始符号FOLLOW(A)=a|S A,且aVT,aFIRST(),VT*,V+若S A,且,则#FOLLOW
7、(A)。也可定义为:FOLLOW(A)=a|S Aa,a VT若有S A,则规定#FOLLOW(A)这里我们用#作为输入串的结束符,或称为句子括号,如:#输入串#。,因此当文法中含有形如:AA的产生式时,其中AVN,,V*,当,不同时推导出空时,设,则当FIRST()(FIRST()FOLLOW(A)=时,对于非终结符A的替换仍可唯一地确定候选。,综合以上情况可定义选择集合SELECT如下:定义5.3 给定上下文无关文法的产生式A,AVN,V*,若,则SELECT(A)=FIRST()如果 则:SELECT(A)=(FIRST())FOLLOW(A),是否所有的文法都能采用确定的自上而下的分析
8、,该文法的特点是:关于A的产生式的不同右部开始符号集合都含有a,因此要替换非终结符A时,对当前输入符为a的情况,不能确定用产生式Aab 的右部还是用Aa的右部去替换。所以导致必须用带回溯的自顶向下分析,,这是一个不确定的分析,文法含有左递归,可见一个文法含有左递归时不能用确定的自顶向下分析,文法含有左递归,一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出,例5.4例5.6的文法不能用确定的自顶向下分析,可用带回溯的自顶向下分析。,5.2 LL(1)文法的定义和判别,由5.1的例1例6可知,一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关,当某个
9、非终结符能推出 时则与该非终结符的后跟符号集合也有关。综合以上两点,即一个文法能否用确定的自顶向下分析与产生式的Select集有关。此外在产生式中不存在左递归。,定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的两个不同产生式,A,A,满足SELECT(A)SELECT(A)=其中,不同时能,LL(1)文法的定义,LL(1)文法的含义:第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向右看一个输入符号便可 决定选择哪个产生式。,例:判断下列文法是否是LL(1)文法,G:SaA Sd AbAS A,解:select(SaA)=a select(S d
10、)=d select(SaA)select(S d)=select(AbAS)=b select(A)=First()-Follow(A)=Follow(A)=a,d,#select(AbAS)select(A)=,所以,该文法是LL(1)文法。,例:判断下列文法是否是LL(1)文法,文法G S为:SaASSbAbAA,例 文法G S为:SaASSbAbAA则 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b 因此,该文法不是LL(
11、1)文法,因而也就不可能用确定的自顶向下分析。,LL(1)文法的判别,当我们需选用自顶向下分析技术时,首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合,进而判别文法是否为LL(1)文法。,4、若XVN;Y1,Y2,YiVN,且有产生式XY1 Y2 Yn;当Y1 Y2 Yi-1都 时,(其中1in),则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。,5、当(4)中所有Yi,(i=1,2,n),则FIRST(X)=(FIRST(Y1))(FIRST(Y2))(F
12、IRST(Yn)),反复使用上述(2)(5)步直到每个符号的FIRST集合不再增大为止。,例,求每个终结符的First集。,例,文法G S为:SABSbCAAb,BBaDCADCbDaSDc,FIRST(S)=FIRST(A)FIRST(B)b=b,a,FIRST(A)=b=b,FIRST(B)aa,FIRST(C)=FIRST(A)FIRST(D)FIRST(b)=b,a,cFIRST(D)=ac=a,c,也可以由关系图法求文法符号的FIRST集,可作为一种验证。其方法为:(a)每个文法符号对应图中一个结点,对应终结符的结点时用符号本身标记,对应非终结符的结点用FIRST(A)标记。这里A表
13、示非终结符。(b)如果文法中有产生式AX,且,则从对应A的结点到对应X的结点连一条箭弧。(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由是否为某非终结符FIRST集的成员,若是则将加入该非终结符的FIRST集中。,FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c,计算FOLLOW集 根据定义计算 对文法中每一 AVN 计算 FOLLOW(A)(a)设S为文法中开始符号,把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式,则把FIRST(
14、)的非空元素加入 FOLLOW(B)中。如果 则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。,求每个非终结符的Follow集。,解:FOLLOW(S)=#FOLLOW(D)#FOLLOW(A)=(FIRST(B)FOLLOW(S)FIRST(D)a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#,判断它是否是LL(1)文法,每个产生式的SELECT集合计算为:SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC)=
15、FIRST(bC)=bSELECT(A)=(FIRST()-)FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FIRST()-)FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c,文法G S为:SABSbCAAb,BBaDCADCbDaSDc,由以上计算结果可得相同左部产生式的SELECT交集为:SELECT(SAB)SELECT(SbC)=b,a,
16、#b=b SELECT(A)SELECT(Ab)=a,c,#b=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)b,a,cbb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定义知该文法不是LL(1)文法,因为关于S和C的相同左部其产生式的SELECT集的交集不为空。,非LL(1)文法到LL(1)文法的等价转换,由前面可知:确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而,不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。,若文法中含有直接
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 向下 语法分析 方法
链接地址:https://www.31ppt.com/p-5659046.html