第五章 自下而上的分析

第一部分：

一、自下而上进行语法分析问题

1.移进规约：

基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

2.规约：是指根据文法的产生式规则，把产生式的右部替换成左部符号

2.规范规约：

短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，其中α,β,δ∈(VN∪VT)*，A∈VN ，如果有S*=>αAδ且A+=>β，则β称是句型αβδ相对于非终结符A的短语。

直接短语：如果有A=>β,则称β是句型αβδ相对于规则A->β的直接短语。

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

规范规约：

修剪语法树：使用修剪语法树的方法来加深对自下而上语法分析的理解。

(1)子树：是由该树的某个结点(子树的根)连同它的所有子孙组成。

(2)简单子树：只有单层分支的子树(只有父子两代没有第三代)

        (3) 对语法树有如下结论

①每个句型都有一棵语法树与之对应

②每棵语法树的叶结点自左至右排列就组成一个句型

③每棵子树的叶结点自左至右排列就组成一个短语

   ④每棵简单子树的叶结点自左至右排列就组成一个直接短语

        ⑤每棵最左简单子树的叶结点自左至右排列就组成一个句柄

3.用符号栈进行自上而下的语法分析

“#”的使用：

(1)在分析开始时，将‘#’预先进栈，作为栈底符号

(2)将‘# ’作为输入串的结束符

分析过程：自左向右对输入串ω不断向栈中进行移进——归约

二、算符优先算法

算符优先文法：

构造算符优先构造表：

三、算法优先算法的设计

自下而上分析：

                     移进-归约法：句柄为可归纳串

                     算符优先分析法：最左素短语为可归纳串

素短语：指一个句型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语

最左素短语：处在句型最左端那个素短语成为最左素短语

算法优先分析算法和设计：

四、优先函数

定义：

优先函数的构造方法：

LR分析法：

LR分析方法是一种自下而上的分析方法

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程

LR分析方法是一种适用于一大类上下文无关文法的分析方法

 比较复杂，不适于用手工实现，可借助于YACC/bison实现

 根据归约过程中向前看输入符号串中字符的个数，定义不同的LR(k)分析方法，通常，k=0，1

LR分析法与LL分析法的区别：

LR文法：一个文法，如果能构造出一个所有条目都唯一的分析表

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

非LR文法结构：存在吸进、规约冲突的文法

LR文法肯定是无二义的，二义文法都不是LR文法

LR(0)项目集族和分析表的构造：

活前缀：文法G的活前缀是他的规范句型的前缀，该前缀不超过句柄的右端。特点是该前缀加上被分析串中未被分析的终结符，就可以构成一个规范句型。

第二部分：课后练习

总结：这一章的内容。。。我觉得太难了。。。前两张还听得懂一半，这一章的内容只能懂一点点，博客也不知道怎么写，完全是迷迷糊糊的，题只找了两个最简单的做了做，我应该找同学给我辅导辅导了。。。