第9讲SLR表案例.ppt

* * * * * * * * * * * * * * * * 3.5 LR分析器 从DFA构造SLR分析表 状态i从Ii构造，它的action函数如下确定： . . . 使用下面规则构造状态i的goto函数： 对所有的非终结符A，如果goto(Ii, A) = Ij, 那么goto[i, A] = j。 3.5 LR分析器 从DFA构造SLR分析表 状态i从Ii构造，它的action函数如下确定： . . . 使用下面规则构造状态i的goto函数： . . . 不能由上面两步定义的条目都置为error。 3.5 LR分析器 从DFA构造SLR分析表 状态i从Ii构造，它的action函数如下确定： . . . 使用下面规则构造状态i的goto函数： . . . 不能由上面两步定义的条目都置为error。 分析器的初始状态是包含[S??·S]的项目集对应的状态。 3.5 LR分析器 例 I2: E ? T· T ? T· * F 因为FOLLOW(E) = {$, +, )}, 所以 action[2, $]=action[2, +]=action[2, )]=r2 action[2, *] = s7 E ? ? E E ? E + T | T T ?T * F | F F ?( E ) | id 3.5 LR分析器 例 SLR(1)文法的描述能力有限 S ? V = E S ? E V ? * E V ? id E ? V I0 : S ? ? · S S ? ·V = E S ? · E V ? · * E V ? · id E ? · V I2 : S ? V · = E E ? V · V 3.5 LR分析器 例 SLR(1)文法的描述能力有限 S ? V = E S ? E V ? * E V ? id E ? V I0 : S ? ? · S S ? ·V = E S ? · E V ? · * E V ? · id E ? · V I2 : S ? V · = E E ? V · V I2第一项目使得 action[2, = ] = s6 3.5 LR分析器 例 SLR(1)文法的描述能力有限 S ? V = E S ? E V ? * E V ? id E ? V I0 : S ? ? · S S ? ·V = E S ? · E V ? · * E V ? · id E ? · V I2 : S ? V · = E E ? V · V 第一项目使得action[2, = ] = s6 第二项目使得 action[2, = ]为按 E?V归约，因为=是 E的一个后继符。 3.5 LR分析器 例 SLR(1)文法的描述能力有限 S ? V = E S ? E V ? * E V ? id E ? V I0 : S ? ? · S S ? ·V = E S ? · E V ? · * E V ? · id E ? · V I2 : S ? V · = E E ? V · V 第一项目使得action[2, = ] = s6 第二项目使得 action[2, = ]为按 E?V归约，因为=是 E的一个后继符。 但是，实际不存在以E=…开始的右句型。 习 题 3.19(a), 3.21(a) * * * * * * * * * * * * * * * * * * * * * * * 中国科大 温故知新 上下文无关文法 自上而下 自下而上 LL(1)文法 2个函数 递归下降预测分析 非递归的预测分析 最左推导 最右推导 ！ LR文法 输入 LR分析程序 输出 栈 LR分析器的模型 action goto sm Xm sm-1 Xm-1 … s0 … a1 ai … an $ 移进-归约分析 归约 移进-归约冲突 归约-归约冲突 句柄 活前缀 右句型的前缀，该前缀不超过最右句柄的右端 1。句柄与某个产生式的右部符号串相同 2。句柄是句型的一个子串 3。把句柄归约成非终结符代表了最右推导逆过程的一步 简单的LR方法（SLR） 规范的LR方法 向前看的LR方法(LALR） 3.5 LR分析器 3.5.3 构造SLR分析表 LR(0)项目（简称项目） 在右部的某个地方加点的产生式 例：A?XYZ对应有四个项目 A ? ·XYZ A ? X·YZ A ? XY·Z A ? XYZ· 例：A??只有一个项目和它对应 A ? · 点的左边代表历史信息，右边代表展望信息。直观地讲，项目表示在分析过程的某一阶段，已经看到了产生式的多大部分，以及希望看到的部