编译原理第四章语法分析—自上而下分析内容总结

时间:2024-03-23 13:57:46

        语法分析是编译过程的核心部分,这一章我们主要学习了自上而下的分析方法进行语法分析,上一章已经对句法有了一定的了解,下一步就是要学好语法分析,这样才能够在后面的学习中部吃力,语法分析也是编译原理最基础的部分。我觉得学完这一章我们应该学会如何直接消除左递归,寻找产生式的first和follow集,学会判断所给出的文法是不是ll(1)文法,以及构造相应的语法分析表等问题。我的总结主要分为三部分:概念内容的总结,典型例题分析(给出例题的解决方法,体现对知识的运用),一点感悟。

一.概念内容总结:

1.语法分析的过程:自上而下推导,自下而上规约。

2.语法分析的工作:

1.从文法的起始符出发进行句子的推导,即自上而下的分析
2.从句子本身出发,进行归约,看能否把句子规约为到起始符,即自下而上的规约

分析的结果:构造一棵语法树。

3.自上而下的分析面临的问题:

1.文法的左递归问题
2.回溯的不确定性,要求我们将已经完成工作推倒从来,
3.虚假匹配的问题
4.不能准确地确定输入串中出错的位置
5.效率低。
4.消除左递归的公式:

设有产生式

  P→Pα1|Pα2|…|Pαm12|…|β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→α12|…|αn

  则  FIRST(αi)∩FIRST(αj)=Φ (ij)

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

  FIRST(A)∩FOLLOW(A)=Φ

  如果一个文法G满足以上条件,则称该文法GLL(1)文法(1L代表从左到右扫描输入串,第2L代表最左推导,1表示分析时每一步只看1个符号)

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

1.若X终结符,则FIRST(X)={X}
2.若X为非终结符,且有X->a…的产生式,则把a加入到FIRST(X)中;
3.若X->Y…是一个产生式,且Y为非终结符,则把FIRST(Y)-ε加入到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集时遇到了一点难度,对定义的理解不是很透彻,所以理解起来比较的困难,后来在同学的帮助下掌握了一定的方法,找起来也就方便多了。文法的分析是一个比较重要的过程,一定要打好基础,后面的学习才能够顺利的进行。在以后的学习中一定要加强预习复习,编译原理是一门比较重要的学科,好多的学校都对编译原理有一定的要求,所以我觉得学好编译原理是十分重要的。