语法分析--自上而下分析

1、第四章语法分析-由上而下分析、第四章语法分析-由上而下分析、高级语言语法结构适合上下无关语法说明，因此我将作为上下文无关文法语法分析的基础。牙齿章节和下一章介绍了编译器配置的几种茄子常见语法分析方法4.1语法分析器功能语法分析是编译过程的关键部分。其任务是根据词法分析识别单词符号字符串分析和判断程序的语法结构是否符合语法规则。下图显示了语法分析器在编译器中的位置。第4章语法分析-自上而下分析、源节目、编译前端、中间、代码、代码最优化、中间、代码、代码生成器、目标节目、符号表、代码生成器位置、第4章语法4.2自上而下分析面临的问题主要是通过示例进行自上而下分析回溯的不确定性要求推翻我们已经完成的

2、工作，为了解决这些问题，必须去掉左递归，去掉回溯。4.3 LL(1)分析4.3.1左递归删除一般来说，假设对P的所有生产式都是PP1| P2| P1m| 1| 2 | | n，如果每个都不相等，并且不是以P开头，那么P就会被删除，在这里，我们将渡边杏受到形式描述消除左递归的算法威胁，最好再举几个茄子例子，然后再理解。范例4 .3:考虑语法：删除SQc|c Q Rb|b R Sa|a左侧递归。解决方案：将终结器与r、q、s对齐。对于r，没有直接左递归。在Q中获取R的相关候选人：Q Sab|ab|b将当前Q也作为S的相关候选人导入，而不直接包含左侧递归。S Sabc|abc|bc|c删除S的直接左

3、递归后，对整个语法S ABCS | BCS | CS ABCS |第4章进行语法分析-自上而下分析，结果：S ABCS | BCS | CS ABCS | 4 . 3 . 2回溯如上所述，要进行由上而下的分析，语法中包括左递归是渡边杏的。g是没有左递归的语法，对于g的所有未结束符号的每个候选项，将结束前缀集FIRST()定义为FIRST()=a| *a，aVT，特别是*的FIRST()。也就是说，FIRST()可以是任何可以派生的开始终结器。如果不是终结点A的所有候选前缀集2不相交(即，A的两个其他候选I和j FIRST(i) FIRST(j)=a请求与输入字符串匹配)，则A可以根据第一个输入

4、符号A正确分配要执行操作的候选。牙齿候选人就是在那个结束的第一集里含有A。如何将语法换成某个结束超集的所有候选超集2，2，2不相交的？方法是提取共同的左系数。例如，假设a的规则是A1| 2|。|n| 1| 2| |m(不要单独启动)，然后A A| 1| 2| |m A | 1 | 2 | | n，第4章语法分析-由上而下分析例如，生成式bBcA|b是FIRST也就是说，B bC C BcA| 4.3.3 LL(1)分析条件假设S是语法G的起始符号。S* A需要# FOLLOW(A)。也就是说，FOLLOW(A)是出现在A之后的所有终结点活动#。判断给定语法是否LL(1)语法的条件是(1)语法不

5、包括左递归。(2)语法中每个非终止子A的每个生成式的候选2 2不相交。也就是说，如果A 1 | 2 |。| n规则：FIRST(i) FIRST(j)=(i j) (3)语法中的每个终结器A，如果包含候选标头集，则为FIRST(A) FLLOW(A)=(a)牙齿分析程序由第一个分组过程组成，每个过程对应于语法的非终止符。这种分析程序称为递归下降分析器。在牙齿部分中，可以使用巴科斯范式(1)闭包显示为大括号* (2) 0n随机重复0到N次，00=。(3)在方括号中显示01。也就是说，是否显示是可选的。4.5预测分析程序使用高级语言递归过程描述递归下降分析器。只有存在实现牙齿过程的编译系统时才有意

6、义。实施LL(1)分析的另一有效方法是使用分析表和堆栈进行协作控制。我们现在介绍的预测分析程序就是这种类型的LL(1)分析器。在牙齿部分，对于给定的语法，必须掌握构成每个非终结器的FIRST和FOLLOW集合。第四章语法分析-由上而下分析，要了解LL(1)预测分析表的结构，请参阅4。5.1预测分析程序工作流程(P76)和4。5.2预测分析表结构(P78)。现在，为了让同学理解，我举几个茄子的例子。范例4 .7对于语法，ete te | T ft * ft | F(E)| I我们不是终结点，而是每个FIRST和FOLLOW集合解决方案(first (e)=(，I follow (e)=)，# i

7、ii(3)如果是FIRST()，则对所有b FOLLOW(A)将A添加到Ma，b。(4)将所有未定义的MA，a“显示错误”4.6 LL(1)在分析中处理错误，第4章语法分析-自上而下分析GS: SSa|Nb|c (1) N Sd|Ne|f (2)S NbS |cS 1 S aS| 2 s替换(2)n ne P begin d 3360 x end x d : x | sy 3360 sy |语法LL(1)创建分析表。解决方案：如果郑智薰终结器仅包含P，X，Y FIRST(Y)，则需要FOLLOW(Y)，如果FOLLOW(Y)=FOLLOE(X)=end，则有LL(1)表。begind3360 end s # p .解决方案：观察句子可以分为发现两部分。1na0n和1ma0m两部分中的符号数N和M没有约束关系。S AB A 1A0 |1a0 B 1B0 |a生产式A 1A0 |1a0的两个候选FIRST(1A0)FIRST(1a0)=1，因此上述语法不是LL(1)语法，第4章语法分析-自上而下分析，示例4中有GS: SaBc | bAB AaAb | b Bb |配置LL(1)