//东南大学。
一、文法g1：
e→et+|t
t→tf*|f
f→fp↑|p
p→e|i1、试证明符号串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→aaaa→1aa→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=上不包括两个相邻的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→d1、试构造一个最小dfa，画出状态转换图。
2、由该dfa给出它所识别的语言（用正规式表示）。
二、已知正规式α=ab*c*d，1、试构造一个dfam，其接受的语言为此α（画出图）；
2、由该dfam写出对应的正规文法（古线性）。
三、文法g3：
s→a[b]
a→[b]|aa
b→a1、求出各非终结符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→t3、t→i
列出lr（0）项目集规范族，求出各非终结符n的follow集合，构造slr分析表。
六、翻译如下语句成四元式序列（由语法制导生成）
while a>b and a if a=5 then b：=b+1 else
repeat
a：=a+1
until a>=d；
七、按语法制导翻译下段程序成四元式序列（不要优化），设数组a：array[1……10，1……10] of int；每个下标变量占1字编址，数组按行存放，z为函数名。
begina[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）
一、已知正规文法中的左线性文法。
g1：s→sa|sb|c
试构造无ε产生式的等价右线性文法，并构造相应的确定有限自动机dfa，画出状态转换图即可。
二、已知正规文法（x为开始符号）
g2：x→0y|1z|0
y→0x|1y|1
z→1x1、该文法产生语言是什么？请用正规式表示。
2、构造最简的确定有限自动机dfa，并画出状态转换图。
2、给出文法改写以后的各非终结符x的first（x）与follow（x）集合，并由此判定它是否是ll（1）文法。
四、已知表达式文法（已拓广）
g4：e‘→e
e→e+e|i
1、试构造文法g4的lr（0）项目集规范族；
五、已知文法（z为开始符号）
g5：z→bmb
m→（ma）|a
1、试构造算符优先分析表。
六、翻译成中间**。
1、将如下程序段翻译成后缀式（逆波兰式），填在一维数组post[i]中，设i初值=1.
t：=15；
b：=20；
while t<>b do
if t>b then t：=t-b
else b：=b-t；
2、翻译布尔表达式成转移四元式序列，并指出待填真假链序号。
（a>b+1）and not（c+2 注：f（x）为布尔函数。
八、已知如下程序段。
a：=1；while a<=10 do
beginif a<>b then
a[a，b]：=a[a，b]+2；
a：=a+1；
end；1、按语法制导生成四元式中间**序列；
2、将中间**序列划分成基本块，画出程序流图，并指出循环结点集；
3、执行循环中**外提，强度减弱优化和基本块内删除公共子表达式优化，最后画出包含优化后的中间**的程序流图。
注：数组a：array[1……10，1……10] of int；按行存放，每个下标变量占1字编址，首地址为addra.
/上海交大。
八、已知如下程序段。
a：=1；while a<=10 do
beginif a<>b then
a[a，b]：=a[a，b]+2；
a：=a+1；
end；1、按语法制导生成四元式中间**序列；
2、将中间**序列划分成基本块，画出程序流图，并指出循环结点集；
3、执行循环中**外提，强度减弱优化和基本块内删除公共子表达式优化，最后画出包含优化后的中间**的程序流图。
注：数组a：array[1……10，1……10] of int；按行存放，每个下标变量占1字编址，首地址为addra.
清华大学1997年研究生入学考试编译原理试题（共50分）
5．(6分)
试对下面基本块进行优化。
应用dag对该基本块进行优化，给出优化后的语句序列。
给出当只有l在基本块出口后为活跃时的优化结果。
基本块为：
x=b＊c
y=b/c
z=x+y
w=9＊z
6．(6分)
已知文法g[s]为：
s→daba→aa|a
b→bb|ε
试向g[s]是否为正规文法，为什么？
g[s]新产生的语言是什么？
g[s]能否改写为等价的正规文法？
3．(8分)专。
有文法g[s]为：
专s→a|b|（a）共。
a→sda|s
完成下列算符优先关系表，并判断g[s]是否为算符优先文法。同济。
g[s]的算符优先关系表业。
表1 算符优先关系表共济网。
ab()d#密云路。
a ·>kaoyangj
b ·>1号。
<·<西门。
#信箱。d<·<
# 给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。
给出输入串（adb）＃的分析过程。
4． (8分)
已知文法g[s]为：
s→aad|；bd|ab↑|；a↑
a→ab→a
试判断g[s]是否为lalr（1）文法。
当一个文法是lr（1）而不是lalr（1）时，那么lr（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。
1、 请写出在＝上，2、 不3、 是a开头的，4、 以aa结尾的字符串集合的正规表达式，5、 并构造与之等价的状态最少的的dfa。（9分）
三、给出文法g2:s sas sbs csd es f
1、 请证实这是一个二义文法；
2、 给出什么的约束条件，3、 可构造出无冲突的lr分析表？请证实你的论点。（8分）。
四、给出下列**序列：
1) a:=b-c
2) d:=a+4
3) e:=a-b
4) f:=c+e
5) b:=b+c
6) c:=b-f
7) if b< p>
8) b:=b-c
9) f:=b+f
10) a:=a-f
11) if a=c goto (3)
12) halt
1、 请划分基本块，2、 并构造流图。
3、 假定各基本块出口之后的活跃变量均为循环中可用作固定分配的寄存器为r0和r1,固定分配给循环中哪二个变量，4、 可使执行代价省得最多？ （10分）
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想，分析器总体结构，分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点 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分 写一个文法使其...
编译原理试题
1 最左简单子树的末端结点构成的符号串称为 2 若一个文法是递归的，则它产生的句子个数是 3 在通常的语法分析方法中，特别适用于表达式的分析。4 后缀式ab cd 可用表达式来表示。5 下面不是常见的中间语言表示形式是 6 文法分为四种类型，即0型 1型 2型 3型。其中3型文法是 7 表达式a b...