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

        之前学过的自上而下的分析是递归，这周学习的是自下而上的分析是一种归约的算法，感觉比上一章的难度有所加大，理解起来也比较的困难，在学习的过程中我也遇到过一些困难，在老师和同学的帮助下得到了解决，下面，我将把这一章所所学的内容做一下总结。

   首先规约的基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。自下而上分析过程：边输入单词符号，边归约。其核心问题是识别可归约串。

在这里我要介绍几个规范规约的概念：（附加例题展示具体的判断过程）

1.短语：定义:令G是一个文法，S是文法的开始符号，假定abd是文法G的一个句型

  其中α,β,d∈(VN∪VT)*，A∈VN ，如果有

则b称是句型abd相对于非终结符A的短语。

2.直接短语：特别是，如果有AÞb,则称b是句型abd相对于规则A®b的直接短语。

3.句柄：一个句型的最左直接短语称为该句型的句柄。

用符号栈进行自下而上的语法分析是一个非常重要的方法，其分析过程是自左向右对输入串ω不断向栈中进行移进——归约。

   算符优先分析法也是一种十分重要的分析方法，思路是：定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约。定义两个终结符‘a’与‘b’的优先关系：a =.b表示a的优先性等于b,a>.b表示a的优先性大于b,a<.b表示a的优先性小于b。

   算符文法指的是一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：…QR…。则我们称该文法为算符文法，也称OG文法。

4.算符优先分析算法和设计：句型的一般表示形式：#N1a1N2a2…NnanNn+1#，其中，每个ai都是终结符，Ni是可有可无的非终结符

(2)定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1，

     aj-1<.aj

     aj=. aj+1，aj+1=. aj+2，…，ai-1=. ai

     ai>. ai+1

注意：

出现在左端或右端的非终结符一定属于这个素短语

优先函数的定义：把每个终结符q与两个自然数f(q)与g(q)相对应，使得

若q1<.q2，则f(q1)< g(q2)

若q1 =. q2，则f(q1)= g(q2)

若q1 >. q2，则f(q1) >g(q2)

f称为入栈优先函数，g称为比较优先函数。

(1)优点:便于比较，节省空间；

(2)缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。

LR分析法也是十分重要的：LR分析方法是一种自下而上的分析方法。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。

移进：把(s，a)的下一状态s’=GOTO[s,a] 和输该前缀加上被分析串中未被分析的终结符，就可以构成一个规范句型

只要输入串的入符号a推进栈，下一输入符号变成现行输入符号。

归约：指用某产生式A®b进行归约. 假若b的长度为r， 归约动作是A， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r,A]和文法符号A推进栈.

例题分析：

  活前缀指的特点有：已扫描部分可归约成一个活前缀，意味着扫描过的部分没有错误，该前缀加上被分析串中未被分析的终结符，就可以构成一个规范句型。只要输入串的已扫描部分可归约成一个活前缀，意味着扫描过的部分没有错误。

   LR分析表的构造需要构造识别活前缀的有限自动机，用有限自动机中的状态表示分析表中的状态,、用状态图中的状态之间的转换关系对分析表中的action goto函数等进行定义。 

感悟：

   以上就是我对本章学习主要内容的总结，总结的可能不是太全面，后面的几个点我还没有弄懂，就没有列出。我认为本章的重点就是掌握利用符号栈进行自下而上的语法分析，算符优先算法的设计，以及lr分析法。本章的概念很多，有一些概念我理解的不是很透彻，只是背过了会用但是并不理解，我觉得这样的学习会容易忘，所以还是要多看几遍课本的，注重复习。编译原理的学习真的是越来越难了，很锻炼一个人的逻辑思维能力，我在这方面还是有所欠缺的，以后还需要更加的努力。编译原理这门课真的让我学到了很多，虽然说这是大三下学期重点在考研，但我还是会分出一些时间给自己的专业课的学习的，培养自己的逻辑思维能力，让自己有所提高。