编译原理7：语法分析、消除左递归、FIRST/FOLLOW集合

语法分析基本概念

 

 输入：单词符号串 输出：树形结构或判断

自上而下分析面临的问题

回溯问题和左递归问题

 

 

自上而下分析面临的问题小结

消除直接左递归

为什么只需要消除左递归？

我们需要明确第一个叶子节点的重要含义：第一个节点是语法的起点，所以第一个节点很重要，如果没有第一个叶子节点，那么就永远无法判断此语法是从哪个字符开始的。所以存在左递归的文法，是无法通过程序解析的，这样的程序无法实现。

相反地，右递归有第一个叶子节点，没有最后一个叶子节点。有第一个叶子节点就可以判断语法从哪个字符开始，但是不知道语法在何时结束。

但是，在实际解析中，因为被解析的文本是有限长的，所以右递归一定会停止。除此之外，因为右递归一定有起始符号，所以在解析文本时，一旦遇到非起始符的字符串，也会停止解析。也就是说，右递归能自动保证语法的正确性，而且不会无穷递归。

综上，只有左递归需要消除。

一般化

消除直接左递归示例

消除间接左递归

前提条件：

 方法：

 
消除间接左递归示例

可以按任意顺序排

FIRST集合与提取公共左因子

  提取公共左因子

FOLLOW集合

  

 

 

 
LL(1)文法条件

第一个L表明自顶向下分析时从左向右扫描输入串,第二个L表明分析过程将最左推导,1表明只需向右看一个符号便可决定如何推导,即选择那个产生式进行推导。

FIRST集合的构造

FOLLOW集合的构造

 

 

示例

求follow集：反复求，直至没有更新

小结