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的首符号不同因此很容易确定用哪个候选式匹配
