编译原理第七章ppt课件.ppt

《编译原理第七章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章LR分析法第七章LR分析法7.1LR分析概述7.2LR（0）分析7.3SLR（1）分析7.4LR（1）分析7.5LALR（1）分析7.6二义性文法在LR分析中的应用复习：自底向上分析思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误核心寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法3优先法----ch6算符优先分析根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先级的句柄两个端点符号

2、的优先级要高于句柄外与之相邻的符号的优先级，句柄内相邻符号具有相同的优先级a1…ai-1aj+1…an4状态法---ch7LR分析法根据句柄的形成过程建立状态用状态来描述不同时刻句柄是否形成因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态例如：S→bBB可分解为如下识别状态S→.bBB移进bS→b.BB等待归约出BS→bB.B等待归约出BS→bBB.归约5LR分析法是1965年由Knuth提出的一种自底向上分析方法，它的适用范围很广，很受计算机理论界的重视。自底向上分析法的关

3、键问题是在分析过程中如何确定句柄。LR分析法能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k≥0）符号可唯一确定分析器的动作是移进还是归约和用哪个产生式归约，能唯一地确定句柄。LR（K）表示“从左至右，每步向前（右）查看K个输入符号”。K=0表示不需要向右查看输入符号LR分析法严格执行最左归约，是一种规范归约，这一点与算符优先分析法不同。LR分析法的优点：①对文法限制少，适用范围广。②分析速度快③能准确及时地报错缺点：①构造分析器的工作量较大②K值愈大，实现愈困难本章主要介绍LR分析的基本思想，及

4、当K≤1时，LR分析器的基本构造原理和方法。着重介绍LR（0）、SLR（1）、LALR（1）、LR（1）四种分析器的构造方法。7.1LR分析概述一LR分析器的组成一个LR分析器由3个部分组成：(1)总控程序：也称驱动程序，所有LR分析器的总控程序都是相同的。(2)分析表或分析函数:不同的文法分析表不同；同一个文法采用的LR分析器不同时，分析表也不同。分析表可分为动作表（ACTION）和状态转换表（GOTO）两部分，它们都可用二维数组表示。(3)分析栈：包括文法符号栈和状态栈二LR分析器工作过程LR分析器的动作由栈顶状态和当

5、前输入符号决定。SP输出输入串×××…#总控程序ACTION表GOTO表SnXn┇┇S1X1S0X0SP：栈指针S[i]：状态栈X[i]：文法符号栈ACTION表和GOTO表分别为动作表和状态转换表。GOTO[Si，X]=Sj表示栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。ACTION[Si，a]规定了栈顶状态为Si时遇到输入符号a应执行的动作。动作有4种：(1)移进：把a移入文法符号栈，把Sj=GOTO[Si，a]移入到状态栈。其中i，j表示状态号。(2)归约：当栈顶形成句柄为β时，把β归约为相应的非终结符A（A

6、→β为文法中的产生式）。设β的长度为r（即

7、β

8、=r），则从状态栈和文法符号栈中自顶向下去掉r个符号（即栈指针SP-r），把A移入文法符号栈，Sj=GOTO[Si，A]移进状态栈，Si为修改指针后的栈顶状态。(3)接受acc：文法符号栈中只有开始符S′，输入串只有#，则为分析成功。(4)报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。LR分析器的关键部分是分析表的构造，下面将针对每种不同的LR分析器详细介绍其构造思想及方法。7.2LR（0）分析LR（0）分析表构造的思想和

9、方法是构造其它LR分析表的基础。先引进一些概念和术语：拓广文法：对原文法G[S]增加一产生式S′→S，S′只在左部出现。对文法进行拓广的目的：为了对某些右部含有开始符的文法，在归约过程中能分清是否已归约到文法的最初开始符，还是在文法右部出现的开始符。拓广文法的开始符S′只在左部出现，这样确保不会混淆。可归前缀：如果有S′=〉，为终结符串（或空），含有句柄，且句柄在的后端，称为可归前缀。*R活前缀：把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。定义7.1若S′=〉αAω=〉αβω是文法G中的

10、一个规范推导（β为句柄），如果符号串γ是αβ的前缀，则称γ是G的一个活前缀，γ的右端不超过句柄的末端。*RR例如：G[S]：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→daAbcde是规范句型。因为:S=〉aAcBe=〉aAcde=〉aAbcde从左至右，规范句型aAbcde的活前缀有ε、a