lr分析法.ppt

nhkjk LR分析法 掌握：LR（0）分析，SLR（1）分析 理解：活前缀，可归前缀 了解：LR(1)、LALR(1)分析思想 回顾：自底向上分析实现的基本思想——“移进－归约”方法 (1) S→aAcBe (2)???A→b (3)???A→Ab (4) B→d 判断输入串 abbcde# 是否为该文法的句子 $1 LR分析概述 LR分析法： 根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K=0）符号就可唯一地确定句柄。 LR(K)的含义： L表示从左到右扫描输入串 R表示最左规约（即最右推导的逆过程） K表示向右查看输入串符号的个数 当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0),SLR(1),LR(1),LALR(1)方法 LR分析的特点： 是规范归约 适用范围广，适用于大多数上下文无关文法描述的语言 分析速度快，能准确定位错误 缺点：LR分析器的构造工作量大 LR分析器的组成 总控程序：所有LR分析器总控程序相同。 分析表： 不同文法有不同的分析表 同一文法采用的LR分析器不同，分析表也不同 分析表分为ACTION表（动作表）和GOTO表（状态转换表）。 分析栈： 包括状态栈S和文法符号栈X。 分析表是LR分析器的核心 LR分析表： 行标题为状态，列标题为文法符号 ACTION表中的动作有4种： 移进(Sk)： 把状态k移入状态栈，若当前状态是i，且k=GOTO[i,a]，把a移入符号栈 归约(rk)： 用第k条产生式进行归约，此时栈顶形成了句柄β，文法中第k条产生式为A-β，且|β|=r，归约时从状态栈和符号栈中弹出r个符号，把A移入符号栈，j=GOTO[i,A]移入状态栈，其中状态i为修改指针后的栈顶状态 接受(acc)： 当符号栈只剩文法开始符S，并且当前输入符为‘＃’，则分析成功 报错： 当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子 LR分析器的工作过程示意图 $2 LR(0) 分析 使用LR(0)分析表的LR分析器称为LR(0)分析器。 LR(0)分析器在分析的过程中只根据符号栈的内容就能确定句柄，不需要向右查看输入符号 对文法的限制较大，对绝大多数高级语言的语法分析器不适用 构造LR(0)分析表的思想和方法是构造其他LR分析表的基础。 2.1 规范句型的可归约前缀和活前缀 什么是可归前缀？ 什么是活前缀？ 可归前缀和活前缀在LR分析中起什么作用？ 前缀 如果Z=xy是一符号串，则x是Z的前缀，其中x,y为任意符号串（包括空串ε ） 例：abc的前缀有ε，a，ab，abc。 可归前缀 规范句型中句柄之前包括句柄在内的串称为可归前缀。 活前缀 定义： 形成可归前缀之前(包括可归前缀在内)的所有规范句型的前缀称为活前缀。即规范句型的不含句柄右边符号的前缀称为活前缀。 ? 例：规范句型 aAbcde (下划线为句柄)的可归前缀为aAb，活前缀为： ε，a，aA，aAb 可归前缀和活前缀在LR分析中的作用 在LR分析过程中，实际上是把活前缀列出放在符号栈中， 一旦在栈中出现可归前缀，即句柄已经形成，就用相应的产生式进行归约， 在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。 2.2 识别活前缀的有穷自动机 回顾：有穷自动机——一种识别装置 分DFA和NFA 用有穷自动机来识别活前缀和可归前缀 有穷自动机的输入字符：终结符和非终结符 状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。 终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约 1. LR(0)项目 文法的识别活前缀的有穷自动机以“项目”作为它的状态 在文法G中每个产生式的右部适当位置添加一个圆点构成项目 例：产生式 U→XYZ 对应有4个项目 [0] U→ ? XYZ [1] U→X ? YZ [2] U→XY ? Z [3] U→XYZ ? 产生式A→ε只有一个项目A→? 项目的含义： 圆点在最左部（ U→ ? XYZ ）表示希望用产生式的右部归约 圆点的左部（ U→X ? YZ ）表示分析过程中已识别过的部分 圆点的右部（ U→X ? YZ ）表示待识别部分 圆点达到最右边（ U→XYZ ? ）表示句柄已形成，可以进行归约。 LR(0)项目分类 移进项目： 形如A→α?аβ的项目，其中а∈VT, α,β ∈V*。 即圆点后面为终结符的项目