第四章 语法分析——自上而下分析
上一章学习的是词法分析,用正规式描述了单词符号的结构,用有限自动机构造词法分析器。但正规式描述能力是有限的,上下文无关文法适用范围更广一些,是语法分析的基础。语法分析办法分为两类,一类是自上而下分析法,另一类是自下而上分析法。这一章学习的是自上而下分析法,主要内容是如何消除左递归(直接左递归和非直接左递归)、寻找产生式的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集,并不一定会按顺序求。