第七章__LR分析.ppt

LR分析方法 一种能根据当前分析栈中的符号串 状态 和向右顺序查看输入串k个符号就可唯一确定分析器的动作是移进还是归约以及用哪个产生式归约的自底向上语法分析算法 是一种规范归约的过程 四种技术LR 0 SLR 1 LR 1 LALR 1 第七章LR分析 第七章LR分析 能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器 YACC 7 1LR分析概述 一个LR分析器由3个部分组成 总控程序 分析表 动作 ACTION 状态转换 GOTO 分析栈 文法符号栈 状态栈 7 1LR分析概述 ACTION表告诉分析器 栈顶状态为i 当前输入符号是a时做什么 1 移进 ACTION i a Sj2 归约 ACTION i a rj 若第j条产生式为A 3 接受 ACTION S a acc S为文法起始符 4 报错 ACTION i a errorGOTO表GOTO i A j表示了当前栈顶状态为i 遇到文法符号A时 应转向新状态j 分析表的具体内容及含义 7 1LR分析概述 LR 0 文法能力最弱 理论上最重要以例题6 1为例说明LR 0 分析过程例 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d对输入串abbcde 利用LR分析法进行分析 7 2LR 0 分析 表7 1例6 1文法的LR 0 分析表 Si 移进 将状态i和输入符进栈ri 归约 用第i个产生式归约 同时状态栈与符号栈退出相应个符号 并把GOTO表相应状态和第i个产生式的左部非终结符入栈 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d 分析输入串abbcde StepStates Syms TherestofinputActionGoto10 abbcde s2202 abbcde s43024 abbcde r2goto 2 A 34023 aAbcde s650236 aAbcde r3goto 2 A 36023 aAcde s570235 aAcde s8802358 aAcde r4goto 5 B 7902357 aAcBe s910023579 aAcBe r1goto 0 S 11101 S acc 对输入串abbcde 的LR分析 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d 规范句型中活前缀 可归前缀设 t是一个规范句型 其中 表示句柄 t Vt 如果 u1u2 ur 那么称符号串u1u2 ui 其中1 i r 是句型 t的活前缀 一个规范句型的活前缀可以有多个 但只有u1u2 ur含有完整句柄 将其称为可归前缀 7 2 1活前缀和可归前缀 解 由E i i 的语法树可找出第一个i是句柄 那么 E i t i 因此活前缀为 E E E E i 其中E i是可归前缀 7 2 1活前缀和可归前缀 例 文法G E T E T E TT i E 找规范句型E i i 的活前缀和可归前缀 例题所得结论 活前缀求法 首先画出句型的语法树 并找出句柄 然后 从句型的左边第一个符号开始 取长度分别为1 2 的符号串 直到包含句柄在内的符号串就是该句型所有的活前缀 而可归前缀就是最长的活前缀 注意 所有活前缀都不包括句柄右边的任何符号 7 2 1活前缀和可归前缀 7 2 1活前缀和可归前缀 为了便于LR分析的进行 还需对文法进行扩充 在原文法中增加一产生式S S 其中S为原文法G的起始符 S 为新引进的符号 拓广后文法在任何产生式的右部不出现S 例 拓广文法G E T E T E TT i E 解 引入一个新的开始符号S 使得文法的开始符号所在的规则唯一 这样得到拓广文法如下 S EE T E T E TT i E 可归前缀可以用穷自动机来识别 了解此法即可 主要思路 将文法中的所有符号均看成是有穷自动机的输入 每当一个符号进栈则表示已经识别了该符号 需进行状态转换 当识别出可归前缀时 等价于在栈中已形成句柄 7 2 2识别活前缀的有限自动机 7 2 2识别活前缀的有限自动机 例 文法G S S S 0 S aAcBe 1 A b 2 A Ab 3 B d 4 给出上文法对句子abbcde的可归前缀 构造识别可归前缀的DFA 解 对于句子abbcde可有以下最右推导过程 S S 0 aAcBe 1 aAcd 4 e 1 aAb 3 cd 4 e 1 ab 2 b 3 cd 4 e 1 而规范归约 最左归约 就是上述过程的逆过程 ab 2 b 3 cd 4 e 1 aAb 3 cd 4 e 1 aAcd 4 e 1 aAcBe 1 S 0 S 7 2 2识别活前缀的有限自动机 文法G S S S 0 S aAcBe 1 A b 2 A Ab 3 B d 4 7 2 2识别活前缀的有限自动机 NFA 该例通过用一个句子归约过程中所有活前缀对应的有限自动机 表示识别整个文法活前缀的有限自动机 仅是一个特殊情况 7 2 2识别活前缀的有限自动机 DFA 定义 非终结符的左文 LC A S A V Vt 推论 若有B A 则 LC A LC B 证明 因为 S B A 所以 规定 对拓广文法的开始符号S LC S 7 2 3活前缀及可归前缀的一般计算方法 7 2 3活前缀及可归前缀的一般计算方法 例题G S 0 S S 1 S aAcBe 2 A b 3 A Ab 4 B d写出该文法中所有非终结符不含句柄的活前缀 每个非终结符的左文方程组LC S LC S LC S LC A LC S a LC A a LC B LC S aAc aAc 用正规式表示如下LC S LC S LC A aLC B aAc 例 写出文法G s 包含句柄的活前缀 可归前缀 G S 0 S S 1 S aAcBe 2 A b 3 A Ab 4 B d解 LR 0 C S S LC S S S SLR 0 C S aAcBe LC S aAcBe aAcBe aAcBeLR 0 C A b LC A b a b abLR 0 C A Ab aAbLR 0 C B d aAcd将所求结果展开就得到了所有的活前缀 进一步即可得NFA 7 2 3活前缀及可归前缀的一般计算方法 定义 LR 0 文法产生式的左文 LR 0 C A LC A 根据可归前缀展开后的结果可构造NFA如下 7 2 3活前缀及可归前缀的一般计算方法 7 2 3小结 活前缀与句柄的关系 在文法G S 中 若S A 并将规范句型 的活前缀记为r 则r与句柄有以下关系 1 活前缀已含有句柄的全部符号 表明产生式A 的右部 已出现在栈顶2 活前缀只含句柄的一部分符号表明A 1 2的右部子串 1已出现在栈顶 期待从输入串中看到 2推出的符号3 活前缀不含有句柄的任何符号 此时期望A 的右部所推出的符号串 1 LR 0 项目 item 在右端某一位置有圆点的G的产生式称为项目 例如 S aAd的所有项目为S aAd S a Ad S aA d S aAd 注意 对于A LR 0 项目只有A 7 2 4LR 0 项目集规范族的构造 2 项目的种类 移进项目 后继符号为终结符号 如E E T 待约项目 后继符号为非终结符号 如E E T和S E归约项目 后继符号为空 如E E T 和S E 接受项目 文法开始符号S的归约项目 如S E 7 2 4LR 0 项目集规范族的构造 3 构造识别活前缀的NFA把文法的所有产生式的项目都列出 并使每个项目都为NFA的一个状态 左端含文法识别符号的项目为初态 其余每个状态都为活前缀的识别态 圆点在最后的项目为句柄识别态 含文法起始符的产生式的句柄识别态为句子识别态 状态之间的转换关系按如下规则确定 7 2 4LR 0 项目集规范族的构造 3 构造识别活前缀的NFA 续 1 若i项目为 X X1X2 Xi 1 Xi Xnj项目为 X X1X2 Xi 1Xi Xi 1 Xni项目和j项目出于同一个产生式 对应于NFA为状态j的圆点只落后于状态i的圆点一个符号的位置 那么从状态i到状态j连一条标记为Xi的箭弧 7 2 4LR 0 项目集规范族的构造 7 2 4LR 0 项目集规范族的构造 2 若Xi为非终结符 则也会有以它为左部的有关项目及其相应的状态 如果有项目形如i X A k A 则从状态i画标记为 的箭弧到状态k 3 构造识别活前缀的NFA 续 例题 构造识别文法G活前缀的NFA 3 构造识别活前缀的NFA 续 7 2 4LR 0 项目集规范族的构造 NFA 7 2 4LR 0 项目集规范族的构造 DFA 4 LR 0 项目集规范族的构造构成识别一个文法活前缀的DFA项目集 状态 的全体 称为这个文法的LR 0 项目集规范族 先构造NFA再确定化的方法工作量太大 有无省劲办法 7 2 4LR 0 项目集规范族的构造 因而可以采用闭包运算来计算DFA一个状态的项目集 规律 若状态中包含形如A B 的项目 则形如B 的项目也在此状态内 例如 0状态中项目集为 S E E aA E bB 项目集的闭包运算设I为一项目集 I的闭包运算CLOSURE I 定义如下 I中的每一个项目都属于CLOSURE I 如项目A 1 X 2属于CLOSURE I 且X为非终结符号 则将形式为X 的项目添加到CLOSURE I 中 重复 1 和 2 直到CLOSURE I 封闭为止 7 2 4LR 0 项目集规范族的构造 例 文法G E E E E E T E T T T F T F F E F i 设项目集I E E 求CLOSURE I 根据第2条 将E E T和E T加进CLOSURE I CLOSURE I E E E E T E T 根据第3条 重复计算 直到CLOSURE I 封闭为止 将T T F和T F加进CLOSURE I CLOSURE I E E E E T E T T T F T F 将F E 和F i 加进CLOSURE I 中 CLOSURE I E E E E T E T T T F T F F E F i 至此 CLOSURE I 封闭 解 根据闭包运算的第1条 CLOSURE I E E 项目集的闭包运算 项目集之间的转换函数GO设I是一个项目集 X是任一文法符号 则项目集之间的转换用GO I X 函数表示为 GO I X CLOSURE J 其中J 任何具有 A X 的项目 A X I 即为对项目集I中所有的项目进行读X操作的结果 并将CLOSURE J 称为I的后继项目集 7 2 4LR 0 项目集规范族的构造 例 有项目集I E E E E T 求GO I 解 在I中挑出点后是 的项目 E E T 将点移到 后面得J E E T 对J进行闭包运算得GO I CLOSURE J E E T T F T T F F E F i 用状态图表示为 7 2 4LR 0 项目集规范族的构造 项目集之间的转换函数GO 7 2 4LR 0 项目集规范族的构造 LR 0 项目集规范族的构造步骤 1 置项目S S为初态集的核 然后对核求闭包 Closure S S 得到初态的项目集 2 对初态集或其它所构造的项目集应用转换函数Go I X Closure J 求出新状态J的项目集 3 重复2 直到不出现新的项目集为止 小结 构造识别文法活前缀DFA的三种方法根据形式定义求出活前缀的正规表达式 然后由此正规表达式构造NFA再确定化为DFA 求出文法的所有项目 按一定规则构造识别活前级的NFA再确定化为DFA 把拓广文法的第一个项目 S S 作为初态集的核 通过求核的闭包和转换函数 求出LR 0 项目集规范族 再由转换函数建立状态之间的连接关系得到识别活前缀的DFA 7 2 4LR 0 项目集规范族的构造 5LR 0 分析表的构造假设已构造出LR 0 项目集规范族为C I0 I1 In 其中Ik为项目集的名字 k为状态名 令包含S S项目的集合Ik的下标k为分析器的初始状态 那么LR 0 分析表的ACTION表和GOTO表可按照如下方法构造 7 2 4LR 0 项目集规范族的构造 7 2 4LR 0 项目集规范族的构造 5LR 0 分析表的构造 1 若项目A a 属于Ik 且GO Ik a Ij 其中a为终结符 则置ACTION k a 为 Sj 把状态j和符号a移进栈 2 若项目A 属于Ik 则对任何终结符a 置ACTION k a 为 rj 用文法中第j条产生式A 进行规约 3 若项目S S 属于Ik 则置ACTION k 为 acc 4 若GO Ik A Ij A为非终结符 则置GOTO k A j 5 分析表中凡不能用规则1至4填入信息的空白格均置上 error 例G S 为 S aAcBeA bA AbB d1 构造识别活前缀的DFA2 构造它的LR 0 分析表 3 给出输入符号串abbcde和abbbce的LR 0 分析步骤 LR 0 项目集规范族的构造实例 G S 拓广为 S SS aAcBeA bA AbB d I0 S SS aAcBe I1 S S I2 S a AcBeA bA Ab I3 S aA cBeA A b I4 A b I5 S aAc BeB d I7 S aAcB e I8 B d I9 S aAcBe I6 A Ab S a A b b c B e d G L ab cde G S 的LR 0 分析表 Stepstates Syms TherestofinputA