_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 号 学 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 名 姓 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 级 班 常 州 工 学 院 试 卷 B 卷 共 5 页 第 1 页 编译原理 试卷 20 / 20 学年第 学期 考试类型 开卷 课程编码 0302008 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 一、为以下字符集编写正规表达式，并构造其与之 等价的最简DFA。（30分） 1）在字母表 {0,1}上的且不以 0 开头但以 11 结尾的所有字符串。（18 分） 2）在字母表 {0,1}上的包含 01 子串的所有字符串。（12 分） … … … … … … … … … … … … … … … … … … … … … … … 线 订 装 … … … … … … … … … … … … … … … … … … … … … … … 

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 号 学 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 名 姓 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 级 班 常 州 工 学 院 试 卷 C 卷 共 5 页 第 2 页 二、写出表达式A+B*(C-D)+E/(C-D)的逆波兰表示及 三元式序列。（10分） 三、已知文法G（开始符号为N）：（20分） NSE|E SSD|D E0|2|4|6|8|10 D0|1|2|3|4|5|6|7|8|9 (1)证明文法G有二义性 (2) 此文法所描述的语言是什么？ … … … … … … … … … … … … … … … … … … … … … … … 线 订 装 … … … … … … … … … … … … … … … … … … … … … … … 

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 号 学 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 名 姓 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 级 班 常 州 工 学 院 试 卷 C 卷 共 5 页 第 3 页 四、已知文法G： （25 分） ETE’ E’  +E |ε T  F T’ T’ T|ε FPF’ F’ *F’ |ε P(E) | ^|a |b 1）计算文法G中每个非终结符的First集和Follow集。 2）证明该文法G是LL(1)文法 3）构造文法G的预测分析表。 … … … … … … … … … … … … … … … … … … … … … … … 线 订 装 … … … … … … … … … … … … … … … … … … … … … … … 

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 号 学 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 名 姓 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 级 班 常 州 工 学 院 试 卷 C 卷 共 5 页 第 4 页 五、把语句 if x＞0 y＞0 then z：＝x＋y （15分） else Begin x：＝x＋2 y：＝y＋3 End； 翻译成四元式序列。 … … … … … … … … … … … … … … … … … … … … … … … 线 订 装 … … … … … … … … … … … … … … … … … … … … … … … 

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 号 学 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 名 姓 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 级 班 常 州 工 学 院 试 卷 C 卷 共 5 页 第 5 页 … … … … … … … … … … … … … … … … … … … … … … … 线 订 装 … … … … … … … … … … … … … … … … … … … … … … …