第4章 LR分析法.ppt

第六章LR分析法 前言LR分析与简单优先分析的异同点相同点 均是移进 归约思想 规范归约不同点 分析范围不同 寻找句柄方法不同 一旦句柄形成LR分析器能立刻查出用哪条产生式归约LR分析法的分类四种LR分析法的异同 Input LR分析程序 Stack Output 分析表action goto 输入串 当前分析器应采取的动作依赖于栈顶与输入字符 分析器的动作 s 栈顶a 当前输入1 若action s a accept 报告成功 若action s a 用产生式A 归约 执行以下动作 2a 文法符号栈与状态栈分别弹出 个符号 2b 文法符号栈中压入A2c Pushgoto s A 其中s 为状态栈弹出符号后的栈顶状态若action s a 移进状态s 将a移入文法符号栈 将s 移入状态栈若action s a 空白 则报错 SP LR分析器工作过程示意图 LR分析概述 一个LR分析器由以下三部分组成 LR分析程序对于同类的LR分析器 分析程序是相同的 分析表是核心 分为动作表 ACTION 和状态转换表 GOTO 分析栈使用两个栈 文法符号栈 状态栈 G S S aABeA Abc bB d输入串abbcde的最右推导如下 S aABe aAde aAbcde abbcde下划线标识的是每一步的句柄 唯一 活前缀 a aA aAB aABe aAd aAb aAbc ab 非活前缀 aAde Abc aAA 移进 归约分析 abbcde 移进 abbcde 移进 abbcde 归约 aAbcde 移进 aAbcde 移进 aAbcde 归约 aAde 移进 aAde 归约 aABe 移进 aABe 归约 S 成功 栈 输入串 动作 注意 栈中所有的串均是活前缀 注意 能归约吗 G S S aAcBeA Ab bB d输入串abbcde的最右推导如下 S aAcBe aAcde aAbcde abbcde下划线标识的是每一步的句柄 唯一 活前缀 a aA aAb aAcBe aAc aAcd 非活前缀 aAA 移进 归约分析 abbcde 移进 abbcde 移进 abbcde 归约 aAbcde 移进 aAbcde 归约 aAcde 移进 aAcde 移进 aAcde 归约 aAcBe 移进 aAcBe 归约 S 成功 栈 输入串 动作 注意 如何知道按哪条产生式归约 LR 0 项集规范族的构造 LR 0 项在文法G中每个产生式的右部适当位置添加一个圆点构成项 例如 对A XYZ对应项A XYZA X YZA XY ZA XYZ 对于A 只有项A 注意 圆点左部表示该句柄已识别部分 右部表示待识别部分 项分类根据圆点所在的位置和圆点后是VT还是VN把项分为以下几种 移进项 形如A a 其中 V a VT待约项 形如A B 其中 V B VN归约项 形如A 其中 V 接受项 形如S S S S为拓广文法 LR 0 项集规范族的构造步骤如下 变为拓广文法构造识别可归前缀的有穷自动机构造LR 0 分析表利用分析表来分析句子 G E E Aa bBA cA dB cB d 构造LR 0 分析表并分析bcccd是否是文法的句子 SLR 1 分析 先看如下文法 S rDD D iD i它是LR 0 文法吗 如何解决冲突 E EE E T TT T F FF E id 构造SLR 1 分析表并分析i i i是否是文法的句子 E Eclosure E E E E T E EkernelitemsE TE E TT T FE TT FT T FF E T FF idF E F id I E E E E T E T T T F T F F E F id goto I E E E E E T goto I T E T T T F goto I F T F goto I F E E E T E T T T F T F F E F id goto I id F id I0 E EI1 E E I6 E E TI9 E E T E E TE E TT T FT T FE TT FT T FI2 E T F E I10 T T F T FT T FF idF E F idI3 T F I7 T T FI11 F E F E I4 F E F idE E TE TI8 F E T T FE E TT FF E F idI5 F id ActionTable GotoTable 冲突的例子 S L RI0 S SI1 S S I6 S L RI9 S L R S RS L RR LL RS RI2 S L RL RL idL RR L L idR LL idR LI3 S R I4 L RI7 L R 问题R LFOLLOW R L RI8 R L shift6L idreducebyR Lshift reduceconflictI5 L id 冲突的例子2 S AaAbI0 S SS BbBaS AaAbA S BbBaB A B 问题FOLLOW A a b FOLLOW B a b areducebyA breducebyA reducebyB reducebyB reduce reduceconflictreduce reduceconflict LR 1 分析 LR 1 项集族的构造S S 属于初始项集中 为向前搜索符 构造LR 1 项集的闭包函数 I的任何项都属于CLOSURE I 中 若有项A B a属于CLOSURE I B 是文法中的产生式 V b FIRST a 则B b也属于CLOSURE I 中 转换函数的构造若A X a属于I则A X a属于GOTO I X 若有A a1 A an可被写为A a1 a2 an 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e 试构造该文法的LR 1 项集族 LR 1 分析表的构造LR 1 项分为 心 LR 0 项 向前搜索符集合 故LR 1 分析表的构造与LR 0 分析表的构造大部分相同 只是对LR 1 归约动作取决于该归约项的向前搜索符集 例1 S AaAbI0 S S I1 S S S BbBaS AaAb A S BbBa I2 S A aAb B A aB bI3 S B bBa I4 S Aa Ab I6 S AaA b I8 S AaAb A bI5 S Bb Ba I7 S BbB a I9 S BbBa B a 例2 S S1 S L R2 S R3 L R4 L id5 R L 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 I10 R L I11 L R R L L R L id I12 L id I13 L R toI6 toI7 toI10 toI11 toI12 toI13 id S L L L R R R id id id R L I4andI11I5andI12I7andI13I8andI10 LR 1 分析表 例2 无移进 归约 归约 归约冲突 所以它是LR 1 文法 S SS AAA Aa a 该文法是否是LR 1 文法 若是给出分析表 L LL MLb aM 该文法是否是LR 1 文法 并说明原因 若是给出分析表 LALR 1 分析 问题的出现 LR 1 分析法适应的文法类广 但它可能引起状态数目的剧烈增长 为克服这一缺点 下面介绍LALR 1 分析 看以下这个例子 S S1 S L R2 S R3 L R4 L id5 R L 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 I411 L R R L L R L id I512 L id I6 S L R R L L R L id I713 L R I810 R L I9 S L R toI6 toI713 S L L L R R id id id R 心相同的状态I4andI11I5andI12I7andI13I8andI10 LALR 1 分析表 例2 无移进 归约 归约 归约冲突 所以它是LALR 1 文法 有关合并同心集的几个问题 同心集是心相同的项合并在一起 超前搜索符集合是他们的和集 合并同心集后 转换函数自动合并 若文法是LR 1 文法 合并同心集后若有冲突只可能是归约 归约冲突 合并同心集后对某些错误发现的时间会产生推迟现象 但错误的出现位置仍是准确的 S SS AaS dAbS cbS BBA cB BcB b 构造下列文法的