《编译原理(清华)第七章LR分析法课件》由会员分享，可在线阅读，更多相关《编译原理(清华)第七章LR分析法课件（94页珍藏版）》请在金锄头文库上搜索。
1、第7章 LR分析法,学习目标： 掌握：LR（0）分析，SLR（1）分析 理解：活前缀，可归前缀 了解：LR(1)、LALR(1)分析思想,7.1LR分析概述 7.2LR(0)分析 7.3SLR(1)分析 7.4LR(1)、LALR(1)分析思想,回顾：自底向上分析实现的基本思想“移进归约”方法 (1) SaAcBe (2)Ab(3)AAb (4) Bd 判断输入串 abbcde# 是否为该文法的句子,LR分析法： 根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K=0）符号就可唯一地确定句柄。 LR(K)的含义： L表示从左到右扫描输入串 R表示最左规约（即最右推导的逆过
2、程） K表示向右查看输入串符号的个数 当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0),SLR(1),LR(1),LALR(1)方法,7.1 LR分析概述,LR分析的特点： 是规范归约 适用范围广，适用于大多数上下文无关文法描述的语言 分析速度快，能准确定位错误 缺点：LR分析器的构造工作量大,LR分析器的组成 总控程序：所有LR分析器总控程序相同。 分析表： 不同文法有不同的分析表 同一文法采用的LR分析器不同，分析表也不同 分析表分为ACTION表（动作表）和GOTO表（状态转换表）。 分析栈： 包括状态栈S和文法符号栈X。 分析表是LR分析器的核心,LR分析表
3、： 列标题为状态，行标题为文法符号,GOTO表示当前状态面临文法符号时应转向的下一个状态。 ACTION表示当前状态面临输入符号时应采取的动作,为了节省空间，将ACTION和GOTO中关于终结符号的各列合并起来,ACTION表中的动作有4种： 移进(Sk)： 把状态k移入状态栈，若当前状态是i，且k=GOTOi,a，把a移入符号栈 归约(rk)： 用第k条产生式进行归约，此时栈顶形成了句柄，文法中第k条产生式为A-，且|=r，归约时从状态栈和符号栈中弹出r个符号，把A移入符号栈，j=GOTOi,A移入状态栈，其中状态i为修改指针后的栈顶状态 接受(acc)： 当符号栈只剩文法开始符S，并且当前
4、输入符为，则分析成功 报错： 当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子,LR分析器的工作过程示意图,状态栈,文法符号栈,栈指针,LR分析器： 在分析的每一步，通用的总控程序按照状态栈栈顶状态i和当前输入符号a查LR分析表，并执行其中ACTION和GOTO规定的操作。,LR分析例（LR(0)分析）,文法GS：(1)S-aAcBe (2)A-b (3)A-Ab (4)B-d,对输入串abbede 进行LR分析,LR(0)分析表为：,对输入串abbcde#的分析过程 (1)S-aAcBe (2)A-b (3)A-Ab (4)B-d,GOTO,ACTION,输入串
5、,符号栈,状态栈,步骤,A,3,3,3,A,3,7,B,7,1,S,1,7.2 LR(0) 分析,使用LR(0)分析表的LR分析器称为LR(0)分析器。 LR(0)分析器在分析的过程中只根据符号栈的内容就能确定句柄，不需要向右查看输入符号 对文法的限制较大，对绝大多数高级语言的语法分析器不适用 构造LR(0)分析表的思想和方法是构造其他LR分析表的基础。,例 文法：(1) SaAcBe (2)Ab (3)AAb (4) Bd 判断输入串 abbcde# 是否为该文法的句子,LR(k)分析法通过活前缀来帮助确定句柄 规范句型的可归约前缀和活前缀(7.2.1) 构造文法的识别活前缀及可归前缀的DF
6、A(7.2.2，7.2.3) 按DFA构造相应分析表状态转换表和动作表(7.2.4) 按分析表进行LR(k)分析(7.2.5),7.2.1 规范句型的可归约前缀和活前缀,什么是可归前缀？ 什么是活前缀？ 可归前缀和活前缀在LR分析中起什么作用？,前缀 如果Z=xy是一符号串，则x是Z的前缀，其中x,y为任意符号串（包括空串 ） 例：abc的前缀有，a，ab，abc。 可归前缀 规范句型中句柄之前包括句柄在内的串称为可归前缀。,例：文法GS，其中产生式后i是其编号 SaAcBe1Ab2AAb3Bd4 输入串abbcde 的最右推导（规范推导）过程： S=aAcBe1 = aAcd4e1=aAb3
7、cd4e1 = ab2b3cd4e1 最左归约(规范归约)过程： ab2b3cd4e1用产生式2归约 aAb3cd4e1用产生式3归约 aAcd4e1用产生式4归约 aAcBe1用产生式1归约 S 可归前缀有：ab2，aAb3，aAcd4，aAcBe1,活前缀 定义： 形成可归前缀之前(包括可归前缀在内)的所有规范句型（符号栈内部分）的前缀称为活前缀。即规范句型的不含句柄右边符号的前缀称为活前缀。 例：规范句型 aAbcde (下划线为句柄)的可归前缀为aAb，活前缀为： ，a，aA，aAb,可归前缀和活前缀在LR分析中的作用 在LR分析过程中，实际上是把活前缀列出放在符号栈中， 一旦在栈中出
8、现可归前缀，即句柄已经形成，就用相应的产生式进行归约， 在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。,7.2.2 识别活前缀的有穷自动机,回顾：有穷自动机一种识别装置 分DFA和NFA,用有穷自动机来识别活前缀和可归前缀 有穷自动机如何构造？ 一个特例：构造识别活前缀和可归前缀的有穷自动机 由文法的产生式构造识别活前缀和可归前缀的有穷自动机的方法,用有穷自动机来识别活前缀和可归前缀 有穷自动机的输入字符：终结符和非终结符 状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识
9、别过的符号串也是活前缀。 终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约,例如：识别可归前缀aAcBe的有穷自动机,构造识别活前缀和可归约前缀的有穷自动机的一个例子： 由句子规范推导的逆过程直观的看出它的活前缀和可归前缀 按活前缀和可归前缀构造识别它们的有穷自动机,例文法G：SaAcBe1Ab2 AAb3Bd4,拓广文法为：S-S0SaAcBe1 Ab2AAb3Bd4,拓广原因：文法开始符S可能出现在产生式的右部，在归约过程中，不能判断是归约到文法的最初开始符，还是归约到在产生式右部出现的开始符，S只在产生式左部出现，确保不会混淆。,S-S0SaAcBe1
10、Ab2AAb3Bd4,输入串abbcde 的最右推导过程： S=S0=aAcBe1 =aAcd4e1 =aAb3cd4e1= ab2b3cd4e1,可归前缀有：ab2，aAb3，aAcd4，aAcBe1， S0,输入串abbcde的可归前缀有： S0，ab2，aAb3，aAcd4，aAcBe1 识别其活前缀和可归前缀的NFA为：,所有的状态都是活前缀的识别状态 终态是句柄的识别态 带“*”号的状态既是句柄识别态又是句子识别态，句子识别态仅有一个,理解识别活前缀和可归前缀的DFA和分析过程的对应,将NFA确定化得到：,S0，ab2，aAb3，aAcd4，aAcBe1,对任何一个上下文无关文法只要
11、构造出它的识别活前缀和可归前缀的有穷自动机，就可以构造其相应的分析表（ACTION表和GOTO表），进行LR分析,S0，ab2，aAb3，aAcd4，aAcBe1,以上示例中构造DFA的方法是通过一个句子的归约过程确定可归前缀，但是： 对于一个复杂的文法，其可归前缀不是如此简单就能计算出来 示例中用一个句子归约过程的所有活前缀和可归前缀构造出的DFA，恰好也是识别整个文法的活前缀和可归前缀的DFA，这仅是一个特殊情况。 对一个上下文无关文法需要求出它的所有活前缀和可归前缀后才能构造其识别该文法活前缀的DFA 由文法的产生式构造识别活前缀和可归前缀的DFA的方法,1. LR(0)项目,文法的识别
12、活前缀的有穷自动机以“项目”作为它的状态 在文法G中每个产生式的右部适当位置添加一个圆点构成项目 例：产生式 UXYZ 对应有4个项目 0 U XYZ1 UX YZ 2 UXY Z3 UXYZ 产生式A只有一个项目A,项目的含义： 圆点在最左部（ U XYZ ）表示希望用产生式的右部归约 圆点的左部（ UX YZ ）表示分析过程中已识别过的部分 圆点的右部（ UX YZ ）表示待识别部分 圆点达到最右边（ UXYZ ）表示句柄已形成，可以进行归约。,LR(0)项目分类 移进项目： 形如A的项目，其中VT, , V*。 即圆点后面为终结符的项目。 分析时把移进符号栈。 待约项目： 形如AB的项目
13、，其中BVN, , V* 。 即圆点后面为非终结符的项目。 表明用产生式A的右部归约时，首先要将B的产生式右部归约为B，对A的右部才能继续进行分析。也就是期待着继续分析过程中首先能归约得到B,归约项目： 形如A的项目，V*,= 对应的项目为A- 即圆点在最右端的项目。 表明该产生式的右部已分析完，句柄已形成，可以把归约为A。 接受项目： 当归约项目为SS，其中S是文法开始符 即对文法开始符的归约项目。 表明输入串可归约为文法开始符，分析结束。 开始项目： 形如SS的项目，其中S是文法开始符。 即拓广文法开始符的产生式圆点在最左边的项目。,2. 构造识别活前缀的有穷自动机,构造识别活前缀的NFA
14、 拓广文法GS为GS，即加入产生式SS 以GS的每个项目为NFA的一个状态，SS为初态，其余每个状态都为活前缀的识别态，所有归约项目为终态(句柄识别态)，SS为接受态 确定状态转换关系： 若有项目i：AX，项目j：AX，则从状态i到状态j连一条标记为X的箭弧。 若XVN，对于X的所有产生式圆点在最左边的状态k:Xr，都从状态i到状态k连一条标记为的箭弧。 用子集法把NFA确定化为DFA,例 文法G：EaA | bB AcA | d BcB | d,拓广文法G：SE EaA | bB AcA|d BcB | d,G的所有LR(0)项目为： 1SE2SE 3EaA 4EaA 5EaA6AcA 7A
15、cA8AcA9Ad 10. Ad11. EbB12. EbB 13. EbB14. BcB15. BcB 16. BcB17. Bd18. Bd,识别G活前缀的NFA,G的所有LR(0)项目为： 1SE2SE 3EaA 4EaA 5EaA6AcA 7AcA8AcA9Ad 10. Ad11. EbB12. EbB EbB14. BcB 15. BcB BcB Bd Bd,识别G活前缀的DFA,通过列出拓广文法的所有项目，进而构造识别活前缀的NFA，再确定化为DFA的方法，工作量较大，不实用 实用的方法是直接构造以项目集为状态的识别活前缀的DFA,7.2.3 构造以LR(0)项目集为状态的识别活前
16、缀的DFA,LR(0)项目集规范族 识别一个文法活前缀的DFA的每个状态都是一个项目集，项目集(状态)的全体称为这个文法的LR(0)项目集规范族。 识别活前缀的DFA的构造 如何构造DFA的一个状态（项目集） 如何由DFA的一个状态求其他状态,1 项目集I的闭包CLOSURE(I) 如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE(I)如下： I的项目均在CLOSURE(I)中； 若AB属于CLOSURE(I)，B VN，则 每一形如Br的项目也属于CLOSURE(I) 重复b）直到CLOSURE(I)不再扩大为止。 说明：圆点后为终结符或在一个产生式的最后，求闭包时不会增加新的项目 例 SE EaA | bB AcA|dBcB | d I= SE 则CLOSURE(I)= SE，EaA，EbB CLOSURE(I)作为DAF的一个状态,2. 状态转换函数GO(I, X) 由DFA的一个状态求其他状态通过状态转换函数 设I为文
