姓名__________ 学号_________________ 院系___________ 班级___________ --------------------------------------请在装订线以下答题----------------------------------- 烟台大学文经学院信息工程系 2018~2019 学年第 一 学期 编译原理 试卷 A （考试时间为 120 分钟） 一、简答题（30 分） 1.一个编译器包括什么？（5 分） 2.cfg 和 yacc 的英文释义分别是什么？（4 分） 3.在 yacc 中，%token 和%left 分别表示什么？（8 分） 4.将 NFA 确定化：（5 分） ε a 0 a 1 a, b a, b b 3 2 a, b 5. 给出生成下述语言的上下文无关文法： （1）{ n m n a b a | n 1, m  0} （4 分） （2）{1 0 1 0 | n m m n n m  , 0} （4 分） 二、应用题（70 分） 1. （1）构造最小化 DFA： | a b  *  a a b （6 分）  | （2）给出正则表达式，构造等价的 NFA：  1 0 |1 *101（6 分）  2.已知拓广后的文法 G’和 LR 分析表如下: G’: S’→ S S → SS+ (0) (1) 

S → SS* S → a + (2) (3) 0 1 2 3 4 5 r3 S4 r1 r2 * r3 S5 r1 r2 a S2 S2 r3 S2 r1 r2 $ acc r3 r1 r2 S 1 3 3 写出输入串 aabb#的 LR 分析过程（14 分） 3.对于下述 SDD，给出(3+4)*(5+6)n 对应的注释语法分析树（10 分） 产生式 1） L   En 2） E   E T 1  3） E T  4） T   1 * T F 5）T F  F   ( E ) 6） 7） F   digit 语义规则 . L val   . E val . E val   E val T val 1  . . . E val   . T val . T val   T val F val 1  . . . T val   . F val F val .   . E val F val .   digit lexval . 4.已知文法 G: S → aBA (0) A → Ba|ε (1) B → bB|b (2) （1）求出文法 G 的 First 和 Follow 集（12 分） （2）判断文法 G 是否为 LL（1）文法？如果是，请写出预测分析表；如果不是，请说明理由（10 分） （3）判断文法 G 是否为 LR（0）文法？如果是，请画出对应的自动机；如果不是，请说明理由（12 分）