第五章-自下而上分析

一、自下而上分析基本问题

1、归约（其实就是上一章自上而下的分析的逆向）

定义：是指根据文法的产生式规则，把产生式的右部替换成左部符号。

2、规范规约

推出了短语、直接短语、句柄的概念。一个句型的最左直接短语称为该句型的句柄。

规范归约（最左规约）是关于是一个最右推导（规范推导）的逆过程。由于规范句型由最右推导推出的句型，故该句型的句柄右边只含有终结符号。

语法树有五个特征:①每个句型都有一棵语法树与之对应； ②每棵语法树的叶结点自左至右排列就组成一个句型； ③每棵子树的叶结点自左至右排列就组成一个短语； ④每棵简单子树的叶结点自左至右排列就组成一个直接短语； ⑤每棵最左简单子树的叶结点自左至右排列就组成一个句柄。

3、符号栈的使用与语法树的表示

有四类操作：“移进”、“归约”、“接受”、“出错处理”。

任何可归约串的出现必在栈顶，不会在栈的内部。

二、算符优先分析

算符优先分析法不是一种规范归约法。算符优先关系有三种：<. >. =.

1、算符优先文法及优先表构造

怎么构造优先表？首先需要对G的每一个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)。构造这两个集合的目的其实就是方便比较优先级。

2、算符优先分析算法

首先引入“素短语”的概念：至少含有一个终结符，并且除它自身之外不再含有任何更小的素短语。需要注意的是，出现在左端或者右端的非终结符一定属于这个素短语。

三、LR分析法

这里的L表示从左到右扫描输入串，R表示构造一个最右推导的逆过程。

能用LR分析器分析的文法类，包含能用LL（1）分析器分析的全部文法类。

1、LR分析器

核心部分是一张分析表。ACTION[s,a]规定了当状态s面临输入符号a时应采取什么动作。GOTO[s,X]规定了状态s面对文法符号X（终结符或非终结符）时下一个状态是什么。

2、LR文法

LR(k)文法：最多向前看K个的符号就可以决定动作的LR分析器所分析的文法成为LR(k)文法。

非LR结构：存在移进、归约冲突的文法。LR文法肯定是无二义的，一个二义文法决不会是LR的。

3、LR（0）项目集族和LR（0）分析表的构造

活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。在右边增添一些终结符号之后，就可以使它成为一个规范句型。

构造识别一个文法活前缀的DFA的项目集（状态）的全体称为这个文法的LR（0）项目集规范族。

4、LR（0）项目集规范族的构造

通过闭包函数(CLOSURE)来求DFA一个状态的项目集。

5、LR（0）分析表的构造

LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。
只有是LR(０)文法，才能构造相应的LR(0)分析表，才能用LR(0)分析法对句子进行分析。

作业：（不知道怎么调过来了....）