编译原理LR分析法ppt课件

7自底向上分析 Bottom upParsing LR分析器 1 7 1LR分析器 自底向上分析 Bottom upParsing L left to rightscanning自左向右扫描 R rightmostderivationinreverse最右推导的逆 5 3 4 1LR分析方法概述5 3 4 2LR 0 分析器5 3 4 3SLR 1 分析器5 3 4 4LR 1 分析器5 3 4 5LALR 1 分析器 2 7 1 1LR 0 分析器 例 考虑文法G S S aAA cA d识别accd是否该文法的句子 A c AA cAA ds2 S a AA cAA ds1 S aAs0 start A cA s4 S aA s5 A d s3 A d d A c a c 3 A c AA cAA ds2 S a AA cAA ds1 S aAs0 start A cA s4 S aA s5 A d s3 A d d A c a c s0accd shifts0as1ccd shifts0as1cs2cd shifts0as1cs2cs2d shifts0as1cs2cs2ds3 reduceA ds0as1cs2cs2As4 reduceA cAs0as1cs2As4 reduceA cAs0as1As5 reduceS aAs0S accept G S 1 S aA2 A cA3 A daccd L G S 4 根据上述例子 可以总结如下 一 概念产生式右部符号被识别的多少 在产生式右部加上 指示位置 项目 在文法产生式右部某个位置标有 的产生式 称为文法的一个LR 0 项目 为了叙述方便 形如A 的项目称为归约项目 形如A B 的项目称为待约项目 基本项目 形如A a 的项目称为移进项目 5 定义 有效项目 项目A 1 2对活前缀 1是有效的 如果存在规范推导S Aw 1 2w 若项目A 1 B 2对活前缀 1是有效的 且B 是产生式 则项目B 对活前缀 1也是有效的 据假设 存在一个规范推导S Aw 1B 2w设 2w xw 则对任何B 有规范推导rmS Aw 1B 2w 1Bxw 1 xw所以B 对活前缀 1也是有效的 伽马 艾塔 6 定义 有效项目集 项目集规范族 文法G的某个活前缀 的所有有效项目组成的集合 称为活前缀 的LR 0 有效项目集 文法G的所有有效项目集组成的集合 称为G的LR 0 项目集规范族 7 定义 项目闭包 设I是文法G的一个LR 0 项目集合 I的项目闭包closure I 定义如下 1 I closure I 2 若项目A B closure I 且B 是G的产生式 则项目B closure I 3 closure I 仅包含上述两条规则确定的LR 0 项目 8 定义 转移函数 若I是文法G的一个LR 0 项目集 X是G中的文法符号 定义go I X closure J 其中J A X A X I 称函数go I X 为转移函数 项目A X 称为项目A X 后继 9 二 识别句柄和活前缀的自动机 若文法G VT VN S P 则识别G的句柄的自动机为DFAM VT VN Q G的LR 0 项目集规范族 q0 closure S S F 所有含归约项目的有效项目集组成的集合 go I X 若将所有状态均视为终态 则识别活前缀的自动机DFAM VT VN Q G的LR 0 项目集规范族 q0 closure S S F Q go I X 10 定理 对于拓广文法G 的每一个活前缀 它的有效项目集恰好是从识别G 活前缀的自动机的初态出发 经过 路径所到达的那个状态所代表的项目集合 11 12 A c AA cAA dI4 S a AA cAA dI2 S b BB cBB dI3 B c BB cBB dI5 S SS aAS bBI0 start S S I1 A cA I8 S aA I6 A d I10 A d d A c a b S S bB I7 B cB I6 B d I11 B d d B c c c 识别文法活前缀的DFA 13 LR 0 分析表 14 三 LR分析器的结构和工作过程 LR分析器的结构如图 它的工作过程由算法1描述 输入 a1 ai an LR驱动程序 分析表 输出 栈 smXmsm 1Xm 1 s0 图4 19一个LR分析器的模型 actiongoto 15 算法1 LR分析算法 输入 一个输入串w和文法G的一张LR分析表M 输出 若w L G 输出w的一个自底向上的分析 否则 输出一个出错表示 方法 分别置放s0到栈中和w 到输入缓冲器中 置ip指向w 的第一个符号 repeatforeverbegin令s是栈顶状态且a是ip所指向的符号ifaction s a shifts thenbegin将a和s 先后压入栈内 使ip指向输入串中的下一个符号 end 16 算法1 LR分析算法 elseifaction s a reduceA thenbegin从栈顶弹出2 个符号 令s 是当前栈顶状态 把A和goto s A 先后入栈 输出产生式A endelseifaction s a acceptthenreturnelseerror end 17 7 1 2SLR 1 分析 若有效项目集中存在冲突动作 I X b A B 设当前输入符号为a 1 若a b 则移进 2 若a Follow A 则用A 进行归约 3 若a Follow B 则用B 进行归约 4 其余情况报错 18 SLR分析算法 算法2 构造SLR分析表 输入 一个拓广文法G 输出 对于G 的分析表的action子表和goto子表方法 1 构造G 的LR 0 项目集规范族 2 对于状态Ii的分析动作如下 a 若A aB Ii且go Ii a Ijaction i a shiftj b 若A Ii 对于所有a Follow A action i a reduceA A S c 若S S Ii action i accept3 若go Ii A Ij A VN 则goto i A j4 分析表其余位置为error 19 SLR SLR 1 算法 如果文法G按上述算法构造出的分析表不存在冲突动作 则称G为SLR文法 类似地 不难定义LR 0 文法 若将上述算法的2 b 步中的a Follow A 改为a VT 则由此修改后的算法所定义的文法 称为LR 0 文法 问题 如何定义LR 0 文法 20 例 设文法G E 的产生式为 E E T TT T F FF E id并用SLR 1 方法分析id id id L G E G的拓广文法G E 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F 21 I0 E EE E TE TT T FT FF E F idI1 I0E E E E E TI2 I0T I4T E T T T F I3 I0F I4F I6F T F I4 I0 I4 I6 I7 F E E E TE TT T FT FF E F id I5 I0id I4id I6id I7id F id I6 I1 I8 E E TT T FT FF E F id I7 I2 I9 T T FF E F idI8 I4E F E E E TI9 I6T E E T T T FI10 I7F T T F I11 I8 F E G 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F 22 E E E E T E T T T F T F F E F id E E E E E T T E T T T F F E E E TE TT T FT FF E F id I0 I1 I2 I6 F T F I3 F id id I5 T I2 F I3 id I5 E E TT T FT FF E F id T T FF E F id I7 F E E E T E I8 T E E T T T F I9 F I3 id I5 F T T F I10 id I4 I4 I7 F E I6 I11 23 E E E E T E T T T F T F F E F id E E E E E T T E T T T F F E E E TE TT T FT FF E F id I0 I1 I2 I6 F T F I3 F id id I5 T I2 F I3 id I5 E E TT T FT FF E F id T T FF E F id I7 F E E E T E I8 T E E T T T F I9 F I3 id I5 F T T F I10 id I4 I4 I7 F E I6 I11 24 I0 I1 I6 I9 E T toI7 F toI3 toI4 id toI5 I2 I7 I10 T F toI4 id toI5 I3 F I4 I8 I11 E toI6 T toI4 F toI5 I5 id id 图4 24识别文法 4 22 的活前缀的DFA 25 I1 E E I2 E T I9 E E T E E TT T FT T FI X b A B 若 b FOLLOW A FOLLOW B 则 面对当前读入符号a 状态I的解决方法 1 若a b 则移进 2 若a b 且a FOLLOW A 则用A 进行归约 3 若a b 且a FOLLOW B 则用B 进行归约 4 此外 报错 这种解决方法是比较简单的 因此称作SLR分析 由此构造的分析表 称作SLR分析表 26 对于表达式文法的例子 FOLLOW集如下 I1 E E E E T I2 E T T T F I9 E E T T T F G 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F I1 FOLLOW E I2 FOLLOW E I9 FOLLOW E 可用SLR 1 方法实现 27 表4 11文法 4 22 的SLR分析表 Follow E 28 表 关于id id id的LR分析过程 29 7 1 3LR 1 分析 例 设文法G的产生式为 1 S L R 2 S R 拓广文法G 的LR 0 项目集规范族为 I0 S S S L R S R L R L id R L I1 S S I2 S L R R L I3 S R I4 L R R L L R L id I5 L id I6 S L R R L L R L id I7 L R I8 R L I9 S L R 3 L R 4 L id 5 R L 30 I1 I0 I3 I2 I6 I9 I8 I7 I5 I4 start S R L id id id L L R R 图 识别文法G S 活前缀的DFA G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L 31 LR 1 分析表的构造 问题分析 当识别出句柄时 活前缀中与句柄相关的非终结符号A的后继符号集合 一般是非终结符号A的Follow集合的真子集 例如在前例中 若活前缀L是句柄 则它的后继符号集合为 而Follow L 所以 只有在输入符号为 时 用R L进行归约 而输入符号为 时 移进 可见用Follow集合来消除分析表的多重入口还是略嫌粗糙 32 LR 1 项目 由LR 0 项目和一个lookahead符号组成 A a LR 1 分析法的思想 用活前缀中与句柄相关的非终结符号A的后继符号 亦称为搜索符 集合 而不是Follow A 来避免分析表的多重入口 重新定义项目 使每个项目附带一个向前搜索符 33 定义 LR 1 有效项目 LR 1 项目 A a a VT 对活前缀 是有效的 如果存在规范推导S Aw w且a First w 定理 若LR 1 项目 A B a 对活前缀 是有效的 且B 是一个产生式 则对任何b First a 项目 B b 也是活前缀 的有效项目 34 例 构造文法G S 的LR 1 分析表 LR 1 项目集规范族 I0 S S S L R S R L R L id R L I1 I0S S S I2 I0L S L R R L I3 I0R S R I4 I0 I4 L R R L L R L id I5 I0id I4id L id I6 I2 S L R R L L R L id I7 I4R L R I8 I4L R L I9 I6R S L R I10 I6L I11L R L I11 I6 I11 L R R L L R L id I12 I6id I11id L id I13 I11R L R G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L 35 action goto 状态 id SLR0s4s51231acc2s6r53r24s4s5875r4r46s11s121097r3r38r5r59r110r511s11s12101312r413r3 36 例 构造文法S CCC cC d的LR 1 和LALR分析表 37 S S S CC C cC c dC d c dI0 S C C C cC C d I2 S S I1 S CC I5 S C C C c C C cC C d I6 C cC I9 C c C d I7 d c C c C c dC cC c dC d c dI3 C cC c dI8 C c C d c dI4 d c 图 对于文法的转移函数图 38 文法的LR 1 分析表 39 S SS CCC cCC dI0 S C CC cCC dI2 S S I1 S CC I5 S C C C c CC cCC dI3 C cC I6 C c C d I4 d c c d 40 文法的LR 1 分析表 文法的LALR 1 分析表 41 7 1 4LALR分析表的构造 LR k 方法分析能力很强 但是也耗费大量存储空间 在实际应用中 还须简化 观察图4 27可知 1 从自动机状态等价的角度来看 图中彩色相同的状态是等价的 这些等价状态的特点是 它们的LR 0 有效项目集相同 由于判断是否等价只须比较状态的输出弧 因而不难看出 LR 0 有效项目集相同的状态必定等价 2 对于初始状态I0 其中的有效项目均可从项目 S S 推导出来 对于非初始状态I2 I3 I6 则其中 点在最左端 的项目均可由 点不在最左端 的项目推导出来 观察图也可以得到相同结果 因此在实际存储状态时 可以只存储 点不在最左端 的项目 42 为了叙述方便 引入 同心项 和项目集的 核 的概念 定义 同心项 如果两个LR 1 项目集去掉搜索符之后是相同的 则称这两个项目集具有相同的心 定义 核 对于初始状态I0 有效项目 S S 称为I0的核 而对于非初始状态 则其中 点不在最左端 的有效项目称为它的核 LALR分析法的基本思想 在LR 1 项目集规范族中 合并同心项以减少状态的数目 在存储LR 1 有效项目集时 仅存储其中的核 注意 由于同心项的合并 使项目的搜索符与活前缀的对应关系不唯一 降低了分析器的识别能力 参见以下两例 43 C c C c d C cC c d C d c d I36 I0 Cc c C cC c d I89 C 活前缀Cc 与搜索符 对应 而活前缀c 与搜索符c和d对应 当合并后的自动机识别出活前缀CcC时 若当前的输入符号是c或d LR 1 分析器马上就能发现出错 而LALR分析器此时则不行 必须先归约 得到活前缀CC后才能发现出错 例 在图中 I3和I6 I8和I9合并后得到如下部分状态图 44 问题 LALR分析器识别活前缀的能力是否比LR 1 的差 答 一样 既然都是识别文法活前缀的自动机 它们就是等价的 45 例 考虑文法GS SS aAd bBd aBe bAeA cB c构造G的LR 1 项目集规范族如下 I0 S S S aAd S bBd S aBe S bAe I1 I0S S S I2 I0a S a Ad S a Be A cdB ceI3 I0b S b Bd S b Ae A ceB cd I4 I2A S aA d I5 I2B S aB e I6 I2c A c dB c eI7 I3B S bB d I8 I3A S bA e I9 I3c A c eB c dI10 I4d S aAd I11 I4e S aBe I12 I7d S bBd I13 I8e S bAe 46 若将同心项I6和I9合并 则得到项目集I69 A c d eB c d e该项目集含 归约 归约 冲突 因此 文法G是LR 1 文法 但不是LALR文法 47 一 LALR 1 分析表的原理性构造方法 构造LR 1 项目集族 如果它不存在冲突 就把同心集合并在一起 若合并后不存在归约 归约冲突 则按这个集族构造文法LALR 1 分析表 48 算法 LALR分析表的构造输入 拓广文法G 输出 对于G 的LALR 1 分析表方法 1 构造文法的LR 1 项目集族C I0 I1 In 2 合并C中的同心集 得到C J0 J1 Jm 3 从C 出发构造action表 a 若 A a b Ji且go Ji a Jj置action i a shiftj b 若 A a Ji 置action i a rA A S c 若 S S Ji 置action i accept4 若go Ik A Jj A VN 则goto k A j5 分析表其余位置为error 49 二 LALR分析表的有效构造方法 前算法在构造LALR分析表时 耗费的存储空间与LR 1 算法完全相同 代价还是太大 可以从两个方面改进 1 存储有效项目集时 只存储它们的核 每当需要完整的有效项目集时 再根据核来计算 2 直接生成LALR项目集规范族的核 这是有效构造方法的关键 注意 LALR项目的搜索符一般是与该项目相关的非终结符号的Follow集的子集 这正是LALR分析法比SLR分析法强的原因 50 直接生成LALR项目集规范族的核的方法如下 1 构造LR 0 项目集规范族的核及其自动机 2 为LR 0 项目集规范簇中的每个核项目配上适当的搜索符 核项目的搜索符无非有两种产生途径 若搜索符从其父核传递下来 则称这样的搜索符为 传播的 否则 称搜索符为 自生的 下面算法确定核项目的搜索符是自生的或者是传播的 for有效项目集I的核K中的每一项目B dobeginJ closure B forJ中的每一个项目 A X a do如果a 则有效项目集go I X 中的核项目 A X a 中的搜索符是自生的 否则就是传播的 51 练习 已知文法 请构造LALR分析表 构造文法的LALR 1 项目集的核 LR 0 项目集的核 I0 S SI1 S S I2 S L RI3 S R I4 L RI5 L id I6 S L RI7 L R I8 R L I9 S L R 计算closure S S S S S L R S R L R L id R L G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L 52 表4 15搜索符的传播 表4 16搜索符的计算 53 Thanks 54