编译原理试题

//东南大学 一、文法G1： E→ET+|T T→TF*|F F→FP↑|P P→E|i

1、试证明符号串TET+*i↑是G1的一个句型（要求画出语法树）。 2、写出该句型的所有短语，简单短句和句柄。 三、

1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（（）），（）（（））等，甚至包含0对括号）。

2、使用文法G3给出输入串（（））（）#的自上而下分析过程。 四、已知文法G4： S→aAb|Sc|ε A→aAb|ε

1、给出G4文法的LR（0）项目集规范族； 2、构造SLR分析表； 3、G4文法所定义的语言；

4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。 S→AAA A→1A A→0 五、

1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）；

while x+y>a do

if a<10 then a：=a+1 else x：=x-1； 2、翻译布尔表达式

（a>b） or （c=d） and not （e

成转移四元式序列（即四元式中仅包含（zθ，-，-，-）和（j，-，-，-）两类语句，其中θ为关系运算符。）

一、判断下列命题的真假，并简述理由：（20分）

1、文法G的一个句子对应于多个推导，则G是二义的。 2、LL（1）分析必须对原有文法提取左因子和消除左递归。

3、算符优先分析法采用“移近-归约”技术，其归约过程是规范的。 4、文法S→aA；A→Ab；A→b是LR（0）文法（S为文法的开始符号）。

5、一个BASIC解释程序和编译程序的不同在于，解释程序由语法制导翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。

二、设计一个最小状态有穷自动机，识别由下列子串组成的任意字符串。（20分） GO，GOTO，TOO，ON

例如：GOTOONGOTOOGOON是合法字符串。

三、构造一个LL（1）文法G，识别语言L：（20分） L={ω|ω为{0，1}上不包括两个相邻的1的非空串} 并证明你的结论。

六、设有一个子程序的四元式序列为：（20分） （1）I：=1

（2）if I>20 GOTO（16） （3）T1：=2*J （4）T2：=20*I （5）T3：=T1+T2

（6）T4：=addr（A）-22 （7）T5：=2*I （8）T6：=T5*20 （9）T7：=2*J （10）T8：=T6+T7 （11）T9：=addr（A）-22 （12）T10：=T9[T8] （13）T4[T3]：=T10+J （14）I：=I+1 （15）goto（2） （16）ret 1、分划基本块。

2、对代码施行各种可能的优化，并写出优化过程中采用了何种优化策略。 一、已知文法G1： S→aB|ε B→bC|bD C→cB|c D→d

1、试构造一个最小DFA，画出状态转换图。

2、由该DFA给出它所识别的语言（用正规式表示）。 二、已知正规式α=ab*c*d，

1、试构造一个DFAM，其接受的语言为此α（画出图）； 2、由该DFAM写出对应的正规文法（古线性）。 三、文法G3：

S→A[B] A→[B]|Aa B→a

1、求出各非终结符N的Firstvt（N）和Lastvt（N），构造包括语句括号‘#’在内的算符优先表； 四、已知文法G4： T→T*F|F F→（T）|i

1、试给出语句（i*i）#的自上而下分析过程（填下表）； 2、画出对应的语法树，指出每一步归纳的句柄。 步骤│栈内│输入│动作 五、已知文法G5： 0、E‘→E 1、E→E+T 2、E→T 3、T→i

列出LR（0）项目集规范族，求出各非终结符N的Follow集合，构造SLR分析表。 六、翻译如下语句成四元式序列（由语法制导生成） while a>b and a=d；

七、按语法制导翻译下段程序成四元式序列（不要优化），设数组A：array[1??10，1??10] of int；每个下标变量占1字编址，数组按行存放，Z为函数名。

begin

A[i，j]：=A[i，j]+2； B：=Z（A[i，j]）*5 end

八、将如下一段四元式序列进行块内优化和循环优化（强度减弱及删除基本归纳变量），写出优化后的四元式序列。（要求先划分基本块） （1）i：=1

（2）if i>100 goto（10） （3）T1：=20*i （4）M：=J+T1 （5）T2：=20*i （6）N：=K+T2 （7）O：=M+N （8）i：=i+1 （9）goto（2） （10）??

一、已知正规文法中的左线性文法 G1：S→Sa|Sb|c

试构造无ε产生式的等价右线性文法，并构造相应的确定有限自动机DFA，画出状态转换图即可。

二、已知正规文法（X为开始符号） G2：X→0Y|1Z|0 Y→0X|1Y|1 Z→1X

1、该文法产生语言是什么？请用正规式表示。

本文来源：https://www.bwwdw.com/article/ksbt.html