计算机学院2001级班学号姓名。
一选择题（12分）s
】1．词法分析器的输入是。
a．符号串 b．源程序 c．语法单位 d．目标程序。
】2．两个有穷自动机等价是指它们的。
a．状态数相等b．有向弧数相等。
c．所识别的语言相等 d．状态数和有向弧数相等。
】3．文法g：s → xsx | y 所识别的语言是。
a．xy*x b．(xyx)* c．xx*yxx* d．x*yx*
】4．设a,b,c为文法的终结符，且有优先关系ab和bc，则。
a．必有ac b．必有ca
c．必有ba d．选项a、b和c都不一定成立。
】5．若状态k含有项目“a→α.且仅当输入符号a∈follow(a)时，才用规则“a →α归约的语法分析方法是。
a．lalr分析法b．lr(0)分析法
c．lr(1)分析法 d．slr(1)分析法。
】6．生成中间**时所依据的是。
a．语法规则 b．词法规则 c．语义规则 d．等价变换规则。
】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。
a．┐ab∨∧cdb．a┐b∨cd∨∧
c．ab∨┐cdd．a┐b∨∧cd∨
】8．基本块。
a．只有一个入口语句和一个出口语句 b．有一个入口语句和多个出口语句。
c．有多个入口语句和一个出口语句 d．有多个入口语句和多个出口语句。
二判断题（6分。认为正确的填“t”，错的填“f”）
】1．同心集的合并有可能产生“归约/归约”冲突。
】2．一个文法所有句子的集合构成该文法定义的语言。
】3．非终结符可以有综合属性，但不能有继承属性。
】4．逆波兰表示法表示表达式时无需使用括号。
】5．一个有穷自动机有且只有一个终态。
】6．若过程p第k次被调用，则p的display表中就有k+1个元素。
三填空题（8分）
1．最常用的两类语法分析方法是和分析法。
2．对于文法g[e]：e→t|e+t t→f|t*f f→p↑f|p p→(e)|i,句型t+t*f+i的直接短语为句柄为。
3．在lr(0)分析法中，若，βv*且a则称“a .”为项目，称“s .aβ”为项目。
4．在pl/0的目标**解释执行时，寄存器b总是指向当前执行过程活动记录的而寄存器t总是指向。
四（7分）有穷自动机m接受字母表＝上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与m等价的正规式。
五（8分）构造下列文法相应的有穷自动机。
g[s]： s → aa | bq
a → aa | bb | b
b → bd | aq
q → aq | bd | b
d → bb | aa
e → ab | bf
f → bd | ae | b
六（8分）写一个文法，使其语言是：
l ＝ 七（12分）已知文法。
g[a]： a → aab | a
b → bb | d
1）构造与g[a]等价的ll(1)文法；
2）构造g’[a]的**分析表。
八（12分）考虑文法。
g[s]: s → as | b
a → sa | a
1）构造文法的可归前缀图（活前缀的dfa）；
2）判断文法是否是lr(0)文法，并说明理由。
九（7分）将下面程序段翻译成四元式序列。
while a if a=1 then c:=c+1
else while aa:=a+2;
十（6分）设有以下程序段。
program main;
var a,b:integer;
procedure p(x,y,z:integer);
begin
y:=y+1;
z:=z+x
end;begin
a:=2; b:=3; p(a+b,a,a); write(a)
end.对于下列参数传递方式，分别写出执行程序后a的输出值。
1）传名；2）传地址。
十一（6分）有一语法制导翻译如下所示：
s → bab
a →(b
a → a
b → aa)
若对输入序列b(((aa)a)a)b 进行自底向上分析，请写出输出序列。
十二（8分）对pl/0语言扩充else子句：
《条件语句》 :if 《条件》 then 《语句》 [else 《语句》 ]
请在空缺处填空，完成条件语句的编译算法：
switch (sym) {
case ifsym:
condition(symsetunion(symsetnew(thensym),fsys),lev,tx);
if (sym==thensym) getsym();
else error(16);
cx1=cx; gen(jpc,0,0);
statement(symsetunion(symsetnew(elsesym),fsys),lev,tx);
ifcode[cx1].a=cx;
else {
cx2=cx; gen(jmp,0,0);
code[cx1].a
statement(fsys,lev,tx);
break;
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想，分析器总体结构，分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点 first和follow集的求法，对它们的理解以及在构造ll 1 分析表时的使用。递归子程序法中如何体现分析的结果。基本要求。掌握语法分析 ...
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式，并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合，并判断该文法是否是ll 1 的，请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...
编译原理试题
东南大学。一 文法g1 e et t t tf f f fp p p e i1 试证明符号串tet i 是g1的一个句型 要求画出语法树 2 写出该句型的所有短语，简单短句和句柄。三 1 试写出一个上下文无关文法g3，它能产生配对的圆括号串 例如等，甚至包含0对括号 2 使用文法g3给出输入串 的自...