确定的自顶向下分析思 编辑原理.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《确定的自顶向下分析思 编辑原理.pdf》由会员分享,可在线阅读,更多相关《确定的自顶向下分析思 编辑原理.pdf(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 单元目录 第四单元自顶向下分析法 4.1 确定的自顶向下分析思想1.确定的自顶向下分析方法确定的自顶向下分析方法 首先要解决从某文法的开始符号出发,对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.例1:若有文法G1S:S pA|qB A cAd|a B dB|c 识别输入串w=pccadd是否是G1S的句子 试探推导过程:S=pA=pcAd=pccAdd=pccadd 试探成功。这个文法有以下两个特点:每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。即每个产生式的右部的开始终结符不同。对于这
2、样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导,因此分析过程是唯一确定的。例2:若有文法G2S:S Ap|Bq A a|cA B b|dB 识别输入串w=ccap是否是G2S的句子,那么试探推出输入串的推导过程为:S=Ap=cAp=ccAp=ccap 试探推导成功。文法的特点是:产生式的右部不全是由终结符开始。如果两个产生式有相同的左部,它们的右部是由不同的终结 符或非终结符开始。文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时,在推导过程中选用哪个产生式不像例5.1文法那样直观,对于W=ccap为输入串时,其第一个符号是c,这时从S出发选择SAp
3、还是选择SBq,需要知道,Ap或Bq它们的开始终结符号集合是什么?因为c是包含在Ap的开始终结符号集合中,且不包含在Bq的开始终结符号集合中,则选择SAp往下进行推导。2.定义定义4.1 设G=(VT,VN,S,P)是上下文无关文法,FIRST()=a|a,aVT,,V*.若,则规定FIRST()。不难求出在例4.2文法G2中FIRST(Ap)=a,c,FIRST(Bq)=b,d,因此有FIRST(Ap)(FIRST(Bq)=。这样文法G中,两个产生式有相同的左部,它们的右部是由不同的终结 符或非终结符开始。但它们右部的符号串可能推导出的First集不相交,因而可以根据当前的输入符号是属于哪个
4、产生式的FIRST集而决定选择相应产生式进行推导,因此仍能构造确定的自顶向下分析。例3:若有文法G3S:SaA|d A bAS|识别输入串w=abd是否是G3S的句子 试探推导出abd的推导过程为:S=aA=abAS=abS=abd 试探推导成功。文法的特点是:文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中,因当前面临输入符号为d,而最左非终结符A的产生式右部的开始符号集合都不包含d,但有,因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号,所以这时选用产生式A往下推导,而当前A后面的符号为S,S产生式右部的开始的终结符号集合包含了d,所以可匹配。当一
5、个文法中相同左部非终结符的右部存在能的情况则必须知道该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。为此,我们定义一个文法非终结符的后跟符号的集合如下:3.定义定义4.2 设G=(VT,VN,S,P)是上下文无关文法,AVN,S是开始符号,FOLLOW(A)=a|SA,且aVT,aFIRST(),VT*,V+.若SA,且,则#FOLLOW(A)。也可定义为:FOLLOW(A)=a|SAa,aVT,若有SA,则规定#FOLLOW(A),这里我们用#作为输入串的结束符,或称为句子括号,如:#输入串#。因此当文法中含有形如:A A 的产生式时,其中AVN,,V*,当,不同时推导出
6、空时,设,则当FIRST()(FIRST()FOLLOW(A)=时,对于非终结符A的替换仍可唯一地确定候选。4.定义定义4.3 综合以上情况可定义选择集合SELECT如下:给定上下文无关文法的产生式A,AVN,V*,若,则SELECT(A)=FIRST(),如果则:SELECT(A)=(FIRST())FOLLOW(A)。5.是否所有的文法都能采用确定的自上而下的分析是否所有的文法都能采用确定的自上而下的分析自上而下的语法分析例4:文法G:ScAdAabAa识别输入串w=cad是否是该文法的句子试探1:推导过程:S=cAd=cabd试探1失败例4:文法G:ScAdAabAa识别输入串w=cad
7、是否该文法的句子试探2:推导过程:S=cAd=cad试探2成功 该文法的特点是:关于A的产生式的不同右部开始符号集合都含有a,因此要替换非终结符A时,对当前输入符为a的情况,不能确定用产生式Aab 的右部还是用Aa的右部去替换。所以导致必须用带回溯的自顶向下分析。自上而下的语法分析例5:GS:SSaSaL=|n=1W=aaaS=Sa=Saa=aaa 但是读输入符是从左向右,无法确定何时永Sa产生式进行推导.这是一个不确定的分析 文法含有左递归,可见一个文法含有左递归时不能用确定的自顶向下分析。例6:GS:SSaSabaL=ab|n=1W=abaaa无法确定何时永Saba产生式进行推导.例4.4
8、4.6都是不确定的自上而下语法分析.文法含有左递归,一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出,例5.4例5.6的文法不能用确定的自顶向下分析,可用带回溯的自顶向下分析。单元目录 第四单元自顶向下分析法 4.4 确定的自顶向下分析方法确定的自顶向下分析方法4.4.1 递归子程序法4.4.2 预测分析方法4.4.1 递归子程序法概述递归子程序法概述 递归子程序法是比较简单直观易于构造的一种语法分析方法。它要求文法满足LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选时能够按LL(1)
9、形式可唯一地确定选择某个候选进行推导。具体的实现方式,识别过程在第2章PL/0的编译程序中已介绍,读者可参考和回顾PL/0编译程序语法分析方法在每个过程中如何识别及各个过程之间的调用关系。由于递归子程序法对每个过程可能存在直接或间接递归调用,所以对某个过程在退出之前可能又被调用,因此有些信息需要保留,通常在入口时需保留某些信息,出口时需恢复。由于递归过程是遵循先进后出规律,所以通常开辟先进后出栈来处理。递归子程序法的缺点是:对文法要求高,必须满足LL(1)文法,当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时,也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 确定的自顶向下分析思 编辑原理 确定 向下 分析 编辑 原理
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内