编译原理第四章语法分析-自上而下分析.ppt
《编译原理第四章语法分析-自上而下分析.ppt》由会员分享,可在线阅读,更多相关《编译原理第四章语法分析-自上而下分析.ppt(34页珍藏版)》请在三一办公上搜索。
1、第四章 语法分析-自上而下分析,4.1 语法分析器的功能4.2 自上而下分析面临的问题4.3 LL(1)分析法4.4 递归下降分析程序构造4.5 预测分析程序4.6 LL(1)分析中的错误处理,4.1 语法分析器的功能,功能定义:按照文法产生式,识别输入符号串是否为一个句子。技术路线:是否能从文法的开始符号出发推导出这个输入串。或者,建立一颗与输入串相匹配的语法分析树。策略:自上而下分析法,自下而上分析法。,图4.1 语法分析器在编译程序中的地位,接收词法分析器输出的记号串,检查是否合乎语法。报告语法错误,并恢复语法错误,从而可以继续分析。输出是分析树的某种形式。分析时其它任务:将各种记号的信
2、息收入符号表、类型检查和其它语义检查、中间代码的生成,这些放在“前端的其它部分”完成。,4.2 自上而下分析面临的问题,例4.1 假定有文法(1)SxAy(2)A*|*对输入串x*y,构造语法树。构造过程:(1)把S作为根(2)用S的产生式构造子树(3)让输入串指示器IP指向输入串的第一个符号。,(4)调整输入串指示器IP与叶结点进行匹配。(5)如果为非终结符,用A的下一个产生式构建子树。(6)如果匹配成功则结束;否则,回溯到步骤(4)。,自上而下分析法的缺点:是文法的左递归性问题。一个文法是含有左递归的自上而下的分析过程陷入无限循环。如PP。由于有回溯,就会产生一大堆麻烦事情。在上述的自上而
3、下分析过程中,当一个非终结符用某一候选匹配成功时,这种成功可能仅是暂时的。这种虚假现象,我们需要更复杂的回溯技术。一般说,要消除虚假匹配是很困难的。当最终报告分析不成功时,我们不知道输入串中出错的确切位置。,4.3 LL(1)分析法,4.3.1 左递归的消除 4.3.2 消除回溯、提左因子 4.3.3 LL(1)分析条件,左递归的消除,一个简单例子:已知文法:PP|是一个左递归文法,它的等价的非左递归文法为:P P P P|例2.2一般转换规则有:PP1|P2|Pm|1|2|n改写成P1P|2P|nPP1P|2P|mP|其中:i都不以P开头,I不等于,一个反例:文法:SQc|c;QRb|b;R
4、Sa|a虽然不是直接左递归,但S、Q、R都是左递归。消除左递归算法:算法的思想是:首先构造直接左递归;再利用一般转换规则,消除直接左递归化简文法。下面算法在不含PP,也不含在右部产生式时可以消除左递归。,消除一个文法的左递归算法:(1)把文法G的所有非终结符按任一种顺利排列成P1Pn;按此顺序执行;(2)FOR i:=1 TO n DOBEGINFOR j:=1 TO i-1 DO把形如Pj+1Pj 的规则改写成Pj+11|1|k|。其中Pj1|1|k是关于Pj的所有规则;消除关于Pi规则的直接左递归性。END 化简由()所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则。,
5、例子4.3:对4.3文法,它的非终结符排序为R,Q,S。把R代入Q,Q代入S得到:SSabc|abc|bc|c消除左递归后得到:SabcS|bcS|cSSabcS|QSab|ab|b(化简消去)RSa|a(化简后消去)对不同的排列,会有不同形式的无左递归文法,但它们等价。,4.3.2 消除回溯、提左因子,消除回溯的思路:对输入符号a,指派一个A的候选式1与a匹配,而再没有其他候选式i的字符与a匹配。通过提取公共左因子,判断首字符集的差异。首字符集定义:对G的所有非终结符的每个候选,它的首字符集为 FIRST()=a|a,aVT,若*,则规定 FIRST()。,提取公共左因子算法:A1|2|n|
6、1|2|m(其中每个 不以开头)那么可以把这些规则改写成:AA|1|2|m A1|2|n例4.4上述算法的不足:当非终结符A面临输入符号a,且a不属于A的任意候选首符集,但A的某个候选首符集包含时,就一定可以使A自动匹配。这是一种错误。,4.3.3 LL(1)分析条件,定义FOLLOW(A)集合:假定S是文法G的开始符号,对于G的任何非终结符A,我们定义FOLLOW(A)=a|S*Aa,aVT 若S*A,则规定FOLLOW(A)。LL(1)文法的充分必要条件:文法不含左递归。若1|2|n,则FIRST(i)FIRST(j)=(ij)对文法中的每个非终结符A,若它存在某个候选首符集包含,则FIR
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第四 语法分析 自上而下 分析
链接地址:https://www.31ppt.com/p-6599846.html