编译原理期中试卷.pdfVIP

编译原理编译原理期中试卷期中试卷 1 简答题 每题 5 分 共计 15 分 1 简述编译程序的概念及构成 编译程序是将高级语言程序翻译成等价的低级语言的翻译程序程序 编译程序的构成 2 什么是文法 在编译原理课程中 文法可以认为是上下文无关文法 一个文法 G 是一个四元组 VN VT P S 其中 1 VT 是一个非空有穷终结符号集合 2 VN 是一个非空有穷的非终结符号集合 且 VT VN 开始符号 4 P 是一个规则的非空有穷集合 每个产生式的形式是 A 其中 A VN VT VN 开始符号 S 至必须在某个产生式的左部出现一次 3 自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么 自顶向下的语法分析解决的核心问题是 1 消除左递归 2 避免回溯 自底向上的语法分析解决的核心问题是 寻找句柄 2 文法 G E E T E T E T T F T F T F F E i 给出句型 i T F i 的短语与直接短语 简单短语 句柄和最左素短语 10 分 短语 i T F i T F T F i i1 i2 直接短语 简单短语 i1 i2 句柄 i1 最左素短语 i1 3 按指定类型给出下列语言的文法 并指出语言的类型 每个 5 分 共 10 分 1 L1 a nbm n 0 m 0 S aS bS b 2 L2 0 na1nbmcm n 0 m 0 S AB A 0A1 0a1 B bBc 4 构造正则式 a b ab b 对应的 DFA 并最小化 要求步骤清楚 15 分 1 b 0 a 6 2 a 3 b 4 b 5 Ia Ib 0 1 2 4 S 1 3 5 6 1 3 A 1 2 4 6 5 6 B 1 C 1 2 4 6 D 3 5 6 3 E 2 4 2 4 F 3 5 6 a b S A B A C D B B C C D D E B E F F E F 5 请在划线处填空 5 分 BEGIN Start Algorithms 1 PUSH PUSH S 把第一个输入符号读进 b FLAG TRUE WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在 X 中 IF X Vt THEN IF X b THEN 把下一个输入符号读进 a ELSE ERROR ELSE IF X THEN FLAG FALSE ELSE ERROR ELSE IF X b X X1X2 XK THEN 2 将 XkXk 1 X1 入栈 ELSE ERROR END End Of While END End of Algorithms 6 为文法 G E E E V V V Na N E N i 构造递归下降识别程序 15 分 构造程序 略 注意判断预测的符号 7 请给出文法的 First 和 Follow 集合 若是 LL 1 文法 给出分析表并分析句 子 abbe 15 分 G S S aD D Te T bH H D 非终结符号的 FIRST 集合 FIRST S a FIRST D b FIRST T b FIRST H b 非终结符号的 FOLLOW 集合 FOLLOW S FOLLOW D e FOLLOW T e FOLLOW H e 对于 H D First H D Follow H 8 文法 G E 1 E T T 2 E T or T 3 T n 4 T b 对应 的 LR 0 分析表如图 状态 Action GOTO or n b E T 0 s4 s3 1 2 1 acc 2 s5 s7 3 r4 r4 r4 r4 r4 4 r3 r3 r3 r3 r3 5 s4 s3 6 6 r1 r1 r1 r1 r1 7 s4 s3 8 8 r2 r2 r2 r2 r2 依据右边的表格格式 写出分析 n b or n 的过程 10 分 答题格式如下 9 Chomsky 文法分类将文法分为几类 分别什么文法 5 分 0 型文法 短语结构文法 PSG u v 其中 u VN VT v VN VT 1 型文法 上下文有关文法 CSG xUy xuy 其中 U VN x y VN VT u VN VT 2 型文法 上下文无关文法 CFG U xuy 其中 U VN x y VN VT u VN VT 3 型文法 正则文法 RG 左线性 U Va 或 U a 右线性 U aV 或 U a 其中 U V VN a VT 步骤 符号栈 状态栈 输入串 动作 1 0 n born Shift S4 2 n 04 born Reduce R3 3 T 02 b