第四章7-LR(1)文法.ppt

主要内容 LR 1 分析方法 Z EE L E E SL L EL ES idS S Z EE L E E SS idS S 0 E L E S S L L EL EE L E E SS idS S 1 E S S S 2 S 1 S2 Shift Reduce3 即 1 S2 1不成立 Follow E 非SLR 1 文法 LR 0 方法不依赖输入流 直接判定归约 容易出现冲突 SLR 1 方法简单地把非终极符的follow集做为可归约的依据 并不精确 一个非终极符在不同的位置上出现 它所允许的后继符是不同的 而SLR 1 没有加以区分 LR 1 针对不同产生式上的非终极符 分别定义其后继符集 展望符集Reducelookup 减少了移入 归约冲突 任何SLR 1 都一定是LR 1 文法 1 构造文法的LR 1 自动机2 由LR 1 自动机构造LR 1 分析表 Action表和Goto表 3 根据当前状态和输入符号查分析表确定要执行的操作 进行相应的语法分析 LR 1 分析步骤 LR 1 分析方法 LR 1 方法研究的对象是二元组 b 其中 是活前缀 而b是一个输入符号 我们称上述 b 为LR1前缀模式 活前缀 规范活前缀 若规范前缀 不含句柄或含一个句柄并且具有形式 是句柄 则称规范前缀 为规范活前缀 简称活前缀 前缀中若有句柄 则句柄在前缀的最右端 物理含义 在归约过程中 若符号栈中的内容为活前缀 则表示到目前为止 语法正确 可以继续进行移入或归约操作 LR 1 分析方法 LR 1 方法研究的对象是二元组 b 其中 是活前缀 而b是一个输入符号 我们称上述 b 为LR1前缀模式 如果 是文法的归约活前缀 b是 的合法后继续符 则称 b 为LR1归约前缀模式 归约活前缀 移入活前缀 如果活前缀不中不包含简单短语 句柄 则称为移入型活前缀 因为此时只能进行移入操作 不能进行归约操作 归约活前缀 若活前缀 是含句柄的活前缀 即有 且 是句柄 则称活前缀 为归约规范活前缀 即含有句柄的规范活前缀 是可以归约的 不确定活前缀 如果一个活前缀既是移入型的又是归约型的 则称为不确定活前缀 例 S abcS ab则ab既是移入型活前缀 又是归约型活前缀 LR 1 分析方法 LR 1 方法研究的对象是二元组 b 其中 是活前缀 而b是一个输入符号 我们称上述 b 为LR1前缀模式 如果 是文法的归约活前缀 b是 的合法后继续符 则称 b 为LR1归约前缀模式 LR1归约前缀的派生定理 假设 0是拓广产生式的右部 是输入流的结束符 则有 0 p 是LR1归约前缀模式 设 A p b 是LR1归约前缀模式 且A 是q产生式 则 q a 也是LR1归约前缀模式 其中a First b 派生定理的目的是要求得项目集合的闭包CLOSURE IS LR 1 项目 A a LR 0 项目及一个VT 的展望符 输入符 集合 IS LR 1 项目集IS X 目的 产生下一个状态 IS X A X a A X a IS CLOSURE IS IS B b A B a CLOSURE IS B 是产生式 b First a 目的 产生派生项目 LRSM1的构造算法 初始项目集 ISS CLOSURE Z S 若所有状态都处理完 则结束选一未处理完状态IS 对所有语法符号X VT VN 求ISX 令IS CLOSURE ISX 若IS 不为空 若IS 为新状态 则增加ISIS 把IS 加入LRSM1中 否则为图中某个状态ISj 则在IS和ISj之间增加一条转换边 ISISj转到步骤2 X X 非SLR 1 文法 Z SS L RS RL aRL bR L Z SS L RS RL aRL bR L 非SLR 1 文法 Z SS L RS RL aRL bR L 2状态存在移入 归约冲突归约 Follow R Follow S Follow L 因此不是SLR 1 文法 展望符不一样 做为不同的状态 LR 1 文法 投影函数 2 用来求分析表 2 StateSet VT 2 2 S a Reducej B a S B 是产生式j Shift A a b S 如果LR 1 状态机的任一状态S和输入符a 都使得 2 S a 1 则称文法为LR 1 文法 LR 1 分析表的构造 Action表的构造 Action S a Error若 2 S a Action S Accept若 2 S Reduce1 Action S a Reducej若 2 S a Reducej Action S a Shifti若 2 S a Shift andGoTo S a SiGoTo表的构造 GoTo S X Si若S与Si状态有X转向边 X为非终极符 Action表 输入a时 由0状态转入5状态 R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a Goto表 由0状态归约到R后 转入3状态 R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a Action表 3状态输入 时 按3产生式S R归约 R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a LR 1 驱动程序 LR 1 的驱动程序与SLR 1 的驱动程序是相同的 可共用一个 状态栈符号栈输入串ActionGoTo0aab b S50 5aab b S50 5 5aab b S40 5 5 4aab b R5110 5 5 11aaL b R6100 5 5 10aaR b R4110 5 11aL b R6100 5 10aR b