编译原理题库

第一章什么就是编译器？编译程序得结构分为几个阶段,各阶段得任务就是什么？遍、编译前端及编译后端得含义？编译程序得生成方式有哪些？第二章1、 写一文法,使其语言就是偶正整数得集合。要求:(1)允许 0 打头 (2) 不允许 0 打头解:(1)允许 0 开头得偶正整数集合得文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8(2)不允许 0 开头得偶正整数集合得文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|02、证明下述文法 G［〈表达式〉］就是二义得。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+||*|/解:可为句子 a+a*a 构造两个不同得最右推导: 最右推导 1 〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉aÞ〈表达式〉* aÞ〈表达式〉〈运算符〉〈表达式〉* aÞ 〈表达式〉〈运算符〉a * aÞ〈表达式〉+ a * aÞ a + a * a最右推导 2 〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉 aÞ〈表达式〉〈运算符〉〈表达式〉 * aÞ 〈表达式〉〈运算符〉a * aÞ〈表达式〉+ a * aÞ a + a * a3、 给出生成下述语言得上下文无关文法: (1){ anbnambm| n,m>=0} (2){ 1n0m1m0n| n,m>=0}解: (1){ anbnambm| n,m>=0} S→AAA→aAb|ε (2) { 1n0m1m0n| n,m>=0}S→1S0|AA→0A1|ε第三章1、构造一个 DFA,它接收∑={a, b}上所有满足下述条件得字符串:字符串中得每个 a 都有至少一个 b 直接跟在其右边。解:已知∑={a, b},根据题意得出相应得得正规式为: (b*abb*)*根据正规式画出相应得 DFA M,如下图所示用子集法将其确定化IIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{5,6,1,2,3,Y} {4}{6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}由 DFA 得状态图 用最小化方法化简得:{0},{1},{2},{3,4},按顺序重新命名 DFA M’XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb0121—3212314414 第四章练习 1:文法 G[V]: V→N|N[E] E→V|V+E N→i 就是否为 LL(1)文法,如不就是,如何将其改造成 LL(1)文法。解:LL(1)文法得基本条件就是不含左递归与回溯(公共左因子),而 G[V]中含有回溯,所以先消除回溯得到文法 G’[V]: G’[V]: V→NV’ V’→ε|[E] E→VE’ E’→ε|+E N→i由 LL(1...