编译原理教案-lr分析(ppt78)-经营管理(编辑修改稿)

编译原理教案-lr分析(ppt78)-经营管理(编辑修改稿)内容摘要：

cde 移进 023 S5 7） aAc de 移进 0235 S8 9） aAcB e 移进 02357 S9 对输入串 abbcde的 LR分析过程 3） ab bcde 归约 (A→ b) 024 r2 3 5） aAb cde 归约 (A→ Ab) 0236 r3 3 8） aAcd e 归约 (B→ d) 02358 r4 7 10） aAcBe 归约 (S→ aAcBe) 023579 r1 1 状态栈 ACTION GOTO 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8  * 的资料库下载 步骤 符号栈 输入符号串 动作 1） abbcde 移进 0 S2 2） a bbcde 移进 02 S4 4） aA bcde 移进 023 S6 6） aA cde 移进 023 S5 7） aAc de 移进 0235 S8 9） aAcB e 移进 02357 S9 11） S 接受 01 acc 对输入串 abbcde的 LR分析过程 3） ab bcde 归约 (A→ b) 024 r2 3 5） aAb cde 归约 (A→ Ab) 0236 r3 3 8） aAcd e 归约 (B→ d) 02358 r4 7 10） aAcBe 归约 (S→ aAcBe) 023579 r1 1 状态栈 ACTION GOTO 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8  * 的资料库下载 如何构造识别活前缀的有限自动机 • 已经有了活前缀如何构造有限自动机 ? • 活前缀及其可归前缀的一般计算方法 的资料库下载 文法 G[S]： S’ → S[0] S → aAcBe[1] A → b[2] A → Ab[3] B → d[4] 句子 abbcde的可归前缀如下： S[0] ab[1] aAb[3] aAcd[4] aAcBe[1] 构造识别其活前缀及可归前缀的有限自动机如下： 1 0 4 3 8 7 13 12 10 18 2 5 9 14 6 17 15 16 11 10 S a b a A b a A c d a A c B e * 1 * 句子识别态 i 句柄识别态 的资料库下载 1 0 4 3 8 7 13 12 10 18 2 5 9 14 6 17 15 16 11 10 S a b a A b a A c d a A c B e * X 加上开始状态 X 确定化      X 1 3 2 4 6 8 5 9 S a b A b c B e d 7  *  识别活前缀的确定的有限自动机 的资料库下载 活前缀及其可归前缀的一般计算方法 定义：文法 G， AVN, LC(A)={ | S’ A, V*, VT *} 规范推导中在非终结符 A左边所有可能出现的符号串的集合 推论：若文法 G中有产生式 B→ A，则有 LC(A)  LC(B)*{} R*的资料库下载 文法 G’[S]： S’ → S[0] S → aAcBe[1] A → b[2] A → Ab[3] B → d[4] 由前面的定义与推论我们知： LC(S’) = {} LC(S) = LC(S’) *{} LC(A) = LC(S) *{a} LC(A) *{} LC(B) = LC(S) *{aAc} 化简为： [S’] =  [S] = [S’] [A] = [S]a+[A] [B] = [S]aAc 求解方程组可得： [S’] =  [S] =  [A] = a+[A] [B] = aAc [A] = a|[A] [A] = a*=a 这样我们求出了每个 非终结符 在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的 所有前缀 ，也就是在规范归约过程中用句柄归约成该非终结符之前 不包括句柄的活前缀。 的资料库下载 不包括句柄的活前缀 + 句柄 =。 可归前缀。 令 LR(0)C(A→ ) = LC(A)* {} 文法 G’的可归前缀有： LR(0)C(S’ → S) = [S’]*{S} = {S} LR(0)C(S → aAcBe) = [S]*{aAcBe} = {aAcBe} LR(0)C(A → b) = [A]*{b} = {ab} LR(0)C(A → Ab) = [A]*{Ab} = {aAb} LR(0)C(B → d) = [B]*{d} = {aAcd} 总结：如何构造识别文法活前缀的有限自动机。 根据文法算出其可归前缀 根据可归前缀，构造识别文法活前缀的不确定有限自动机 确定化，从而构造出识别文法活前缀的确定的有限自动机 参见课本 P124的例子 的资料库下载 LR分析器的构造 构造识别文法活前缀的确定有限自动机 根据该自动机构造相应的分析表 (ACTION表、 GOTO表 ) 总控程序 Action/Goto表 输入符号串 输出 状态与符号栈 的资料库下载 这种方法构造识别可归前缀的有限自动机从理论的角度讲是比较严格的，但实现起来却很复杂 是否存在一种比较实用的方法。 的资料库下载 由文法的产生式直接构造识别活前缀和可归前缀的有限自动机 项目（ item）：在每个产生式的右部适当位置添加一个圆点构成 项目 例如：产生式 S → aAcBe对应有 6个项目 [0] S → • aAcBe [1] S → a • AcBe [2] S → aA • cBe [3] S → aAc • Be [4] S → aAcB • e [5] S → aAcBe • 有限自动机的每一个状态由一个 项目 构成 的资料库下载 项目圆点的 左部 表示分析过程的某个时刻用该产生式归约时 句柄已识别的部分 ，圆点 右部 表示 待识别的部分。 构造识别活前缀的 NFA： 把文法的所有产生式的项目都引出，每个项目都为 NFA的一个状态 确定 初态 、 句柄识别态 、 句子识别态 确定状态之间的转换关系 *若项目 i为 X → X1X2...Xi1 • Xi...Xn 项目 j为 X → X1X2...Xi1 Xi • Xi+1...Xn 则从状态 i到状态 j连一条标记为 Xi的箭弧 *若 i为 X →  • A， k为 A → • ，则从状态 i画标 记为  的箭弧到状态 k 的资料库下载 文法 G‘： S’  E E  T + E E  T T  int * T T  int T  (E) 文法的项目有： S’  • E S’  E • E  • T + E E  T • + E E  T + • E E  T + E • E  • T E  T • T  • int * T T  int • * T 1 T  int * • T 1 T  int * T • 1 T  • int 1 T  int • 1 T  •(E) 1 T  (• E) 1 T  (E •) 1 T  (E) • 的资料库下载 NFA for Viable Prefixes of the Example T  . (E) T  (.E) T  (E.) T  (E). ( E ) S’  E. E  . T+E E  T.+E E  T+.E E  T+E. S’  . E E . T E T. T int. T .int T  .int * T T  int * T. T  int *.T T  int.* T     E  T    E +  int int * T      T  的资料库下载 NFA for Viable Prefixes in Detail (1) S’  . E 的资料库下载 NFA for Viable Prefixes in Detail (2) S’  . E S’  E. E E . T  E  . T+E  的资料库下载 NFA for Viable Prefixes in Detail (3) S’  E. E  . T+E S’  . E E . T T  .int * T   E T  . (E)  T .int   E T. T 的资料库下载 NFA for Viable Prefixes in Detail (4) T  . (E) S’  E. E  . T+E S’  .。