编译原理复习资料语法.ppt

编译原理 期末总复习 考试题型及分数分布 填空题单选题判断题解析题 第二章文法与形式语言简介 用语法树求句型的短语 简单短语 素短语 句柄 举例 用语法树求F F T T i 的短语 E E T T T T F F F E a E T T F E E T T F i T T F F 寻找子树求短语 1 F是句型F F T T i 相对于非终结符号T的短语 是简单短语 是句柄 寻找子树求短语 2 F F是句型F F T T i 相对于非终结符号T的短语 寻找子树求短语 3 T是句型F F T T i 相对于非终结符号E的短语 是简单短语 寻找子树求短语 4 i是句型F F T T i 相对于非终结符号F的短语 是简单短语 寻找子树求短语 5 T i是句型F F T T i 相对于非终结符号F的短语 寻找子树求短语 6 T T i是句型F F T T i 相对于非终结符号T的短语 寻找子树求短语 7 T T i 是句型F F T T i 相对于非终结符号F的短语 寻找子树求短语 8 F F T T i 是句型F F T T i 相对于非终结符号E和T的短语 第三章词法分析 1 NFA到DFA转换的子集法及最小化2 正规式和有限自动机的等价性 子集法的基本思想 NFA 基本思想 NFA的一组状态 DFA的一个状态 对应 等价的DFA 子集法 转换 2 子集法 设已给具有 动作的NFAM K f S0 Z 构造相应的确定的有限自动机 DFAM K f q0 Z 构造K 及f 的步骤可递归地描述如下 1 给出M 的初态 递归描述步骤 1 K q0 q0 closure S0 递归描述步骤 2 2 对于K 中尚未标记的状态qi Si1 Si2 Sim Sik K做 标记qi 对于每一个a 置 若qj不在K 中 则将qj f qi a qj K M J move Si1 Si2 Sim a qj closure J Ia 递归描述步骤 3 3 重复 2 直到M 中不再有未标记的状态为止 至少含有一个Z中元素的qi作为M 的终态 子集法举例 DFAM 0 1 2 3 4 5 6 7 8 9 10 a b f 0 10 求与之等价的DFA 子集法求解过程 1 1 closure 0 0 q0 0 1 2 4 7 1 2 4 7 K q0 子集法求解过程 2 2 对K 中未标记状态q0做 1 标记q0 2 move q0 a move 0 1 2 4 7 a closure 3 8 3 8 3 8 f q0 a 6 7 1 2 4 1 2 3 4 6 7 8 q1 q1 q0 0 1 2 4 7 子集法求解过程 2 move q0 b q0 0 1 2 4 7 q1 1 2 3 4 6 7 8 move 0 1 2 4 7 b closure 5 5 5 f q0 b q2 6 7 1 2 4 1 2 4 5 6 7 q2 K q0 q1 q2 子集法求解过程 3 3 对K 中未标记状态q1做 q0 0 1 2 4 7 q1 1 2 3 4 6 7 8 q2 1 2 4 5 6 7 1 标记q1 2 move q1 a closure 3 8 q1 move 0 1 3 4 6 7 8 a 3 8 closure 5 9 f q1 a q1 move q1 b move 0 1 3 4 6 7 8 b 5 9 1 2 4 5 6 7 9 5 9 6 7 1 4 2 f q1 b q3 K q0 q1 q2 q3 q3 子集法求解过程 4 4 对K 中未标记状态q2做 q0 q1 q2 1 2 4 5 6 7 q3 1 2 4 5 6 7 9 1 标记q2 2 move q2 a move 1 2 4 5 6 7 a K q0 q1 q2 q3 3 8 closure 3 8 q1 f q2 a q1 move q2 b move 1 2 4 5 6 7 b 5 closure 5 5 6 7 1 2 4 q2 f q2 b q2 子集法求解过程 5 5 对K 中未标记状态q3做 1 标记q3 q0 q1 q2 q3 1 2 4 5 6 7 9 2 move q3 a move 1 2 4 5 6 7 9 a K q0 q1 q2 q3 3 8 closure 3 8 q1 f q3 a q1 move q3 b move 1 2 4 5 6 7 9 b 5 10 closure 5 10 5 10 6 7 1 2 4 q4 f q3 b q4 q4 子集法求解过程 6 6 对K 中未标记状态q4做 1 标记q4 q0 q1 q2 q3 q4 1 2 4 5 6 7 10 2 move q4 a move 1 2 4 5 6 7 10 a K q0 q1 q2 q3 q4 3 8 closure 3 8 q1 f q4 a q1 move q4 b move 1 2 4 5 6 7 10 b 5 closure 5 q2 f q4 b q2 等价的DFAM 如下 K q0 q1 q2 q3 q4 f q0 a q1 f q0 b q2 f q1 a q1 f q1 b q3 f q2 a q1 f q2 b q2 f q3 a q1 f q3 b q4 f q4 a q1 f q4 b q2 Z q4 NFAM转换为DFAM 的过程 f q0 a q1 f q0 b q2 f q1 a q1 f q1 b q3 f q2 a q1 f q2 b q2 f q3 a q1 f q3 b q4 f q4 a q1 f q4 b q2 q0 0 1 2 4 7 q1 1 2 3 4 6 7 8 q2 1 2 4 5 6 7 q3 1 2 4 5 6 7 9 q4 1 2 4 5 6 7 10 q1 1 2 3 4 6 7 8 q2 1 2 4 5 6 7 q1 1 2 3 4 6 7 8 q3 1 2 4 5 6 7 9 q1 1 2 3 4 6 7 8 q2 1 2 4 5 6 7 q1 1 2 3 4 6 7 8 q4 1 2 4 5 6 7 10 q1 1 2 3 4 6 7 8 q2 1 2 4 5 6 7 DFAM 的状态图 f q0 a q1 f q0 b q2 f q1 a q1 f q1 b q3 f q2 a q1 f q2 b q2 f q3 a q1 f q3 b q4 f q4 a q1 f q4 b q2 q0 q1 q2 q3 a b a b a b a b a b 初态 终态 例 将下列DFAM最小化 化简 化简步骤1 1 初始划分由两个子集组成 即 q4 终态 q0 q1 q2 q3 非终态 q0 q1 q2 q3 q4 化简步骤2 2 考查子集 q0 q1 q2 q3 q0 q1 q2 q3 q4 表示对q0 q1 q2 q3输入符号a转移到的下一状态所组成的集合 q0 q1 q2 q3 a 化简步骤2 1 1 q0 q1 q2 q3 a q0 q1 q2 q3 q4 q0 q1 q2 q3 q4 q1 q0 q1 q2 q3 q0 q1 q2 q3 b q2 q3 q4 q0 q1 q2 q3 q4 q0 q1 q2 b q2 q3 q3 b q4 q0 q1 q2 q3 q0 q1 q2 q3 化简步骤2 2 2 考查子集 q0 q1 q2 q0 q1 q2 q3 q4 q0 q2 q1 q3 q4 q0 q1 q2 a q1 q0 q1 q2 q0 q1 q2 b q2 q3 q0 q1 q2 q0 q1 q2 q0 q2 q1 化简步骤2 3 3 考查子集 q0 q2 q0 q2 q1 q3 q4 q0 q2 q1 q3 q4 q0 q2 a q1 q0 q2 b q2 q0 q2 子集 q0 q2 不能再分割 化简步骤3 3 选择q0作为 q0 q2 的代表 化简后的DFAM 将q2从状态转换图中删除 将原来引向q2的有向弧都引至q0 q0 q1 q3 a b a b b a b a 初态 终态 从正规式R构造NFAM的步骤1 1 把正规式R表示为 初态 终态 x R 从 上的正规式R构造NFAM的步骤2 2 把R分裂并加进新的结点 每条弧标记为 上的一个字符或 结点分裂规则 加入k结点 1弧变2弧 结点分裂规则 1弧变2弧 结点分裂规则 加入k结点 闭包去掉变闭环 前后各1条空弧 k R1 例 构造与正规式等价的NFAM 正规式R a b ba a b 步骤1 初态 终态 x a b ba a b 步骤2 初态 终态 x a b 1 a b 2 b 3 a 步骤3 a b a b 4 5 步骤4 a b 6 a b 步骤5 a 7 第四章自顶向下的语法分析 LL 1 分析方法 LL 1 文法举例 A A B BB B C CC D DD A i 1 试问该文法是否为LL 1 文法 为什么 2 写出与该文法等价的LL 1 文法G1 3 构造G1的LL 1 分析表 FIRST集 FIRST D i FIRST C i FIRST B FIRST C i FIRST A FIRST B i FOLLOW集 FOLLOW B A A B FOLLOW A D A FOLLOW A A是开始符号 FOLLOW A FOLLOW A A A B B FOLLOW A 加入 FOLLOW B B B C FOLLOW A FOLLOW D B B C C FOLLOW B 加入 FOLLOW C FOLLOW C FOLLOW B FOLLOW B C D D FOLLOW C 加入 FOLLOW D FOLLOW C 判断是否为LL 1 文法 该文法不是LL 1 文法 A A B B B C 左递归 A A B B FIRST A i FIRST B i FIRST A B FIRST B i 不能避免回溯 消除左递归 1 A A B B 引进新的非终结符号A A BA A BA 消除左递归 2 CB B B C C 引进新的非终结符号B B CB B 改写后的文法 A BA A BA B CB B CB C D DD A i 考察是否避免回溯 1 A BA 求FOLLOW A A BA FOLLOW A 加入 FOLLOW A D A FOLLOW A A为文法的识别符号 FOLLOW A FOLLOW A FOLLOW A FIRST BA FOLLOW A 考察是否避免回溯 2 B CB 求FOLLOW B B CB FOLLOW B 加入 FOLLOW B A BA FIRST A 加入 FOLLOW B A FOLLOW A 加入 FOLLOW B FOLLOW A FOLLOW B FOLLOW B FIRST CB FOLLOW B 考察是否避免回溯 3 改写后的文法是LL 1 文法 C D D 求FIRST D D A i FIRST D i FIRST D FIRST D i 构造LL 1 分析表M FIRST A FIRST B FIRST A LL 1 分析表M FIRST B FIRST C i FIRST D i FOLLOW A FOLLOW B i A A B B C D A BA A BA A BA A BA A A B CB B CB B CB B CB B B B C D C D C D D A D i 表达式文法G S 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P i 7 D i 计算文法G中每一个非终结符的FIRSTVT LASTVT集 构造文法G的算符优先关系矩阵 第五章自底向上的优先分析法 FIRSTVT集 1 S S 所以 FIRSTVT S 2 D i所以 FIRSTVT D i 3 S D R FIRSTVT S 属于FIRST D 的元素也属于FIRSTVT S 即 FIRSTVT S i 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P I 7 D i FIRSTVT集 续 4 P i所以 i FIRSTVT P P S所以 属于FIRST S 的元素也属于FIRSTVT P 即 FIRSTVT P i 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P i 7 D i FIRSTVT S i FIRSTVT集 续 5 R R P所以 FIRSTVT R 6 R P所以 属于FIRST P 的元素也属于FIRSTVT R 即 FIRSTVT R i 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P I 7 D i FIRSTVT P i LASTVT集 1 S S 所以 LASTVT S 2 D i所以 LASTVT D i 3 S D R 所以 FIRSTVT S 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P I 7 D i 4 P i所以 i LASTVT P P S所以 属于LASTVT S 的元素也属于LASTVT P 即 LASTVT P i LASTVT集 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P I 7 D i FIRSTVT S 5 R R P所以 LASTVT R 6 R P所以 属于LASTVT P 的元素也属于LASTVT R 即 LASTVT R i 1 S S 2 S D R 3 R R P 4 R P 5 P S 6 P I 7 D i LASTVT集 LASTVT P i 优先相等关系 1 S S 所以 2 S D R 所以 优先小于关系 1 S S FIRSTVT S i 所以 与FIRSTVT S 中的元素有小于关系 即 i 2 S D R FIRSTVT R i 所以 与FIRSTVT R 中的元素有小于关系 即 i 优先小于关系 续 3 R R PFIRSTVT P i 所以 与FIRSTVT P 中的元素有小于关系 即 i 优先大于关系 1 S S LASTVT S 所以 LASTVT S 中的元素与 有大于关系 即 优先大于关系 续 2 S D R LASTVT D i 所以 LASTVT D 中的元素与 有大于关系 即 i S D R LASTVT R i 所以 LASTVT R 中的元素与 有大于关系 即 i 优先大于关系 续 3 R R PLASTVT R i 所以 LASTVT R 中的元素与 有大于关系 即 i 构造算符优先分析表 第六章LR分析法 1 LR 0 分析法2 SLR 1 分析法 SLR 1 分析法举例 对下列文法 1 S S 2 S bRST 3 S bR 4 R dSa 5 R e 6 T fRa 7 T f 求各非终结符号的FIRST和FOLLOW集 构造该文法的SLR 1 分析表 分析符号串bebefea FIRST集 FIRST S b FIRST S