编译原理第四章中，各种语法分析算法的复杂度与时间效率如何权衡？

本文共计1209个文字，预计阅读时间需要5分钟。

第四章 自上而下的语法分析

4.1 语法分析器的功能

语法分析器，又称解析器，其功能是对单词符号串进行语法分析，识别出各种语法单位，最终生成语法树或中间代码。具体来说，语法分析器对单词符号串进行以下操作：

1. 识别出各类语法单位，如终端符号（单词）、非终端符号（语法规则）、短语结构规则等；

2.生成语法树，展示单词符号串的语法结构；

3.生成中间代码，为编译器后续阶段提供语法结构信息。

第四章自上而下的语法分析4.1语法分析器的功能语法分析器又称分析器对单词符号串进行语法分析识别出各类语法单位最终 第四章 自上而下的语法分析

4.1 语法分析器的功能

语法分析器又称分析器对单词符号串进行语法分析识别出各类语法单位最终判断输入串是否构成语法上正确的“程序”

• 自上而下的分析从文法的开始符号开始向下推导推出句子。
• 自下而上的分析雄踞子开始向上规约归约到文法的开始符号

4.2 自上而下分析面临的问题

回溯

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rQqTrfJN-1647683004320)(assets/markdown-img-paste-20220317165555768.png)]

左递归造成无限循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IXKbA6lx-1647683004320)(assets/markdown-img-paste-20220317165753300.png)]

左公因子造成不确定性

问题

• 文法中含有左递归 P⇒PaP \Rightarrow^ PaP⇒Pa 会造成无限循环
• 回溯
• 从最巡航的候选式开始匹配虚假匹配现象会减少
• 当最终报告分析不成功时难于知道输入串中出错的确切位置
• 由于带回溯的自上而下分析采用了一种穷尽一切可能的试探法因此效率很低代价极高实践上价值不大

4.3 LL(1)分析法

4.3.1 左递归的消除

直接左递归

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jugttZIY-1647683004322)(assets/markdown-img-paste-20220317171137786.png)]

隐含左递归

消除无限循环 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w64KN7Of-1647683004325)(assets/markdown-img-paste-20220317171435399.png)]

隐式左递归确定 S⇒Qc⇒Rbc⇒SabcS\Rightarrow Qc\Rightarrow Rbc\Rightarrow SabcS⇒Qc⇒Rbc⇒Sabc

解决方案 给定一个非终结符号的排序 … 如1, 2, … , 使 → 的产生式中仅含有其中 ≥

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zoIqoL1f-1647683004326)(assets/markdown-img-paste-20220317171819264.png)]

注意要求 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4rHKhm05-1647683004328)(assets/markdown-img-paste-20220317173518687.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UCqZZWEP-1647683004329)(assets/markdown-img-paste-20220317171949781.png)]

例题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bFFhVBvx-1647683004331)(assets/markdown-img-paste-20220317172056521.png)]

1、排序 S,Q,R 2、 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nKNqphGm-1647683004332)(assets/markdown-img-paste-20220317172155155.png)]

因为R->SA A的序号比R小将S替换掉出现了Q继续将Q替换掉然后消除R的直接左递归。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q5HsWy3f-1647683004333)(assets/markdown-img-paste-20220317172649533.png)]

将S排到最后S的产生式右侧不含 R QS是开始符号因此最终的产生式会比较少

但是两种推导都是等价的

推论

• 含有回路的左递归无法消除A⇒AA\Rightarrow^AA⇒A
• 消除左递归与非终结符号的排序无关
• 如果从开始符号依次推导出1, 2, … , 则按其逆序排序时得到的产生式最少

4.3.2消除回溯 提左公因子

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GogOnn0P-1647683004335)(assets/markdown-img-paste-2022031917282676.png)]

• S的两个候选是 xAy和z的首符号不同因此很容易确定用哪个候选式匹配