编译原理第五章自下而上的语法分析.docx

《编译原理第五章自下而上的语法分析.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自下而上的语法分析ü5.1自下而上的语法分析概览§5.2LR分析概览§5.3LR(0)项目的有穷自动机与LR(0)分析§5.4SLR(1)分析§5.5一般的LR(1)§5.6LALR(1)分析§5.7语法分析器自动生成工具—YACC5.1自下而上语法分析方法：从输入单词序列开始，自左至右逐步进行归约，试图将其归约为文法的开始符号。从输入单词序列开始，以单词做为语法树的叶节点，自底向上地构造语法树。自左至右规约是规范推导的逆过程,所以称之为规范规约。将每次规约的子串称为句柄，规范规约的每一步是从当前的规范句型中将句柄归约为相应的非终结符。5.2LR分析概览LR分析

2、法是一种有效的自下而上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中nL是指自左(Left)向右分析输入单词序列，nR是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，n括号中的k是指在决定当前分析动作时向右看的单词个数。为了描述何时移进，何时规约，现将分析栈中存储的符号串称之为活前缀；????如何识别(符号栈)栈顶的符号组成的符号串是否是可归前缀，是可归前缀就规约，否则移进????分析表指导，分析表如何构造①求文法中的所有可归前缀②识别可归前缀和活前缀③分析表的构造o可以证明一个文法G的所有可归前缀是一个正规集，它

3、可以由DFA加以识别。分析表由动作表和状态转换表组成：动作表(Action)以一个二维数组表示，列代表识别活前缀的状态，行代表当前的输入符号，数组元素Action[i，a]表示所执行的分析动作，即：当前识别活前缀的状态为i，而输入符号为a时所执行的动作。状态转换表用一个二维数组表示，列代表识别活前缀的状态，行代表文法符号，数组元素表示当前识别活前缀的状态为i面对文法符号为X时，应转去的新状态Goto[i,X]。5.3LR(0)项目的有穷自动机与LR(0)分析定义：对于文法G，其产生式的右部添加一个特殊符号“.”就构成文法的一个LR(0)项目，简称项目.1.构造识别活前

4、缀的NFA(续)考虑文法：S’→SS→(S)S

5、ε对应的LR(0)项目的NFA，见下页所示。2.构造识别活前缀的DFAo基于闭包函数CLOSURE(I)以及转移函数GO(I，x)构造识别活前缀的DFA;CLOSURE(I)的定义、GO(I，x)的定义、构造识别活前缀的DFA，CLOSURE(I)是一个LR(0)项目集合。I是一个项目集，x属于VN∪VT，状态转移函数GO(I，x)的定义如下：GO(I，x)=CLOSURE(J)，其中：J是I识别输入符号x后所到达的项目集。3，由识别活前缀的DFA构造LR(0)分析表的方法：1.设状态i、j，若有GO(i，x)=j，对于

6、状态i中的项目Aa.x,若x属于VT,则置Action[i，x]=Sj;（属于终结符就规约）若x属于VN,则置Goto[i，x]=j;（属于非终结符就移近）2.若终态i中含项目S’→S.,则置Action[i,$]=acc($表示输入串结束符);3.其它情况均置错。例：文法A→(A)

7、a对应的LR(0)项目集合的DFA5.4SLR(1)分析算法问题：通常的程序设计语言一般不能满足LR(0)文法的要求。例如：文法：S¢→S，S→(S)S

8、ε对应的LR(0)项目集合的DFA如下图：o从分析表可以发现：表中Action[0,(]出现了多重定义的元素，即冲突。o对于状态0，当

9、输入“（”时，既要进行归约又要进行移进，因而不能做唯一选择，从而发生冲突。o对LR(0)分析的构造算法进行改造，以避免分析表中分析动作的冲突。当分析表出现冲突动作时，观察下一个输入符号是什么，从而确定该采用什么动作。o所以可以这样处理：当下一个输入符号‘(’时，做移进动作，当下一个输入符号‘)’和‘$’时做归约动作。这样，消除冲突的分析表为(SLR(1)分析表)：5.5LR（1）分析算法1.给定文法G[S]:S->SaSb︱c给出句子cacbacb的规范推导，画出该句子的语法推导树，指出该句子的句柄。2.简述SLR(1)分析方法是如何处理LR(0)分析中出现的移进——

10、规约冲突和规约——规约冲突的。3.给定文法G[S]:S->SbA︱AA->a1)造文法G[S]的LR(1)项目的DFA。2)上述文法构造LR(1)分析表。3)写出句子ababa的分析过程。