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

上一章学习的是词法分析，用正规式描述了单词符号的结构，用有限自动机构造词法分析器。但正规式描述能力是有限的，上下文无关文法适用范围更广一些，是语法分析的基础。语法分析办法分为两类，一类是自上而下分析法，另一类是自下而上分析法。这一章学习的是自上而下分析法，主要内容是如何消除左递归（直接左递归和非直接左递归）、寻找产生式的FIRST和FOLLOW集，学会判断所给出的文法是不是LL(1)文法，以及构造相应的语法分析表等问题。

主要知识点概括：

自上而下分析面临的问题

1、文法的左递归问题

2、回溯的不确定性，要求我们将已经完成工作推倒从来，

3、虚假匹配的问题

4、不能准确地确定输入串中出错的位置

5、效率低

左递归问题的解决

假设原式为

      P→Pα|β

可以将P的规则改写为如下非直接左递归形式：

      P→βP'

      P'→αP'|ε

FIRST集：

令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：

 

FOLLOW集：

对文法G的任何非终结符A，定义它的后继符号集合：

具体做法：

1、对于文法的开始符，置#于FOLLOW(S)中

2、若A->αBβ, 则把FIRST (β)-ε加入到FOLLOW(B)中

3、若A->αB 是一个产生式，或 A->αBβ是一个产生式，而β-> ε,则把FOLLOW(A)加入到FOLLOW(B)中

不带回溯的自上而下分析的文法条件（LL(1)文法）

  (1)文法不含左递归

  (2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若

                A→α1|α2|…|αn

  则            

                FIRST(αi)∩FIRST(αj)=Φ (i≠j)

  (3)对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则

                FIRST(A)∩FOLLOW(A)=Φ

如果一个文法G满足以上条件，则称该文法为LL（1）文法。

这里，LL（1）中的第1个L代表从左到右扫描输入串，第2个L代表最左推导，1表示分析时每一步只看1个符号。

预测分析表的构造——FIRST(X)

1、若X终结符，则FIRST(X)={X}

2、若X为非终结符，且有X->a …的产生式，则把a加入到FIRST(X)中；

若X->Y…是一个产生式，且Y为非终结符，则把FIRST (Y)-ε加入到FIRST(X)中；

3、若X->Y1Y2Y3….YK,是产生式， Y1Y2Y3….Yi-1是非终结符，而且ε属于 FIRST (Yj)(1<=j<=i-1),则把FIRST (Yj)-ε加入到FIRST(X)中；如果ε属于所有的FIRST (Yj)，则ε加入到FIRST(X)中。

课后习题分析

习题一

 

这道题比较简单，但是包含本章学习的主要内容的应用。第一小题消除左递归，直接套公式。

第二小题先找出FIRST集和FOLLOW集。FIRST集的定义比较好理解，直接按照定义可以很轻松的找出，主要是FOLLOW集的定义比较难理解，具体做法如下：

1、对于文法的开始符，置#于FOLLOW(S)中

2、若A->αBβ, 则把FIRST (β)-ε加入到FOLLOW(B)中

3、若A->αB 是一个产生式，或 A->αBβ是一个产生式，而β-> ε,则把FOLLOW(A)加入到FOLLOW(B)中

看起来还是比较抽象，需要借助例题去理解和掌握，记住B后边有没有内容分别使用不同的方法。

然后根据LL(1)文法条件判断是否为LL(1)文法，对于这道题可以直接看出是LL(1)文法，复杂的就需要比较FIRST集和FOLLOW集去判断了。

FIRST集和FOLLOW集找出来，只要理解了定义，预测分析表就比较容易写出来了。

习题二

这道题虽然看起来比较复杂，但步骤和例题一是一样的。需要注意的是在求FIRST集的时候需要先求后边的FIRST集，并不一定会按顺序求。