编译原理陈火旺版PPT课件.ppt

5 3LR分析方法 LR分析法也是一种 移进 归约 的自底向上语法分析方法 其本质是规范归约 具有以下特点 1 应用面广 能够用LR分析程序识别绝大多数的程序设计语言的语法结构 2 实现效率高 虽构造方法复杂 但是实现 执行 效率高 3 查错准确 LR分析器能够及时发现语法错误并准确指出错误位置 1 LR k 分析方法中L是指自左 Left 向右扫描输入单词串 R指分析过程是最右 Right 推导的逆过程 规范归约 k是指在决定当前分析动作时需向前察看的输入符号个数 LR 0 构造简单 适用文法少 是SLR 1 LR K 的基础 SLR 1 是针对LR 0 的一些问题进行改进 简单的LR 1 方法 LR K 分析能力强 构造复杂 2 一 LR分析器的逻辑结构 3 LR分析器工作过程简介 例 有文法G L 1 L E L 2 L E 3 E a 4 E b 首先应给出LR分析表 4 1 在总控程序的控制下 从左到右扫描输入串根据分析栈和输入符号的情况 查分析表确定分析动作 2 分析表是LR分析器的核心 根据文法构造 它包括动作表 Action 和状态转换表 Goto 两部分 总控程序根据分析表确定分析动作 3 分析栈包括文法符号栈X i 和相应的状态栈S i 两部分 LR分析器通过判断栈顶元素和当前输入符号查分析表确定下步分析动作 5 规范归约的关键是寻找句柄 LR法是根据已 移进 归约 的符号串及即将读入的符号串进行分析 以确定是否有句柄可归约 状态 是对迄今为止的整个分析过程的记录以及对即将扫描的输入串的展望 预测 状态是根据分析表得到的 分析表是由文法构造的 例 S0状态 开始态 表示当前栈中仅有 且即将输入的符号为句首符号 SN状态 接受态 表示当前栈中已归约为开始符号 且即将输入的符号应为 6 2 分析表的组成 1 动作表是一个二维数组 行代表状态 列代表当前的输入符号 数组元素Action Si aj 表示当栈顶状态为Si 输入符号为aj时 所执行的分析动作 共有4种动作 移进 新状态进栈 输入符号进栈 移进 归约 用相应的产生式进行归约 r5 接受 当归约到只剩下文法开始符号且输入串结束时分析成功 acc 出错 当状态栈顶为某一状态下 出现了不该出现的文法符号时 报错 执行移进动作 元素为产生式或产生式编号表示用它进行归约 元素为acc表示接受 元素为空白表示出错 7 2 状态转换表也用一个二维数组表示 行代表分析栈栈顶状态 列代表文法符号 数组元素Goto Si Xj 表示当前栈顶状态为Si 面对文法符号为Xj时 新的栈顶状态 文法符号包括终结符号和非终结符号 8 二 LR分析过程 1 将初始状态S0和输入串的左边界 分别进栈 2 根据栈顶状态Si和当前输入符号a查动作表进行如下工作 移进 若Action Si a 为 移进 则a进符号栈 并查Goto Si a 得到新的状态Sj进状态栈 继续扫描 即下一个输入符号变成当前输入符号 9 接受 若动作表中对应 acc 则分析成功 出错 若动作表中对应空白 则报告错误信息 3 重复以上2的工作直到接受或出错为止 例有文法G L 1 L E L 2 L E 3 E a 4 E b 要求对输入串a b a进行分析 即分析 a b a 为了分析方便 给文法的产生式进行了编号 文法中非终结符有L E终结符有a b 它们共同组成文法符号 首先应给出LR分析表 为了节省空间 在实际应用中 将动作 Action 表和状态转换 Goto 表中关于终结符的各列对应进行合并 10 例如 本来Action S0 a 移进 表示在状态S0下输入a时 执行 移进 动作 而Goto S0 a S3表示在状态S0下遇到a时 新的状态为S3 现在 Action S0 a S3表示在状态S0下输入a时 a移进符号栈 S3移进状态栈 r1 r4表示文法的产生式 1 4 即应采用此产生式进行归约 数字表示新状态的编号 如 Goto S5 L 6表示新状态为S6 11 分析过程 1 L E L 2 L E 3 E a 4 E b 12 三 LR 0 分析表的构造 一 规范句型的活前缀 前缀 符号串的任意首部子串称为符号串的前缀 规范句型的活前缀 规范句型中不含句柄之后任意符号的前缀称为规范句型的活前缀 例有文法G S aAcBeA bA AbB d及规范句型 abbcde 活前缀有 a ab 规范句型 aAbcde的活前缀有 a aA aAb 当前句柄 13 事实上 LR分析过程中 任意时刻均应保证栈中符号串是规范句型的活前缀 即 栈中绝无句柄之后的任何符号 若输入串为一合法的 句子 则栈中符号与剩余输入串就构成一个规范句型 因此识别 产生规范句型的活前缀就是LR分析器的工作过程 为此 我们需要构造可识别文法所有活前缀的有限自动机 为构造识别文法所有活前缀的有限自动机 现定义构成有限自动机中状态的 项目 二 项目 1 定义 对于文法G 其产生式右部添加一个特殊的符号 就构成文法的一个LR 0 项目 简称项目 14 2 例如 对于产生式 S aAcBe 有项目 S aAcBeS a AcBeS aA cBeS aAc BeS aAcB eS aAcBe 项目中圆点的左部表示在分析过程中已入栈的部分 右部表示等待分析识别的部分 用产生式S aAcBe进行的识别已开始 期待输入的符号应为a 可移进项目 用产生式S aAcBe进行识别时 a已经进栈 匹配 待分析A的部分 即期待着后续输入可归约为A 待移进归约项目 产生式S aAcBe右部分析结束 句柄已经形成 可以归约了 可归约项目 每个产生式对应的项目个数等于它右部的长度加1A 的项目为A 每个项目可用一对整数表示 可归约项目的产生式左部为文法开始符号时 该项目称接受项目 15 三 构造识别活前缀的NFA 根据项目的定义 我们可给出文法中所有产生式的项目 而每个项目都为识别活前缀的NFA的一个状态 即文法有多少个项目 它所对应识别活前缀的NFA就有多少个状态 1 NFA的构造方法 1 状态集 由每个项目所对应的状态组成的集合 2 输入字符集合 由文法符号组成 包括 终结符 非终结符和 3 初态 对于文法G S 的拓广文法G S 有项目S S 由于S 仅在第一个产生式的左部出现 所以规定它为初态 4 终态 每个状态均为NFA的终态 活前缀的识别态 16 5 转换函数f 若有项目i为 X x1x2 xi 1 xi xn S aA cBe 项目j为 X x1x2 xi 1xi xi 1 xn S aAc Be 那么 从项目i 状态i 到项目j 状态j 连接一条标记为xi的有向弧 即f i xi j 若xi为非终结符号 则项目i 状态i 与以xi为左部符号的有关项目 状态 之间也有转换 即 若有项目i X A A VN 项目k A A为左部符号的项目中圆点在最左边 则从项目i 状态i 到项目k 状态k 连接一条标记为 的有向弧 即f i k S aAc Be S aAcB e B d 两个项目出自同一个产生式 且项目j的圆点在项目i的基础上后移一个符号的位置 17 2 举例 有文法G E E aA bBA cA dB cB d 改为拓广文法G S S EE aA bBA cA dB cB d 文法G S 的项目有 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA 7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B 13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 每个项目对应一个NFA的状态 S E对应的项目1为初态 2 5 8 10 13 16 18为 句柄识别态 18 可画出NFA的状态图如下 P106 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA 7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B 13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 状态1为初态 其余状态为活前缀的识别态 终态 双圈的为句柄识别态 对应可归约态 第一个产生式对应的可归约态为句子的识别态 接受态 19 四 项目的分类 为了构造分析表 我们根据各项目的特点把项目分成不同类型 分类的原则是根据圆点所在位置和圆点之后是终结符还是非终结符进行的 1 移进项目 圆点之后为终结符的项目 A a V a VT 它对应的状态为移进状态 S aA cBe 2 待约项目 圆点之后为非终结符的项目 A B V B VN 它对应的状态为待约状态 S aAc Be 3 归约项目 圆点之后没有符号 圆点在最后 的项目 A V 它对应的状态为归约状态 S aAcBe 4 接受项目 对于拓广文法G S 有项目S S 它是一个特殊的归约项目 我们称它为接受项目 它所对应的状态为接受状态 进行分析时 对应的动作是把符号a移进符号栈 它表明该状态等待着对非终结符B的分析 此时 已把 分析完毕 已在栈顶 可以按相应的产生式归约 20 五 识别活前缀的DFA 1 方法一 1 求出文法的所有项目 2 按前述的方法构造识别活前缀的NFA 3 将NFA确定化得DFA 例 对拓广文法G S S EE aA bBA cA dB cB d 1 如前所述求所有项目 P105 2 如前所述求NFA P106 3 将NFA确定化 21 S EE aA bBA cA dB cB d 文法G S 的项目有 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA 7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B 13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 返回 22 返回 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA 7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B 13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 23 据NFA可以构造DFA的转换矩阵 初态集 1 的 闭包 状态集 1 3 11 的a弧转换的 闭包 状态集 1 3 11 的b弧转换的 闭包 24 状态转换图表示 P106 对照转换矩阵 下一页 25 与转换图对照 26 2 方法二 求项目集规范族每个项目集对应一个DFA状态 它们的全体称这个文法的项目集规范族 下面给出求各项目集的方法 以便得到识别文法活前缀的DFA 1 求项目集 设I是拓广文法G的任意项目 定义和构造I的闭包CLOSURE I 的方法为 I中的任何项目均属于CLOSURE I 若A B CLOSURE I B VN 则任何B的产生式B 对应的项目B 也属于CLOSURE I 重复 直到CLOSURE I 不再增加项目为止 2 转换函数 从一个状态出发 到达下一个状态的转换函数定义为 GO I X CLOSURE J I为某个项目集对应的状态 X为输入符号X V J 任何形如A x 的项目 A x I 27 构造项目集规范族的算法 P107 BeginC CLOSURE S S REPEATFORC中的每一个项目集I和G 的每个符号XDOIFGO I X 非空且不属于CTHEN把GO I X 放入C族中UNTILC不再增大End 28 3 构造DFA 举例 对拓广文法G S S EE aA bBA cA dB cB d 项目见P105 S E肯定包含在S0中 S E 求CLOSURE S0 E aAE bB E a A A cAA d E b B B cBB d A c A A cAA d B c B B cBB d 与P106所示结果一致 29 六 LR 0 文法 1 项目集的相容性 我们已知 项目有4种类型 但在一个项目集中 不能有以下情况存在 1 移进项目和归约项目并存 2 多个归约项目并存 若并存则不知该移进还是归约 若并存则不知该归约为哪个非终结符 若项目集能满足以上条件 则称为相容的项目集 2 冲突 项目集中含有的项目不符合以上两个条件 则称为项目集中含有冲突 若移进项目和归约项目并存 则称为移进 归约冲突 若多个归约项目并存 则称为归约 归约冲突 3 LR 0 文法 若一个文法G的项目集规范族中的所有项目都是相容的 则称文法G为LR 0 文法 30 七 LR 0 分析表的构造 1 构造方法 对于文法G S 根据其项目集规范族及DFA的GO函数 按以下规则构造LR 0 分析表 1 对于A x Si GO Si x Sj 若x VT 则置Action Si x Sj 2 对于A Si 若A 是G中第k个产生式 则对所有输入符号x VT 包括 均置Action Si x rk 3 若S Si 则置Action Si acc 表示输入串右界符 4 其它情况均置错 对应分析动作为 将x入符号栈 状态Sj进状态栈 对应分析动作为 将状态Sj进状态栈 对应分析动作为 按指定的产生式进行归约 将归约后的非终结符进符号栈 对应分析动作为 报告分析成功 对应分析动作为 报告出错 31 例对文法G S S EE aA bBA cA dB cB d GO Si x Sj 若x VT 置Action Si x