编译原理第五章总结——语法分析（自下而上分析）

  上一章学习了自上而下的语法分析，本章总结自下而上语法分析方法。就是从输入串开始，逐步归约，直至归约到文法的开始符号。

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

  对于规范归约，要清楚短语，直接短语，最左直接短语的含义。对于一个从开始符号推导出来的句型，短语由非终结符推导来，直接短语由非终结符一步推导出来的，最左直接短语是语法树中最左分支。一个句型的最左直接短语称为该句型的句柄。

  算符优先法思想：定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约。

  定义两个终结符‘a’与‘b’的优先关系

         a=.b   表示a的优先性等于b

         a>.b   表示a的优先性大于b

         a<.b   表示a的优先性小于b 

   一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：

…QR…   则我们称该文法为算符文法，也称OG文法。

  构造算符关系优先表：

  

(1)通过检查产生式的每一个候选式可以找出满足a=.b

  （即P→…ab…或P→…aQb…的产生式）

(2)为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)

(3)构造集合FIRSTVT(P)的算法

         按其定义，可用下面两条规则来构造集合FIRSTVT(P)：

         ① 若有产生式P→a…或P→Qa…，

                   则aÎFIRSTVT(P)；

         ② 若aÎFIRSTVT(Q)，且有产生式P→Q…，

                   则aÎFIRSTVT(P)。

(4)同理构造构造集合LASTVT(P)的算法

(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。

  LR分析方法是一种自下而上的分析方法。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程（归约过程中找句柄）。

动作表：

                   ACTION[s，a]：

                   当状态s面临输入符号a时，应采取什么动作 四种动作：移进，归约，接受，报错。

状态转换表：

                   GOTO[s，X]：

                   状态s面对文法符号X时，下一状态是什么

  LR分析过程：

     活前缀是指规范句型的一个前缀。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0)项目。能够把识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA的项目集的全体称为这个文法的LR(0)项目集规范族。

构造识别该文法所有活前缀的NFA

(1)求出该文法的LR(0)项目

(2)构造识别文法的NFA为

         M= (S, ∑, f, S0, Z)

其中

S={s|s是文法G的18个LR(0)项目}

∑={S’,E, A, B, a, b, c, d}

S0= S¢→·E

Z:规定每个状态都是识别活前缀的终态(18个)

课后习题：

  心得体会：本章内容比较多，比较复杂，一些概念性的东西比较好理解。LR分析法根据例题理解也更加深刻，但是对于以前的FIRST集FELLOW集自己掌握的还不是很透彻，以后会多多练习，争取熟练掌握。