编译原理第七章.ppt

第8章LR k 分析方法 8 1分析方法的逻辑结构及分析过程8 2LR 0 分析表的构造8 3SLR 1 分析表的构造8 4LR 1 分析表的构造8 5LALR 1 分析表的构造 LR k 分析方法是指从左向右扫描和自底向上的语法分析 每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读 一般来说 凡是上下文无关文法描述的程序设计语言都可以用LR方法进行有效的分析 而且还能在分析过程中及时准确地发现输入符号串的语法错误 通常的程序设计语言一般均能由LR 1 文法产生 而且能由LR k 产生的语言也可以由LR 1 文法来产生 因此 我们通常只考虑LR 0 和LR 1 两种情况 在本章中我们先后介绍LR 0 SLR 1 LR 1 和LALR 1 分析方法 8 1LR分析方法的逻辑结构及分析过程 LR方法也是通过求句柄逐步归约进行语法分析 句柄在运算符优先数法中是通过运算符的优先关系而求得的 在LR方法中 则是通过求可归前缀而求得的 1 活前缀与可归前缀 活前缀与可归前缀 符号串的前缀是指符号串的任意首部 包括 空串 若 是含句柄的活前缀 并且每个句柄是 的后缀或本身 则称 是可归规范前缀或可归前缀 含有句柄的活前缀 活前缀不含句柄之右的任何符号 是规范句型的左起部分 到当前句柄为止 如果在其右边加上终结符号串 后就可以成为一个规范句型 S SS CbBAA AabA abB CB DbC aD a对于句子ababab有规范推导 见下面的语法树 S S 例如 设有文法G S 规范句型ababab的活前缀为a 可归前缀为此a 时句柄也是a 规范句型Cbabab的活前缀为C Cb Cba 可归前缀为Cba 此时句柄为a 规范句型CbDbab的活前缀为CbD CbDb 可归前缀为CbDb 此时句柄为Db 规范句型CbBab活前缀为CbB CbBa CbBab 可归前缀为CbBab 此时的句柄为ab 规范句型CbBA的活前缀为CbBA 可归前缀为CbBA 此时亦为CbBA 规范句型S的活前缀为S 可归前缀为S 此时句柄亦为S 又例如 设有文法G A A aBCbB BaCB bC c对于句子abaccb 可归前缀的求法 设某文法有可归前缀 A A Vn若有规则A uu V 则 u也是文法的可归前缀 例如 设有文法G S S aAcA AbbA b 文法的所有可归前缀构成的集合称为文法的可归前缀集 其可归前缀集可用自动机来表示 称之为可归前缀图 从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀 从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀 2 LR分析方法的逻辑结构 LR分析方法的逻辑结构 设有输入串a1a2a3 an LR分析方法的逻辑结构图如下 栈顶 分析栈中每项都包括状态栈Si和文法符号栈xi两部分 LR分析器包括两个部分 一个总控程序和一张分析表 不同文法的LR分析器的总控程序都是一样的 只是分析表不同 因此LR分析表是LR分析方法的核心 总控程序根据具体的分析表来决定起下一步的处理动作 LR分析的基本原理 把每个句柄 某个产生式的右部 的识别过程划分为若干状态 每个状态下 从左向右地识别句柄中的一个符号 每 个状态识别句柄的一部分符号 也就是 在总控程序的控制下 从左到右扫描输入符号串 根据分析栈中的状态和文法符号及当前输入符号 按分析表完成相应的分析工作 由此可见 构造LR分析器的主要工作是构造分析表 LR分析表的组成 LR分析表由分析动作 ACTION 表和状态转换 GOTO 表组成 1 分析动作表 在分析动作表中 其元素由action si aj 来表示 action si aj 表示当前分析栈的状态栈栈顶元素为si 文法符号栈栈顶元素为aj 当前输入符号 时 所执行的动作 这个动作可分为四种 移进 S 归约 r 接受 acc 和出错 error 2 状态转换表 goto si xj 指出栈顶状态为si 文法符号为aj时应转到的下一状态 3 LR分析过程 LR分析步骤 在讲述LR的分析步骤之前 我们假设分析 表已经成功构造 下面我们给出LR分析的具体步骤 将初始状态S0和句子的左界符 分别进分析栈中的状态栈和符号栈 根据栈顶状态和当前输入符号查动作表 然后分别做如下动作 移进 当前输入符号进符号栈 根据状态转换表 得到的新的状态进状态栈 继续扫描 从而下一个符号变成当前输入符号 归约 按某个产生式进行归约 若产生式的右端长度为n 则符号栈顶和状态栈顶n个元素同时相应退栈 归约后的文法符号进符号栈 查状态转换表 得到的新状态进状态栈 接受 分析成功 终止分析 出错 报告出错信息 重复第2步的工作 直到接受或出错 LR分析流程图 P192图8 4 具体分析过程下面我们以具体的例子来说明LR方法的分析过程 设有文法G L 1 L E L2 L E3 E a4 E b 上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成的所有符号串的集合 这里我们直接给出该文法的分析表 P192图8 3 ri表示按第i个产生式进行归约 Si表示把当前输入符号移进符号栈 且第i个状态进状态栈 i表示转第i个状态 即第i个状态进状态栈 表中未填内容的空白则表示分析动作为出错 下面我们以输入串 a b a 为例 具体讲述LR分析过程 可见 a b a 符合所给的文法规则 8 2LR 0 分析表的构造 LR 0 分析是当k 0时的LR k 分析方法 在分析的每一步只要根据当前栈顶状态就能确定 完成何种分析动作 基本概念 项目 对于文法G 其产生式右部带有特殊符号 则称之为文法的一个LR 0 项目 简称项目 有时也称为配置式 特殊符号也可以用 并且要加在产生式右部的任何地方 表示一个位置 项目集 若干个项目组成的集合称为项目集 又称为配置集合 后继符号 项目中紧跟在特殊符号 后面的符号称为该项目的后继符号 后继符号表示下一时刻读到的符号 有如下两种情况 后继符号为终结符号和非终结符号 例如 对应于产生式 E E T 有四个项目 E E TE E TE E TE E T 这一类的后继符号为 E E T的后继符号为E E E T的后继符号为 E E T的后继符号为T 后继符号为空规定 该项目的后继符号为带有 的相应产生式 用来表示下一时刻将按指定的产生式进行归约 后继符号集定义 项目集中诸项目的后继符号所组成的集合称为后继符号集 状态内容分成是基本 BASIC 部分和闭包 CLOSURE 部分 设Si是Sk关于符号X的后继状态 则求BASIC Si 和CLOSURE Si 的方法 1 BASIC Si 的计算 BASIC Si A X A X Sk 2 CLOSURE Si 的计算 BASIC Si CLOSURE Si 若A Y CLOSURE Si 且Y Vn则Y r CLOSURE Si r为符号串 重复 直到CLOSURE Si 不再增加为止 例如 对于文法G S S AA aAbA c设其开始状态为S0 则求S0的状态内容 项目类型项目类型有三类归约项目 移进项目和待归项目 归约项目 A 此时已把分析结束 已在栈顶 从而可按相应的产生式进行归约 移进项目 A X X Vt此时把X移进文法符号栈 待约项目 A X X Vn此时等待从余留的输入符号中进行归约而得到X 项目集的相容性满足以下条件的项目集称为相容的项目集 无移进项目和归约项目并处 无多个归约项目并存 例如 项目集 A B A B 状态描述序列和状态转换图 在某一状态的项目集中 不同的项目 其后 状态描述序列 查看完毕 在状态描述序列中 必须遵守以下规则 不同状态的项目集中 有若干个与前面对应相同的项目 其后继状态与前面相同时 则后继状态相同 例如 有文法G S 1 S A 2 S B 3 A aAb 4 A c 5 B aBb 6 B d 我们先对文法进行拓展 增加一条规则 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBb 6 B d 继符号相同时 则后继状态相同 状态转换图 由上面的状态描述序列可见 其项目集是相容的 查看相容的定义 注意 对于一个文法G 若其状态描述序列中的状态项目集是相容的 则称G为LR 0 文法 LR 0 分析表的构造 首先 设有状态转换函数GO Si X Sj表示当前状态为Si 输入符号为X时的后继状态为Sj LR 0 分析表的构造规则 设有文法G S 则LR 0 分析表的构造规则为 对于A X Si GO Si X Sj 若X Vt 则置action Si X Sj若X Vn 则置goto Si X j 对于A Si 若A 是文法的第j个产生式 则对所有的X Vt 均置action Si X rj 对于S Si 则置action Si acc 其它情况均置出错 LR 0 分析表设有文法G S 则LR 0 分析表的构造规则为 应用举例用上述分析表对输入串 aacbb 进行分析 过程如书表8 6所示 8 3SLR 1 分析表的构造 问题的提出 只有当文法G的每一个状态项目集相容是才为LR 0 文法 当文法的状态项目集不相容时 就会出现不确定的动作 此时LR 0 分析方法就已经无法解决了 SLR 1 方法是一种简单的LR 1 方法 它用从左到右向前看一个符号来解决冲突动作 SLR 1 与LR 1 方法的区别 SLR 1 的向前看的符号是在出现冲突时才确定向前看的符号 而LR 1 方法则是在一开始就确定向前看的符号 SLR 1 分析表的构造方法思想 SLR 1 分析表的构造思想 在构造SLR 1 分析表时 根据不同的向前看符号 将Si中的各项目所对应的动作加以区分 从而即可使冲突动作得到解决 例如 对于状态Si 假设其项目集为Si B A C 其中 是首符号为终结符的符号串 对于归约项目 A C 分别求其Follow A 和Follow C 对于移进项目 B 求其First 若集合Follow A Follow C First 不相交 则对于任何a a Vt 可按如下方法构造分析表就能解决冲突 对于B Si a First 且GO Si a Sj则置 action Si a Sj 对于A Si a Follow A 且A 为文法的第j个产生式 则置 action Si a rj 对于C Si a Follow C 且C 为文法的第k个产生式 则置 action Si a rk 凡不能按上述方法填入的项均置出错 SLR 1 分析表的构造规则 设有文法G S 则SLR 1 分析表的构造规则为 对于A X Si GO Si X Sj 若X Vt 则置action Si X Sj若X Vn 则置goto Si X j 对于归约项目A Si 若A 为文法的第j个产生式则对于任何输入符号a 若a Follow A 则置 action Si a rj 对于S Si 则置action Si acc 其它情况均置出错 对于给定的文法G 若按上述规则所构造的 分析表不含多重定义的元素 则称文法G为SLR 1 文法 SLR 1 分析表 例如 文法G S 为算术表达式的文法 0 S E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 我们可以构造 见书P201图8 8 状态描述序列 其中 S2和S9两个项目集不相容 于是 对于S2有S2 E T T T F 下面求Follow E 于是Follow E 与 不相交 应用举例 利用上述文法G S 的SLR 1 分析表对输入串 i i i 进行分析 8 4LR 1 分析表的构造 问题的提出 设有文法G S 0 S S 1 S CbBA 2 A Aab 3 A ab 4 B C 5 B Db 6 C a 7 D a 由其状态描述序列 见图8 10 可得 项目集 S10 S CbBA A A ab 和项目集 S9 C a D a 都是不相容的 可用LR 1 方法来解决SLR 1 仍然出现的项目集的项目不相容且Follow和First相交的问题 LR 1 分析表构造的思想 只要输入串的已扫描部分可保持可归约成一个活前缀 那就可判定所扫描的部分未出错 LR 1 项目 为解决SLR 1 方法无法解决的问题 我们在LR 0 项目中放置一个向前搜索的符号a 从而组成如下的形式 A a a Follow A 我们把这样的项目称为LR 1 项目 有效项目 若归约项目A 对活前缀r 是有效的 则说明应把符号串 归约为A 即把活前缀 变为 A 1 SLR 0 有效项目 若移进项目A 对活前缀r 是有效的 则说明句柄尚未形成 下一步动作应该是移进 说明 当一个项目出现在几个不同的项目集中时 同一项目可能对好几个活前缀都是有效的 有可能存在这样的情形 在一个项目集中 对同一个活前缀 存在若干项目对它都是有效的 而项目集却不相容 2 LR 1 有效项目 构造LR 1 分析表的思想 对于上述例子的规范句型Cbabab 根据定义 LR 1 项目 D a b 对活前缀r Cba有效 因此 应将栈顶文法符号a归约成D 而不应归约成C 由此可见 在LR 1 分析表的构造过程中 要根据Si的项目集中的各个项目 对活前缀有效情况 来确定相应的动作 状态描述序列 每一个状态也是由一个LR 1 项目集来表示的 每一个项目集都是由若干个对相应的活前缀有效的LR 1 项目组成 Si中的任何LR 1 项目都属于CLOSURE Si 设有项目 A X a CLOSURE Si X Vn则 X b CLOSURE Si V 其中 a为已知 b First 重复 直到CLOSURE Si 不再增加 注意 每一个LR 1 项目与其后继项目有相同的向前的搜索符号 注