语法分析是编译过程的核心部分,这一章我们主要学习了自上而下的分析方法进行语法分析,上一章已经对句法有了一定的了解,下一步就是要学好语法分析,这样才能够在后面的学习中部吃力,语法分析也是编译原理最基础的部分。我觉得学完这一章我们应该学会如何直接消除左递归,寻找产生式的first和follow集,学会判断所给出的文法是不是ll(1)文法,以及构造相应的语法分析表等问题。我的总结主要分为三部分:概念内容的总结,典型例题分析(给出例题的解决方法,体现对知识的运用),一点感悟。
一.概念内容总结:
1.语法分析的过程:自上而下推导,自下而上规约。
2.语法分析的工作:
分析的结果:构造一棵语法树。
3.自上而下的分析面临的问题:
设有产生式
P→Pα1|Pα2|…|Pαm|β1|β2|…|βn
其中每个βi不以P开头,每个αi不为ε
消除P的直接左递归性就是把这些规则改写成:
P→β1P’|β2P’|…|βnP’
P’→α1P’| α2P’|…|αmP’| ε
5.FIRST集:
令文法G是不含左递归的文法,对G的非终结符的候选α,定义它的开始符号(终结首符)集合:
6.follow集
对文法G的任何非终结符A,定义它的后继符号集合:
7.不带回溯的自上而下分析的文法条件(LL(1)文法)
(1)文法不含左递归
(2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即,若
A→α1|α2|…|αn
则 FIRST(αi)∩FIRST(αj)=Φ (i≠j)
(3)对于文法中的每个非终结符A,若它的某个候选首符集包含ε,则
FIRST(A)∩FOLLOW(A)=Φ
如果一个文法G满足以上条件,则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串,第2个L代表最左推导,1表示分析时每一步只看1个符号)
8.预测分析表的构造——FIRST(X)
若X->Y1Y2Y3….YK,是产生式,Y1Y2Y3….Yi-1是非终结符,而且ε属于FIRST (Yj)(1<=j<=i-1),则把FIRST(Yj)-ε加入到FIRST(X)中;如果ε属于所有的FIRST(Yj),则ε加入到FIRST(X)中。
二.典型例题的分析
题型一:消除文法的左递归
思路:1.观察文法的格式,构造出非终结符直接左递归的文法。
2.根据上文中提到的公式对文法进行左递归的消除。
3.当非终结符的顺寻不一样时,构造的文法会不同。
题型二:寻找first和follow集
思路:1.first集指的是该非终结符可以推出的第一个终结符,follow集指的是一个非终结符可以推出他本身后面有一个终结符,紧跟的那个终结符,就是它的follow集的元素。
2.查找的时候一定要仔细,不要漏下。
题型三:判断文法是否为ll(1)文法:
思路:1.先找出文法的first和follow集。
2.根据不带回溯的自上而下分析的文法条件,逐一进行验证即可。
题型四:构造预测分析表:
思路:1.找出非终结符的first和follow集。
2.若该非终结符能够推出对应的终结符,就把该非终结符的表达式写到对应的终结符下边。
3.若first集没有对应的终结符,而这个非终结符能够推出空字符,那么如果该非终结符的follow集含有该终结符,则写在表格上。
三.学习感悟
编译原理的学习难度在逐渐的加大,现在还能跟上老师的进度,但是课后不复习的话,感觉比较容易忘,最好当天学完了就要复习一下,在这一章中,我在找follow集时遇到了一点难度,对定义的理解不是很透彻,所以理解起来比较的困难,后来在同学的帮助下掌握了一定的方法,找起来也就方便多了。文法的分析是一个比较重要的过程,一定要打好基础,后面的学习才能够顺利的进行。在以后的学习中一定要加强预习复习,编译原理是一门比较重要的学科,好多的学校都对编译原理有一定的要求,所以我觉得学好编译原理是十分重要的。