广东海洋学编译原理期末试题（）
非题（请括号正确划√错误划×）（2分20分）
1．编译程序高级语言程序解释执行(× )
2．限状态动机中仅唯终态(×)（终态）
3．算符优先文法存算符优先函数应 (√ )
4．语法分析时必须先消文法中左递 (×)
5．LR分析法左右扫描输入串时发现错误准确指出出错点 (√)
6．逆波兰表示法表示表达式时须括号 (√ )
7．静态数组存储空间编译时确定 (×)
8．进行代码优化时应着重考虑循环代码优化提高目标代码效率起更作 (×)
9．两正规集相等必条件应正规式等价 (× )
10．语义子程序描述文法应翻译工作 (×)
二选择题(请前括号选择确切项作答案划勾划错)(4分40分)
1．词法分析器输出结果_____
A．( ) 单词种编码 B．( ) 单词符号表中位置
C．( ) 单词种编码身值 D．( ) 单词身值
2． 正规式 M 1 M 2 等价指_____
A．( ) M1M2状态数相等 B．( ) M1M2边条数相等
C．( ) M1M2识语言集相等 D．( ) M1M2状态数边条数相等
3． 文法G：S→xSx|y识语言_____
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*
4．果文法G二义句子α_____
A．( )左推导右推导应语法树必定相
B．( ) 左推导右推导应语法树
C．( ) 左推导右推导必定相
D．( )存两左推导应语法树相
5．构造编译程序应掌握______
A．( )源程序 B．( ) 目标语言
C．( ) 编译方法 D．( ) 三项
6．四元式间联系通_____实现
A．( ) 指示器 B．( ) 时变量
C．( ) 符号表 D．( ) 程序变量
7．表达式(┐A∨B)∧(C∨D)逆波兰表示_____
A ( ) ┐AB∨∧CD∨ B．( ) A┐B∨CD∨∧
C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨
8 优化生成_____目标代码
A．( ) 运行时间较短 B．( ) 占存储空间较
C．( ) 运行时间短占存空间 D．( ) 运行时间短占存储空间
9．列______优化方法针循环优化进行
A ( ) 强度削弱 B．( ) 删纳变量
C．( ) 删余运算 D．( ) 代码外提
10．编译程序_____区标识符作域
A ( ) 说明标识符程函数名
B．( ) 说明标识符程函数静态层次
C．( ) 说明标识符程函数动态层次
D ( ) 标识符行号
三填空题(空1分10分)
1．计算机执行高级语言编写程序两种途径：___解释____编译___
2．扫描器__词法分析器___接受输入__源程序___源程序进行___词法分析__识出单词符号输出结果单词符号供语法分析器
3．分析法采___移进__约错误处理___接受__等四种操作
4．LR分析器包括两部分：总控程序___张分析表__
5．缀式abc代表表达式___a(bc)__
6．局部优化__基块___范围进行种优化
四简答题（20分）
1 简说明语义分析基功
答：语义分析基功包括 确定类型类型检查语义处理某静态语义检 查
2 考虑文法 G[S]
S → (T) | a+S | a
T → TS | S
消文法左递提取公左子
解：消文法G[S]左递：
S→(T) | a+S | a
T→ST′
T′→ST′| ε
提取公左子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→ST′| ε
3 试表达式 w+(a+b)*(c+d(e10)+8) 写出相应逆波兰表示
解： w a b + c d e 10 + 8 + * +
4 三种基控制结构文法面语句翻译成四元式序列：
while (A{
if (A ≥ 1) CC+1
else while (A ≤ D)
AA+2
}
解：该语句四元式序列(中E1E2E3分应A＜C∧B＜DA≥1A≤D关系运算符优先级高)：
100 (j101 (j__113)
102 (j103 (j__113)
104 (jA1106)
105 (j__108)
106 (+ C 1 C)
107 (j__112)
108 (j≤AD110)
109 (j__112)
110 (+ A 2 A)
111 (j__108)
112 (j__100)
113
5 已知文法 G[S] S → aSb|Sb|b 试证明文法 G[S] 二义文法
证明：
文法G[S]：S→aSb|Sb|b句子aabbbb应两棵语法树：
文法G[S]二义文法
五计算题（10分）
已知文法
A>aAd|aAb| ε
判断该文法否 SLR(1) 文法构造相应分析表输入串 ab# 出分析程
解：增加非终结符S产生原文法增广文法：
S'>A
A>aAd|aAb|ε
面构造LR(0)项目集规范族：
表出状态I0I2存移进约突该文法LR(0)文法I0说：FOLLOW(A)∩{a}{bd#}∩{a}ΦI0状态面输入符号a时移进bd#时约时报错I2说I0完全相结说移进约突解决该文法SLR(1)文法
SLR(1)分析表：
输入串ab#出分析程：
编译原理期末试题（二）
非题：
1文关文法开始符终结符非终结符 ( )
2句型直接短语唯 （ ）
3已证明文法二义性判定 （ ）
4基块DAG表示 （ ）
5程活动记录体积编译时静态确定 （ ）
62型文法定3型文法 （ ）
7句型定句子 ( )
8算符优先分析法次句柄进行约 X 应左素短语 ( )
9采三元式实现三址代码时利中间代码进行优化 （ ）
10编译程中语法分析器务分析单词样构成 ( )
11优先表定存相应优先函数 X ( )
12目标代码生成时应考虑充分利计算机寄存器问题 ( )
13递降分析法种分析法 ( )
14文法改写成LL(1)文法 ( )
15基块入口出口 ( )
16LL(1)文法定二义 ( )
17逆波兰法表示表达试称前缀式 ( )
18目标代码生成时应考虑充分利计算机寄存器问题 ( )
19正规文法产生语言文关文法描述 ( )
20优先表定存相应优先函数 ( )
213型文法定2型文法 ( )
22果文法存某句子应两棵语法树文法二义性 ( )
答案：1× 2× 3× 4√ 5√ 6× 7× 8× 9√ 10× 11×
12√ 13× 14√ 15√ 16√ 17× 18√ 19√ 20× 21√ 22√
二填空题：
2编译程分 （ 词法分析） （语法分析）（语义分析中间代码生成 ）（优化）（目标代码生成 ）五阶段
3果文法存某句子应两棵语法树称文法（ 二义性 ）
4功说程序语言语句体分（ 执行性 ）语句（说明性 ）语句两类
5语法分析器输入（ 单词符号 ）输出（ 语法单位 ）
6扫描器务（ 源程序中 ）中识出（ 单词符号 ）
7符号表中信息栏中登记名字关性质(类型种属占单元址）等等
8程相应DISPLAY表容(现行活动记录址外层新活动记录址)
10常两种动态存贮分配办法（栈式）动态分配（堆式）动态分配
11名字属性包括( 类型)(作域 )
12常参数传递方式(传址）（传值）（传名）
13根优化涉程序范围优化分成(局部优化）（循环优化）（全局优化）三级
14语法分析方法致分两类类（ ）分析法类（ ）分析法
15预测分析程序张（ 分析表 ）（ 符号栈 ）进行联合控制
17张转换图包含限状态中认（初）态实际少（终 ）态
19语法分析语言（语法 ）规进行中间代码产生语言（语义）规进行
21文法G预测分析表M含重定义该文法（LL(1) 文法）文法
22数空间存贮分配 FORTRAN采( 静态策略 PASCAL采( 动态)策略
24右推导称（规范推导）句型称（规范）句型
26文法G仅含终结符号句型称 ( 句子 )
27谓分析法指(开始符号出发推导推出句子）
29局限基块范围优化称（ 局部优化 ）
312型文法称（文关）文法3型文法称（正 ）文法
32条指令执行代价定义(指令访问存次数加1）
33算符优先分析法次(左素短语）进行约
三名词解释题：
1局部优化局限基块范围优化称
2二义性文法果文法存某句子应两棵语法树称文法二义性文法
3DISPLAY表程嵌套层次显示表记录该程外层程新活动记录起始址
5左推导步α>βα中右非终结符换
6语法组规形成产生组合式程序
7文法描述语言语法结构形式规
8基块指程序中序执行语句序列中入口出口入口中第语句出口中语句
9语法制导翻译语法分析程中根产生式应语义子程序进行翻译办法做语法制导翻译
10短语令G文法S划文法开始符号假定αβδ文法G句型果SαAδAβ称β句型αβδ相非终结符A短语
11信息果基块中四元式iA定值四元式j引A值ij间没A定值称j四元式i变量A信息
12规范句型规范推导句型
13扫描器执行词法分析程序
14超前搜索词法分析程中时确定词性需超前扫描干字符
15句柄句型左直接短语
16语法制导翻译语法分析程中根产生式应语义程序进行翻译方法 做语法制导翻译
17规范句型规范推导句型
18素短语素短语指样短语少含终结符身外含更素短语
19语法组规形成产生合式程序
20信息果基块中四元式iA定值四元式j引A值ij间没A定值称j四元式i变量A信息
21语义定义程序意义组规
四简答题：
注1写文法G 语言 0开头偶数集
2已知文法G(S)相应翻译方案
S→aAb {print 1}
S→a {print 2}
A→AS {print 3}
A→c {print 4}
输入acab 输出什？
3 已知文法G(S)
S→bAa
A→(B | a
B→Aa)
写出句子b(aa)b规范约程
4 考虑面程序：
…
procedure p(x y z)
begin
yx+y
zz*z
end
begin
A2
BA*2
P(A A B)
Print A B
end
试问参数传递方式分采传址传值时程序执行输出 A B值什
5．文法G(S)
S→dAB
A→aA| a
B→Bb| ε
描述语言什？
6 证明文法G(S)
S→SaS| ε
二义性
7 已知文法G(S)
S→BA
A→BS| d
B→aA| bS | c
预测分析表
a
b
c
d
#
S
S→BA
S→BA
S→BA
A
A→BS
A→BS
A→BS
A→d
B
B→aA
B→bS
B→c
出句子 adccd 分析程
8 写文法G 语言 L(G){albmclanbn| l>0 m>1 n>2}
9 已知文法G(S)
S→a| (T)
T→TS|S
优先关系表：
关系
a
(
)
a
>
>
(
<
<
<
)
>
>
<
<
>
>
请计算出该优先关系表应优先函数表
10 谓优化？涉程序范围分级优化？
11 目标代码种形式？生成目标代码时通常应考虑问题？
12 字母表Σ{a b}试写出Σa首字组成正规集相应正规式
13 基优化方法种？
14 写文法G 语言 L(G){abncn| n≥0}
15 考虑面程序：
…
procedure p(x y z)
begin
yy+z
zy*z+x
end
begin
a2
b3
p(a+b b a)
print a
end
试问参数传递方式分采传址传值时程序执行输出 a值什
16写出表达式a＋b*(cd)e逆波兰式三元序列
17证明文法G(A)
A→AA | (A)| ε
二义性
18令Σ{ab}正规式a*b|b*a 表示正规集什？
19谓DISPLAY表？作什？
20考虑面程序：
…
procedure p(x y z)
begin
yy+2
zz+x
end
begin
a5
b2
p(a+b ab a)
print a
end
试问参数传递方式分采传址传值时程序执行输出 a值什
21写文法G 语言 L(G){anbncm| n>0奇数 m>0偶数}
22写出表达式a(b+c)*e+(b+c)f逆波兰式三元序列
23文法GLL(1)文法充条件什？
24已知文法G[S]
S→S*aF | aF | *aF
F→+aF | +a
消文法左递提公左子
25符号表作什？符号表查找整理技术种？
答案：1求文法G[S]
S→AB |B A0
A→AD |C
B→2 |4 |6 |8
C→1 |3 |5 |7 |9 |B
D→0 |C
2输出4231
3句子b(aa)b规范约程：
步骤
符号栈
输入串
动作
0
#
b(aa)b#
预备
1
#b
(aa)b#
移进
2
#b(
aa)b#
移进
3
#b(a
a)b#
移进
4
#b(A
a)b#
约
5
#b(Ma
)b#
移进
6
#b(Ma)
b#
移进
7
#b(B
b#
约
8
#bA
b#
约
9
#bAb
#
移进
10
#S
#
接受
4传址 A6 B16
传值 A2 B4
5L(G){danbm |n>0 m≥0}
6证明：
文法G[S]存句子aa两左推导文法G[S]二义性
S>SaS>SaSaS>aSaS>aaS>aa
S>SaS>aS>aSaS>aaS>aa
7句子 adccd 分析程：
步骤
符号栈
输入串
产生式
0
#S
adccd#
1
#AB
adccd#
S→BA
2
#AAa
adccd#
B→aA
3
#AA
dccd#
4
#Ad
dccd#
A→d
5
#A
ccd#
6
#SB
ccd#
A→BS
7
#Sc
ccd#
B→c
8
#S
cd#
9
#AB
cd#
B→c
10
#Ac
d#
11
#A
d#
12
#d
d#
A→d
13
#
#
8求文法G[S]
S→AB
A→aAc | D
D→bD | b
B→aBb | aabb
9
函数
a
(
)
f
4
2
4
4
g
5
5
2
3
10优化：程序进行种等价变换变换程序出发产生更效目标代码
三种级：局部优化循环优化全局优化
11目标代码通常采三种形式：机器语言汇编语言装配机器语言模块
应着重考虑问题：
(1)生成目标代码较短
(2)充分利寄存器减少访问存次数
(3)充分利指令系统特点
12正规式 a ( a | b )*
13删余运算代码外提强度削弱变换循环控制条件合已知量复写传播删赋值
14文法G[S]
S→aB | a
B→bc |bBc
15传值 a2
传址 a15
16逆波兰式 abcd*e+
三元序列 op arg1 arg2
(1) c d
(2) * b (1)
(3) (2) e
(4) + a (3)
17证明：
文法G[S]存句子 () 两左推导文法G[S]二义性
A>AA>(A)A>()A>()
A>AA>A>(A)>()
18(a*b|b*a){ababbaaabbba……}
19Display表 嵌套层次显示表
程嵌套允许层程引外层程定义数程运行时必须踪外层程新活动记录起始址 display表登记外层程新活动记录起始址
20传址 a12
传值 a5
21求文法G[S]
S→AC
A→aaAbb | ab
C→ccC | cc
22逆波兰式 abc+e*bc+f+
三元序列 op arg1 arg2
(1) + b c
(2) * (1) e
(3) + b c
(4) (3) f
(5) + (2) (4)
(6) a (5)
23文法GLL(1)文法充条件
(1) FIRST(α) ∩FIRST(β)Ф
(2) 果 β*>ε FIRST(α) ∩FOLLOW(A) Ф
24消左递
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF | +a
提公左子文法 G’(S)
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF’
F’→F |ε
25作：登记源程序中出现种名字信息解阶段进展状况
技术：线性表折查找杂奏技术
五计算题：
1设文法G(S)
S→^ | a | (T)
T→TS | S
⑴ 消左递
⑵ 构造相应FIRSTFOLLOW集合
⑶ 构造预测分析表
2语句 if E then S
(1) 改写文法适合语法制导翻译
(2) 写出改写产生式语义动作
3设文法G（S）：
S→(T) | a
T→T+S | S
(1）计算FIRSTVT LASTVT
（2）构造优先关系表
4设某语言for语句形式
for i＝E(1) to E(2) do S
语义解释
i＝E(1)
LIMIT＝E(2)
again if i＜＝LIMIT then
Begin
S
i＝i＋1
goto again
End
（1）写出适合语法制导翻译产生式
（2）写出产生式应语义动作
5语句
while a<10 do
if c>0 then aa+1
else aa*31
翻译成四元式序列
6设基块
DAC
EA*C
FD*E
S2
TAC
QA*C
G2*S
JT*Q
KG*5
LK+J
ML
假设基块出口时M引请写出优化四元序列
7已知文法G(S)
S→a | ^ | (T)
T→TS | S
(1) 出句子(a(aa))左推导
(2) 出句型((TS)a)短语 直接短语句柄
8 C 语言do S while E语句
(1)改写文法适合语法制导翻译
(2)写出改写产生式语义动作
9已知文法G(S)
S→aAcBe
A→Ab| b
B→d
(1)出句子abbcde左推导画出语法树
(2)出句型aAbcde短语素短语
10设文法G(S)
S→(T) | aS | a
T→TS | S
⑴消左递提公左子
⑵构造相应FIRSTFOLLOW集合
⑶构造预测分析表
11语句
if X>0 ∨ Y<0
then while X>0 do XA*3
else YB+3
翻译成四元式序列
12已知文法G(S)
E→E+T | T
T→T*F| F
F→(E)| i
(1) 出句型 (i+i)*i+i左推导画出语法树
(2) 出句型 (E+T)*i+F 短语素短语左素短语
13设文法G（S）：
S→T | S∨T
T→U |T∧U
U→i |U
（1）计算FIRSTVT LASTVT
（2）构造优先关系表
答案：(1)消左递文法变G’[S]：
S→^ | a | (T)'
T→ST’ | S
T’→ST’ |ε
文法左公左子
(2)构造相应FIRSTFOLLOW集合：
FIRST(S){a ^ (} FOLLOW(S){# )}
FIRST(T){a ^ (} FOLLOW(T){}}
FIRST(T’){ ε} FOLLOW(F){)}
(3)构造预测分析表：
a
^
(
)
#
S
S→a
S→^
S→(T)'
T
T→ST’
T→ST’
T→ST’
T’
T’→ε
T’→ST’
2 (1)
C→if E then
S→CS(1)
(2)
C→if E then {BACK(ETC NXQ) CchainEFC}
S→CS(1) {SchainMERG(CChain S(1) Chain)}
3 (1) FIRSTVT(S){a ( }
FIRSTVT(T){+ aa (}
LASTVT(S){a ) }
LASTVT(T){+ a )}
(2)
a
+
(
)
a
>
>
+
<
>
<
>
(
<
<
<
)
>
>
>
4 (1) F→for iE(1) to E(2) do
S→FS(1)
(2) F→for iE(1) to E(2) do
{GEN( E(1)place _ entry(i))
Fplaceentry(i)
LIMITNewtemp
GEN( E(2)place _ LIMIT)
QNXQ
FQUADq
GEN(j≤ entry(i) LIMIT q+2)
FchainNXQ
GEN(j _ _ 0)}
S→FS(1)
{BACKPATCH(S(1)chain NXQ)
GEN(+ Fplace 1 Fplace)
GEN(j _ _ FQUAD)
SchainFchain
}
5 (1) (j< a 10’ (3))
(2) (j _ _ (12))
(3) (j> c 0’ (5))
(4) (j _ _ (8))
(5) (+ a 1’ T1))
(6) ( T1 _ a)
(7) (j _ _ (1))
(8) (* a 13’ T2)
(9) ( T2 1’ T3)
(10) ( T3 _ a)
(11) (j _ _ (1))
6优化四元序列
DAC
EA*C
FD*E
MF+20
7 左推导
S(T)>(TS)>(SS)>(aS)>(a(T))>(a(TS))>(a(SS))>(a(aS))>(a(aa))
短语
((TS)a)
(TS)a
(TS)
TS
a
直接短语
TS
a
句柄
TS
8(1)
S→do M1 S1 while M2 E
M→ε
(2)
M→ε {Mquadnestquad}
S→do M1 S1 while M2 E {backpatch(s1nextlist M2quad)
backpatch(Etruelist M1quad)
SnextlistEfalelist
}
9(1) S>aAcBe>AAbcBe>abbcBe>abbcde
(2) 短语 aAbcde Ab d
素短语 Ab d
10(1) S →(L) | aS’
S’→S |ε
L→SL’
L’→SL’ |ε
(2) FIRST(S){a (} FIRST(S’){a ( ε}
FIRST(L){a (} FIRST(L’){ ε}
FOLLOW(S){ ) #} FOLLOW(S’){ ) #}
FOLLOW(L){ )} FOLLOW(L’){ )}
(3)
(
)
a
#
S
S →(L)
S → aS’
S’
S’→S
S’→ε
S’→S
S’→ε
S’→ε
L
L→SL’
L→SL’
L’→SL’
L’
L’→ε
11(1) (j> X 0 (5))
(2) (j _ _ (3))
(3) (j< Y 0 (5))
(4) (j _ _ (11))
(5) (j>0 X 0 (7))
(6) (j _ _ (7))
(7) (* A 3 T1)
(8) ( T1 _ N)
(9) (j _ _ (5))
(10) (j _ _ (13))
(11) (+ B 3 T2)
(12) ( T2 _ Y)
12(1) E>E+T>T+T>T*F+T>F*F+T>(E)*F+T>(E+T)*F+T>(T+T)*F+T
>(F+T)*F+T>(i+T)*F+T>(i+F)*F+T>(i+i)*F+T>(i+i)*i+T
>(i+i)*i+F>(i+i)*i+i
(2) 短语 i F E+T (E+T) (E+T)*i (E+T)*i+F
素短语 i E+T
左素短语 E+T
13(1) FIRSTVT(S){∨ ∧ i }
FIRSTVT(T){∧ i }
FIRSTVT(U){i }
LASTVT(S){∨ ∧ i }
LASTVT(T){∧ i }
LASTVT(U){i }
(2)
i
∨
∧
S
>
>
∨
<
>
<
<
∧
<
>
>
<
<
>
>
<
编译原理期末试题（二）
1描述正规式b*(abb*)*(a| e)定义语言画出接受该语言简DFA
2证明文法E ® E + id | idSLR(1)文法
3面表达式赋值语句文法中and类型bool ´ bool ® bool+类型int ´ int ® int类型int ´ int ® bool 求id E类型int者bool该文法写语法制导定义翻译方案完成类型检查
S ® id E
E ® E and E | E + E | E E |id
4面C语言文件sc
f1(int x)
{
long x
x 1
}
f2(int x)
{
{
long x
x 1
}
}
某编译器编译时报错：
sc In function f1’
sc3 warning declaration of x’ shadows a parameter
请回答函数f2什没类似警告错误
5面C语言程序非优化编译运行时输入2结果
area12566360 addr1073743076
优化编译运行时输入2结果
area12566360 addr1073743068
请解释什输出结果区
main()
{
float s pi r
pi314159
scanf(f &r)
printf(areaf addrd\n spi*r*r &r)
}
6描述正规式b*a(bb*a) *b*定义语言画出接受该语言简DFA
7面文法产生代表正二进制数01串集：
B ® B 0 | B 1 | 1
面翻译方案计算种正二进制数十进制值：
B ® B1 0 {Bval B1val ´ 2 }
| B1 1 {Bval B1val ´ 2 +1}
| 1 {Bval 1 }
请消该基础文法左递重写翻译方案然计算种正二进制数十进制值
8 C语言中果变量ijlong类型请写出表达式&i表达式&i&j类型表达式帮助回答问题面出程序作提示运行时输出1
main() {
long i j
printf(d\n &i&j)
}
9C语言函数：
func(i) long i {
long j
j i – 1
func(j)
}
面左右两边汇编代码两版GCC编译器该函数产生代码左边代码调func前参数压栈调结束参数退栈右边代码参数传递处理方式没实质区请叙述右边代码参数传递处理方式推测带优点
func | func
pushl ebp | pushl ebp
movl esp ebp | movl esp ebp
subl 4 esp | subl 8 esp
movl 8(ebp) edx | movl 8(ebp) eax
decl edx | decl eax
movl edx 4(ebp) | movl eax 4(ebp)
movl 4(ebp) eax | movl 4(ebp) eax
pushl eax | movl eax (esp)
call func | call func
addl 4 esp | leave
leave | ret
ret |
编译原理试卷八答案
start
1
a
b
b
2
1正规式b*(abb*)*(a| e)定义语言字母表{a b}含子串aa串集合简DFA：
2先出接受该文法活前缀DFA：
E¢ ®·E
E ®·E + id
E ®·id
I0
E¢ ® E·
E ® E·+ id
I1
E ® id·
I2
E
id
+
E ® E +·id
I3
E ® E + id·
I4
id
I0I3移进项目肯定会引起突I2I4移进项目仅含约项目肯定会引起突I1中E¢继符号第2项目展符号+样I1肯定会引起突断定该文法SLR(1)
3语法制导定义
S ® id E { Stype if (idtype bool and Etype bool) or (idtype int and Etype int)then type_ok else type_error }
E ® E1 and E2 { Etype if E1type bool and E2type bool then bool else type_error }
E ® E1 + E2 { Etype if E1type int and E2type int then int else type_error }
E ® E1 E2 { Etype if E1type int and E2type int then bool else type_error }
E ® id { Etype lookup(identry) }
4函数f1局部变量x声明作域整函数体导致函数体中访问形式参数x合法C语言函数编译器出警告错误
函数f2局部变量x作域函数体部分会出现述问题编译器报错
5非优化编译时变量s pi r局部数区分配4字节空间优化编译时复写传播pi*r*r 变成314159*r*rpi314159成赋值删函数中pi引必pi分配空间类似s314159*r*r赋值（表达式计算赋值）必s分配空间样非优化情况相局部数区少8字节 r址高址方移动8字节
6正规式b*a(bb*a) *b*体现特点a左边干b非a第字母该正规式定义语言：少含a含子串aaab串集简DFA：
start
2
a
b
b
1
0
a
b
7 消左递文法：
B ® 1 B¢
B¢ ® 0 B¢ | 1 B¢ | e
相应翻译方案：
B ® 1 {B¢i 1 }B¢{Bval B¢val}
B¢ ® 0 {B¢1i B¢i ´ 2 } B¢1 {B¢val B¢1val}
| 1 {B¢1i B¢i ´ 2 +1} B¢1 {B¢val B¢1val}
| e {B¢val B¢i}
8表达式&i类型表达式pointer(long)表达式&i&j类型表达式longC语言规定指类型两指针相加减值差间元素数
9左边编译器版：般局部变量分配空间调函数前干次pushl指令参数压栈返回addl n esp次参数退栈（常数n根调前做少次pushl决定）
右边编译器版：局部变量分配空间外时函数中出现函数调参数分配空间参数空间栈顶调函数前movl指令参数移入栈顶调结束需参数退栈指令
优点次函数调结束需执行addl n esp指令外增加优化性
编译原理期末试题（三）
1 优化范围角度优化分两类？循环优化三种？
答：优化范围角度优化分局部优化全局优化两类
循环优化三种：循环变表达式外提纳变量删计算强度削减
2写出表达式ab*c+b*d应逆波兰式四元式序列三元式序列
答：逆波兰式： abc*bd*+
四元式序列： 三元式序列 OP ARG1 ARG2
(1) (* b c t1) (1) (* b c )
(2) (* b d t2) (2) (* b d )
(3) (+ t1 t2t3) (3) (+ (1) (2))
(4) ( t3 a) (4) ( (3) a)
3文法G(S)
S
b
M
(
T
M
a
b
L
)
答：1）
2） 短语 Ma) (Ma) b(Ma)b
直接短语 Ma) 句柄 Ma)
三 设字母表{ab}正规式R(ab|a)*
解：（1）
0
1
2
3
b
a
a
ε
ε
+
（2）（1）非确定限动机确定化
ε
a
b
0
1
1
3
12
2
1
+3
a
b
+013
123
+123
123
13
+13
123
0
1
2
a
a
b
a
+
+
+
（3）（2）DFA化简合状态02 状态2：
1
2
a
a
b
+
+
（4）令状态12分应非终结符BA
G A→aB|a|ε B→aB|bA|a|b|ε化简：G A→aB|εB→aB|bA|ε
四 设文法G改写成等价LL(1)文法构造预测分析表
G：S→S*aT|aT|*aT T→+aT|+a
解：消左递文法G’ S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公子文法G’’
S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT’
T’→T|ε
Select(S→aTS’){a}
Select(S→*aTS’){*}
Select(S→aTS’)∩Select(S→*aTS’)Ф
Select(S’→*aTS’){*}
Select(S’→ε)Follow(s’){#}
Select(S’→*aTS’)∩Select(S’→ε) Ф
Select(T→+aT’){+}
Select(T’→T)First(T) {+}
Select(T’→ ε)Follow(T’){*#}
Select(T’→T)∩Select(T’→ε) Ф
该文法LL(1)文法
预测分析表：
*
+
a
#
S
→*aTS’
→aTS’
S’
→*aTS’
→ε
T
→+aT’
T’
→ ε
→T
→ ε
6设文法G ：
S→AA→BA|εB→aB|b
解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4) B→aB (5) B→b FIRST(A) {ε a b}FIRST(B) {a b}
构造DFA
项目集规范族出存突动作∴该文法LR(1)文法
（2） LR(1)分析表：
(3)输入串abab 分析程：
简答题 3设文法G[S] S→S(S)S|ε该文法否二义文法？说明理 答：二义（）（）构造两棵语法树
S S
S ( S ) S S ( S ) S
ε ε S ( S ) S S ( S ) S ε ε
ε ε ε ε ε ε
五 定文法G[S]：
S→aA|bQ A→aA|bB|bB→bD|aQ Q→aQ|bD|bD→bB|aA E→aB|bF
F→bD|aE|b
构造相应DFA
解：先构造NFA： 子集法NFA确定化：
a
b
S
A
Q
A
A
BZ
Q
Q
DZ
BZ
Q
D
DZ
A
B
D
A
B
B
Q
D
SAQBZDZDB重新命名分0123456表示34中含z终态
a
b
0
1
2
1
1
3
2
2
4
3
2
5
4
1
6
5
1
6
6
2
5
令P0＝（｛01256｝｛34｝）b进行分割：
P1＝（｛05 6｝｛12｝｛34｝）b进行分割：
P2＝（｛0｝｛5 6｝｛12｝｛34｝）ab 进行分割变
令｛０｝A｛12｝B｛34｝C｛56｝D
化右图
六 文法G(S)：S → a | ^ | (T)T → TS | S
答：(1)
a
^
(
)
#
a
>
>
>
^
>
>
>
(
<
<
<
<
)
>
>
>
<
<
<
>
>
#
<
<
<
(2) 算符优先文法两终结符间种优先关系（2分）
(3) 出输入串(aa)#算符优先分析程
步骤
栈
前输入字符
剩余输入串
动作
1
#
(
aa#
#<( 移进
2
#(
a
a)#
(3
#(a
a)#
a> 约
4
#(N
a)#
(< 移进
5
#(N
a
)#
6
#(Na
)
#
a>) 约
7
#(NN
）
#
>) 约
8
#(N
)
#
() 移进
9
#(N)
#
)># 约
10
#N
#
接受
编译原理期末试题（四）
简述编译程序工作程（10）
编译程序工作程指输入源程序开始输出目标程序止整程非常复杂程言般划分五工作阶段：①词法分析构成源程序字符串进行扫描分解识出单词②语法分析根语言语法规单词符号串分解成类语法单位③语义分析中间代码产生类语法单位分析含义进行初步翻译④代码优化期产生更高效代码⑤目标代码生成中间代码变换成特定机器低级语言指令形式
二构造列正规式相应DFA（状态转换图表示）（15）
（1） 1（0 | 1）*1
01
（2） 0*10*10*10*1
（3） letter（letter | digit）*
3
1
0
2
1
（1）
0
0
5
1
（2）
1
0
4
1
3
0
2
1
1
letter
(3)
2
letter
1
digit
三出面语言相应文法：（15）
L1{an bn | n≥1} L2{anbm+nam | n≥1m≥0}
G1：
A→aAb |ab
G1：
S→AB
A→aAb | ab
B→bBa | ε
四面文法G：
S→a | b | （T）
T→TS | S
(1) 消文法左递等价文法G2
(2) 判断文法G2否LL（1）文法果出预测分析表（15）
G2：
S→a | b | （T）
T→ ST’
T’→S T’ | ε
G2LL（1）文法
a
b
（
）
#
S
S→a
S→b
S→（T）
T
T→ ST’
T→ ST’
T→ ST’
T’
T’→ ε
T’→S T’
五设文法G[A]：
A→BCc | gDB
B→bCDE |ε
C→DaB | ca
D→dD |ε
E→gAf | c
(1) 计算该文法非终结符FIRST集FOLLOW集
(2) 试判断该文法否LL（1）文法（15）
FIRST
FOLLOW
A
B
C
D
E
Abcdg
b
Acd
D
Cg
Acd
Cdg
Abcg
LL（1）文法
六表达式文法G：
E → E+T | T
T → T*F | F
F → (E) | I
（1）造非终结符FIRSTVTLASTVT集合
（2）构造文法算符优先关系表（15）
FIRSTVT
LASTVT
E
T
F
*+（i
*（i
（i
*+）i
*）i
）i
算符优先关系表
+
*
I
（
）
#
+
*
I
（
）
#
>
>
>
<
>
<
<
>
>
<
>
<
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
七定义二进制整数文法：
L →LB | B
B →0 | 1
构造翻译模式计算该二进制数值（十进制值）（15）
引入LB综合属性val翻译模式：
S →L {print(Lval)}
L →L1B {Lval L1val*2+Bval}
L →B {Lval Bval}
B →0 {Bval0}
B →1 {Bval1}
编译原理期末试题（五）
单项选择题(10题题2分20分)
1．语言
A．句子集合 B．产生式集合
C．符号串集合 D．句型集合
2．编译程序前三阶段完成工作
A．词法分析语法分析代码优化
B．代码生成代码优化词法分析
C．词法分析语法分析语义分析中间代码生成
D．词法分析语法分析代码优化
3．句型中称句柄该句型左
A．非终结符号 B．短语 C．句子 D．直接短语
4．推动机识语言
A．0型语言 B．1型语言
C．2型语言 D．3型语言
5．扫描器完成务字符串形式源程序中识出具独立含义语法单位
A． 字符 B．单词 C．句子 D．句型
6．应Chomsky四种文法四种语言间关系
A．L0ÌL1ÌL2ÌL3 B．L3ÌL2ÌL1ÌL0
C．L3L2ÌL1ÌL0 D．L0ÌL1ÌL2L3
7．词法分析务
A．识单词 B．分析句子含义
C．识句子 D．生成目标代码
8．常中间代码形式含
A．三元式 B．四元式 C．逆波兰式 D．语法树
9． 代码优化目
A．节省时间 B．节省空间
C．节省时间空间 D．编译程序进行等价交换
10．代码生成阶段务
A．高级语言翻译成汇编语言
B．高级语言翻译成机器语言
C．中间代码变换成赖具体机器目标代码
D．汇编语言翻译成机器语言
二填空题（题5题题2分10分）
1．编译程序首先识出源程序中(单词)然分析(句子)翻译意义
2．编译器常语法分析方法(底)(顶)两种
3．通常编译程分分析前端综合端两阶段词法语法语义分析源程序(分析)中间代码生成代码优化目标代码生成源程序(综合)
4．程序设计语言发展带日渐变运行时存储理方案分两类(静态存储分配)方案(动态存储分配)方案
5．编译程序言输入数(源程序)输出结果(目标程序)
三名词解释题(5题题4分20分)
1．词法分析
词法分析务左右扫描行源程序符号词法规
构成源程序字符串中识出具独立意义语法单位
转换成统部表示(token)送语法分析程序
2．LL(1)文法
文法两产生式A ® a | b满足面两条件：
（1）FIRST(a ) Ç FIRST(b ) f
（2）b Þ* e FIRST(a ) Ç FOLLOW( A ) f
满足两条件文法做LL(1)文法中第L代表左
右扫描输入第二L表示产生左推导1代表决定分析器步
动作时前输入符号没公左子外LL(1)文法
明显性质二义含左递
3．语法树
句子树结构表示法称语法树(语法分析树语法推导树)
定文法G(VNVTPS)G句型构造关联
语法树棵树具列特征：
(1)根节点标记开始符号S
(2)节点标记V中符号
(3)棵子树根节点A直接子孙标记左右排列
次序A1A2…ARA®A1A2…AR定P中条产生式
(4)标记A节点少外子孙AVN
(5)树叶节点标记左右排列字符串ww文法G
句型w中仅含终结符号w文法G产生句子
4．LR(0)分析器
谓LR(0)分析指左右扫描底语法分析分析
步须根分析栈前已移进约出全部文法符号
前查0输入符号确定相某产生式左部符号句柄否
已分析栈顶部形成确定前应采取分析动作 (
移进某产生式进行约等)
5．语言文法
文法语言结构定义描述穷非空产生式集合
文法G定义四元组形式：
G(VNVTPS)
中：VN 非空穷集合称非终结符号集合VT 非空穷集合
称终结符号集合P产生式集合(非空)S开始符号(识符号)
里VN∩VTÆSVNVVN∪VT称文法G字母表出现
文法产生式中切符号集合
文法G描述语言L(G)表示文法G产生全部句子组成
L(G){x| SÞ*x中S文法开始符号 }
简单说文法描述语言该文法切句子集合
四简答题(4题题5分20分)
1．编译程序高级语言什区
汇编语言高级语言编写程序必须先送入计算机转换成机器
语言表示目标程序（程编译）计算机执行执行转换程
程序编译程序汇编程序指没编译汇编语言源文件编译程序转
换目标程序机器语言
编译程序工作情况三种：汇编型解释型编译型汇编型编译程序
汇编语言编写程序应关系转换成机器语言表示程序
解释型编译程序高级语言程序语句先解释成组机器语言指令
然立执行执行完取组语句解释执行继续完成程序
止解释型编译程序执行速度慢进行计算机话时
修改高级语言程序BASIC语言解释型高级语言编译型编译程序
级语言编写程序次会部翻译成机器语言表示程序程进行快
程中进行机话修改FORTRAN语言编译型高级语言
2．编译程序工作分阶段
词法分析语法分析语义分析源程序进行分析(称编译程序前端)
中间代码生成代码优化代码生成三阶段合称源程序进行综合(称
编译程序端)源程序中间表示建立起源程序等价目标程序
3．简述分析方法
谓分析法输入串开始逐步进行约直约文法
开始符号者说语法树末端开始步步约直根节点
4．简述代码优化目意义
代码优化量生成代码编译阶段程序代码进行
种等价变换保证变换前代码执行结果相前提量目
标程序运行时需时间短时占存储空间少
五综合应题(3题题10分30分)
1．证明述文法G：
S®aSbS|aS|d
二义性文法
解：
文法果存某句子棵语法分析树应称
文法二义性文法
句子aadbd两棵语法树图：
S
a
S
S
a
b
S
d
d
d
S
S
a
b
S
S
a
d
(1) (2)
知S®aSbS|aS|d定义文法二义性文法
A
S
B
b
B
S
a
b
2．文法G[S]：S®ABA®Aa|bBB®a|Sb求句型baSb全部短语直接短语句柄？
句型baSb语法树图五(2)示
解：baSb句型baSb相S短语ba句型baSb相A短语Sb句型baSb相B短语直接短语a句型baSb相B短语直接短语句柄
3．设非确定限动机NFA M({ABC}{01}d{A}{C})中：
d (A0){C} d (A1){AB} d (B1){C} d (C1){C}请画出状态转换距阵状态转换图
解：状态转换距阵：
d
0
1
A
C
AB
B
Æ
C
C
Æ
C
状态转换图1
1
0
1
1
编译原理期末试题（六）
编译原理 样题
1．____型文法称正规文法
[A] 0 [B] 1 [C] 2 [D] 3
2．____文法LL(1)
[A] 递 [B] 右递 [C] 2型 [D] 含公左子
3． 文法E→E+E|E*E|i句子i*i+i*i语法分析树总数______
[A]1 [B]3 [C]5 [D]7
4．四元式间联系通 实现
[A]时变量 [B]指示器 [C]符号表 [D]程序变量
5．心集合会产生新突
[A]二义 [B]移进移进 [C]移进约 [D]约约
6．代码优化时
[A]语法规 [B]词法规 [C]等价变换规 [D]语义规
7．表达式a(b)*c逆波兰表示
[A]ab@c* [B]ab@c* [C]ab@ [D]ab@c* （注：@单目减运算符）
8．程DISPLAY表记录
[A]程连接数 [B]程嵌套层次
[C]程返回址 [D]程入口址
二 填空题
3．文法G1G2L(G1)L(G2) （ G1G2语言相）称文法G1G2等价
4．文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i句型T+T*F+i句柄T 左素短语 T*F
5．右推导逆程称规范约 称 左约
6．规范规约中规约串句柄 算符优先分析中规约串 左素短语
7．（A∨ B）∧（C∨ ¬D∧ E） 逆波兰式ＡＢ∨ＣＤ¬Ｅ∧∨∧
8．属性文法中文法符号两种属性分称继承属性 综合属性（次序换）
9．符号表项名字栏 址分配 两栏目组成目标代码生成阶段符号表 址分配
10．程DISPLAY表容 直接外层 DISPLAY表容加
程SP址
三 穷动机M接受字母表S＝{01}满足述条件串：10直接右边构造DFA MM等价正规式
四 证明正规式(ab)*a 正规式a(ba)*等价 （构造DFA方法）
答案：
五 写文法语言：
L ＝ { 1n0m1m0n | mn≥0 }
五 文法G：S → 1S0 | A
A → 0A1 | ε
六 文法G[S]
S → aSb | P
P → bPc | bQc
Q → Qa | a
(1) 否算符优先文法？请构造算符优先关系表
(2) 文法G[S]消左递提取左公子否LL（1）文法？请证实
1求出G[S]FIRSTVT集LASTVT集：
FIERSTVT（S）{ab} LASTBVT（S）{bc}
FIERSTVT(P){b} LASTBVT（P）{c}
FIERSTVT(Q){a} LASTBVT（Q）{a}
构造优先关系表：
a
b
c
a
< >
<
>
b
< >
c
>
>
优先关系中时出现aabb该文法算符优先文法
2 消左递提取左公子文法：
S → aSb | P
P → bP’
P’→ Pc |Qc
Q → aQ’
Q’→ aQ’|ε
求具相左部两产生式Select集交集：
Select(S→aSb)∩Select(S→P) {a}∩First(P) {a}∩{b} Ф
Select(P’→Pc)∩Select(P’→Qc) First(P)∩First(Q){b}∩{a} Ф
Select(Q’→aQ’)∩Select(Q’→ε) {a}∩Follow(Q) {a}∩{c} Ф
修改文法LL（1）文法
七 已知文法G
（0） S′→ S
（1） S → aAd
（2） S → bAc
（3） S → aec
（4） S → bed
（5） A → e
试构造LR（1）项目集前缀图LR（1）分析表
答案：
e
c
A
d
I0
S′→· S #
S→· aAd #
S→ · bAc #
S→ ·aec #
S→ · bed #
I2：
S→a · Ad #
S→a · ec #
A→· e d
a
I1：S′→S · #
S
I3 S→b · Ac #
S→b · ed #
A→· e c
b
I6 S→bA·c#
A
I7：S→be · d #
A→e · c
I11：
S→bed · #
d
I10：
S→bAc · #
I4：S→aA· d #
I5：S→ae· c # A→e · d
e
I8：S→aAd · #
I9：S→aec · #
c
构造LR(1)分析表
：
r4
11
S10
6
r2
10
r3
9
r1
8
S11
r5
7
r5
S9
5
S8
4
6
S7
3
4
S5
2
acc
1
A
#
S3
b
e
d
c
1
S
goto
a
S2
action
0
状态
八 已知源程序：
prod0
i1
while i≤20 do
begin
prodprod+a[i]*b[i]
ii+1
end
试语法制导翻译法源程序翻译成四元式序列（设A数组a起始址B数组b起始址机器字节编址数组元素占四字节）
答案：
九 设程序段
procedure P(xyz)
begin
Yy*3
ZX+z
end
begin
a5 b2
p(a*baa)
print(a)
end
参数传递方法分（1）传值（2）传址（3）传名试问结果分什？
十 （1）传值 5 （2）传址 25 （3）传名 45
十 文法请写出关括号嵌套层数属性文法(SL引入属性h记录输出配括号数)
文法规
语 义 规
S→(T)
S→i
T→TS
T→S
答案：
十 PL0语言while语句 while 条件B DO 语句S 编译程序
请空缺处填空完成该语句编译算法：
switch (SYM) { ……
case WHILESYM
CX1CX
GetSym()
CONDITION(SymSetAdd(DOSYMFSYS)LEVTX)
CX2CX
GEN(JPC00)
if (SYMDOSYM)
GetSym()
else Error(18)
STATEMENT(FSYSLEVTX)
GEN(JMP0CX1)
CODE[CX2]ACX
break
……}
编译原理期末试题（七）
回答列问题：(30分)
1．什S属性文法？什L属性文法？间什关系？
解答：
S属性文法含综合属性属性文法 （2分）
L属性文法求产生式AàX1X2…Xn语义规中属性者综合属性者Xj继承属性该属性仅赖：
（1） 产生式Xj左边符号X1X2…Xj1属性
（2） A继承属性 （2分）
S属性文法L属性文法特例 （2分）
2．什句柄？什素短语？
句型左直接短语称该句型句柄（3分）素短语样短语少包含终结符包含更素短语（3分）
3．划分程序基块时确定基块入口语句条件什？
解答：
（1）程序第语句
（2）条件转移语句条件转移语句转移语句
（3）紧条件转移语句面语句
4．(6分)运行时DISPLAY表容什？作什？
答：DISPLAY表嵌套层次显示表进入程建立活动记录区时建立张嵌套层次显示表diaplay假定现进入程层次idiaplay表含i+1单元顶单元次存放着现行层直接外层…直外层(程序0层)等层程新活动记录起始址通DISPLAY表访问外层程变量
5．(6分)列四元式序列生成目标代码：
AB*C
DE+F
GA+D
HG*2
中H基块出口活跃变量 R0R1寄存器
答：
LD R0 B
MUL R0 C
LD R1 E
ADD R1 F
ADD R0 R1
MUL R0 2
ST R0 H
注二设S{01}正规集S倒数第二字符1字符串组成请出该字集应正规式构造识该正规集DFA(8分)
答：
构造相应正规式：(0|1)*1(0|1) (3分)
NFA (2分)
1 1
1
0
4
3
2
e e e e 1
0 0
确定化：(3分)
I
{012}
{12}
{123}
{12}
{12}
{123}
{123}
{124}
{1234}
{124}
{12}
{123}
{1234}
{124}
{1234}
0
1
4
3
2
1
0
0 1 0 0
0 1
1 1
三写文法语言L(G){ anbmambn | mn≥1}(6分)
答：文法G(S)
S ® aSb | B
B ® bBa | ba
四文法G(E) (8分)
E®T|E+T
T®F|T*F
F®(E)|i
E
T
F
(
E
)
E
+
T
F
i
T
T
*
F
1 写出句型(T*F+i)右推导画出语法树
2 写出述句型短语直接短语句柄素短语
答：
1 (4分)
EÞTÞFÞ(E) Þ(E+T) Þ(E+F)
Þ(E+i) Þ(T+i) Þ(T*F+i)
2 (4分)
短语：(T*F+i) T*F+i T*F i
直接短语：T*F i
句柄：T*F
素短语：T*F i
五设文法G(S)：(12分)
1． 构造非终结符FIRSTVTLASTVT集合
2． 构造优先关系表优先函数(12分)
答：(6分)
FIRSTVT(S){ i+)( }
FIRSTVT(A){ +)( }
FIRSTVT(B){ )( }
LASTVT(S){ i+*( }
LASTVT(A){ +*( }
LASTVT(B){ *( }
优先关系表 (3分)
i
+
(
)
*
i
>
<
<
<
+
>
>
<
<
>
(
>
>
>
)
<
<
<
*
>
>
>
优先函数 (3分)
i
+
(
)
*
f
2
6
6
1
6
g
1
4
6
6
1
六设某语言dowhile语句语法形式 (9分)
S ® do S(1) While E
语义解释：
真
假
S(1)代码
E代码
针语法分析器求构造该语句翻译模式：
(1) 写出适合语法制导翻译产生式
(2) 写出产生式应语义动作
答：(1) 适合语法制导翻译文法(3分)
G(S)
R® do
U®R S(1) While
S®U E
(2) (6分)
R® do
{ RQUADNXQ }
U®R S(1) While
{ UQUADRQUAD
BACKPATCH(SCHAIN NXQ) }
S®U E
{ BACKPATCH(ETC UQUAD)
SCHAINEFC }
答案二：
(1) S ® do M1 S(1) While M2 E
M ®ε (3分)
(2) M ®ε { MQUAD NXQ } (6分)
S ® do M1 S(1) While M2 E
{
BACKPATCH(S(1)CHAIN M2QUAD)
BACKPATCH(ETC M1QUAD)
SCHAINE FC
}
七(8分)语句
if (A0) then while C>0 do CC+D
翻译成四元式(8分)
答：
100 (j< A X 102)
101 (j 109)
102 (j> B 0 104)
103 (j 109)
104 (j> C 0 106)
105 (j 109)
106 (+ C D T1)
107 ( T1 C)
108 (j 104)
109
(控制结构3分5分)
八(10分) 设基块：
T1S+R
T2 3
T3 12T2
T4SR
AT1T4
T5S+R
BT5
T6T5*T3
BT6
(1)画出DAG图
(2)设AB出基块活跃变量请出优化四元式序列
T1T5 B
3
T2
4
S
R
+
*
_
T3
T4
A
T6B
n4
n5
n1
n2
n3
n6
n8
n7
答：(1) DAG右图：(6分)
(2) 四元式序列：(4分)
T1S+R
T4SR
AT1T4
BT1*4
九(9分) 设已构造出文法G(S)：
(1) S ® BB
(2) B ® aB
(3) B® b
LR分析表
ACTION
GOTO
状态
a
b
#
S
B
0
s3
s4
1
2
1
acc
2
s6
s7
5
3
s3
s4
8
4
r3
r3
5
r1
6
s6
s7
9
7
r3
8
r2
r2
9
r2
假定输入串abab请出LR分析程(步骤出状态符号输入串变化程)
答：
步骤 状态 符号 输入串
0 0 # abab#
1 03 #a bab#
2 034 #ab ab#
3 038 #aB ab#
4 02 #B ab#
5 026 #Ba b#
6 0267 #Bab #
7 0269 #BaB #
8 025 #BB #
9 01 #S # acc
编译原理期末试题（八）
1．（10分）处* *间串构成注解注解中间没*画出接受种注解DFA状态转换图
2．语言L ＝ {ambn | 0 £ m £ 2n}（a数超b数两倍）
写LR（1）文法准超6产生式（超6产生式分写文法LR（1）文法5分）
3．（10分）构造面文法LL（1）分析表
D ® TL
T ® int | real
L ® id R
R ® id R | e
4．（15分）面文法
S ® ( L) | a L ® L S | S
· 出语法制导定义输出配括号数
· 出翻译方案输出a嵌套深度
句子(a (a a) )第题输出2第二题输出1 2 2
5．（10分）Pascal语言for语句含义见教材第222页题713请该语句设计种合理中间代码结构第215页图717方式者第219页图719方式写出设计需写产生中间代码语法制导定义
6．（5分）C语言程序：
func(i1i2i3)
long i1i2i3
{
long j1j2j3
printf(Addresses of i1i2i3 ooo\n&i1&i2&i3)
printf(Addresses of j1j2j3 ooo\n&j1&j2&j3)
}
main()
{
long i1i2i3
func(i1i2i3)
}
该程序某种机器Linux运行结果：
Addresses of i1i2i3 277777754602777777546427777775470
Addresses of j1j2j3 277777754442777777544027777775434
面结果出func 函数3形式参数址次升高3局部变量址次降低试说明什会区
7．（15分）C语言程序某种机器linux操作系统编译结果根生成汇编程序解释程序中四变量作域生存期置初值方式等方面区
static long aa 10
short bb 20
func()
{
static long cc 30
short dd 40
}
file staticc
version 0101
gcc2_compiled
data
align 4
type aa@object
size aa4
aa
long 10
globl bb
align 2
type bb@object
size bb2
bb
value 20
align 4
type cc2@object
size cc24
cc2
long 30
text
align 4
globl func
type func@function
func
pushl ebp
movl espebp
subl 4esp
movw 402(ebp)
L1
leave
ret
Lfe1
size funcLfe1func
ident GCC (GNU) egcs29166 19990314Linux (egcs112 release)
8．（10分）C语言种类型语言强类型语言编译时类型检查保证接受程序没运行时类型错误例编译时类型检查般保证运行时没数组越界请举样例子说明C语言强类型语言
9．（10分）果A机器C语言编译器CCA源码SA（C语言写成）利通量少工作B机器C语言编译器CCB
10．（5分）表达式(lx(lyz(x + y) + z) 3) 4 5(lx(lyz(x + y) + z) 3 5) 4样结果抽象机FAM表达式应目标代码执行效率高？什？
参考答案
1．
1
2
4
start
5
2
others
others
*
*
*
2．LR（1）文法 LR（1）文法 二义文法
S ® AB | aABb S ® AB S ® AASb | e
A ® aaAb | e A ® aaAb | ab | e A ® a | e
B ® Bb | e B ® Bb | e
3． int real id
D D®TL D®TL
T T®int T®real
L L®id R
R R ® id R R ® e
4． S¢ ® S print(Snum)
S ® (L) Snum Lnum +1
S ® a Snum 0
L ® L1S Lnum L1num + Snum
L ® S Lnum Snum
S¢ ® {Sdepth 0} S
S ® {Ldepth Sdepth +1} (L)
S ® a {print(Sdepth)}
L ® {L1depth Ldepth} L1 {Sdepth Ldepth} S
L ® { Sdepth Ldepth} S
5． t1 initial
t2 final
if t1 > t2 goto L1
v t1
L2 stmt
if v t2 goto L1
v v + 1
goto L2
L1
6．实参表达式反序进入活动记录局部变量序活动记录中分配
7．aa静态外部变量bb外部变量分配静态数区（data伪指令开始）bb伪指令globl指明全局解决文件中bb外部引aa文件引cc静态局部变量aabb样生存期整程序分配静态数区cc源程序中作域函数func体目标文件中作域少已整文件避免源文件中外部变量函数静态局部变量名字突进行改名成cc2cc全局cc2前面没伪指令globldd动变量作域函数func体生存期该函数激活期间分配栈区置初值运行时赋值实现
8．例联合体类型检查般编译时完成然面例子静态判断类型错误
union U { int u1 int *u2} u
int *p
uu1 10
p uu2
*p 0
9． · 修改源码SA 代码生成部分产生B机器代码称结果程序SB
· SB提交CCA进行编译执行程序
· SB提交述执行程序进行编译需编译器CCB
10．第表达式执行lyz(x + y) + z) 3时出现参数数足情况FUNVAL值进入栈顶然发现参数数足做成FANVAL情况第二表达式执行(lyz(x + y) + z) 3 5会出现参数数足情况第二表达式执行效率第表达式高
编译原理期末题
1 注设文法G（S）试消左递
G（S）：S—>Ac|c
A—>Bb|b
B—>Sa|a
解：S→abcS′|bcS′|cS′ S′→abcS′|
2 试构造面G（S）等价左递文法
G（S）：S—>Sa|Nb|c
N—>Sd|Ne|f
解：S→fN′bS′|cS′ S′→aS′|dN′bS′| N′→eN′|
3 设文法G（S）：
S—>aBc|bAB
A—>aAb|b
B—>b|ε
①求产生式FIRST集FOLLOW(A)FOLLOW(B)产生式SELECT集
②构造LL(1)分析表分析符号串baabbb否
解：（1）FIRST(aBc){a} FIRST(bAB){b} FIRST(aAb){a} A→b FIRST(A→b){b} B→b FIRST(b) {b} FIRST(ε){ε}
FOLLOW(A){b #} FOOLOW(B){c #}
SELECT(S→aBc){a} SELECT(S→bAB) {b} SELECT(A→aAb){a} SELECT(A→b){b} SELECT(B→b){b} SELECT(B→){c #}
LL(1)分析表表A4示
表A4 LL(1)分析表
输入
VN
输入符号
a
b
c
#
S
S→aBc
S→bAB
A
A→aAb
A→b
B
B→b
B→
B→
（2）分析符号串baabbb成功baabbb该文法句子图A16示
图A16 识串baabbb程
4 列文法G(S)：
S—>D(R) R—>RP|P
P—>S|I D—>i
①计算文法G中非终结符FIRSTVT集LASTVT集
②构造文法G算符优先关系矩阵
解：（1）FIRSTVT(S){( i}FIRSTVT(D) {i}FIRSTVT(R){ ( i}FIRSTVT(P){i (}LASTVT
(S){)}LASTVT(D){i}LASTVT(R) { ) i}LASTVT(P){i )}
（2）算符优先矩阵表A5示
表A5 优先矩阵
(
)
i
#
(
)
i
#
5 已知文法G(S)：
S—>a|(T)
T—>TS|S
①出句子((aa)a)左推导画出语法树②出句型(Ta(T))短语直接短语素短语左素短语句柄活前缀
解：（1）左推导：S(T)(TS)(SS) (aS)(a(T))(a(TS))(a(SS))(a(a S))(a(aa))
语法树：图A16示
图A16 (a(aa))语法树
（2）句型(T a (T))短语直接短语素短语左素短语句柄活前缀语法树（图A17）
短语：a || Ta || (T) || T a (T) || (T a (T))
直接短语：a || (T)
素短语：a || (T)
左素短语：a
句柄：a
活前缀： || ( || (T || (T || (T a
图A17 (Ta(T))语法树
6 设文法Ｇ（Ｓ）：
Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ
Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε
求①ＬＲ（０）项目集族②构造识文法Ｇ（Ｅ）ＤＦＡ
③构造文法Ｇ（Ｅ）SLR（１）分析表
④分析句子ａ１１００ｂ识程
解：（1）（2）LR(0)项目集族识活前缀DFA图A19示
图A19 LR(0)
项目集族DFA
（3）（4）略
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
非题（请括号正确划√错误划×）（2分20分）
1．编译程序高级语言程序解释执行(× )
2．限状态动机中仅唯终态(×)（终态）
3．算符优先文法存算符优先函数应 (√ )
4．语法分析时必须先消文法中左递 (×)
5．LR分析法左右扫描输入串时发现错误准确指出出错点 (√)
6．逆波兰表示法表示表达式时须括号 (√ )
7．静态数组存储空间编译时确定 (×)
8．进行代码优化时应着重考虑循环代码优化提高目标代码效率起更作 (×)
9．两正规集相等必条件应正规式等价 (× )
10．语义子程序描述文法应翻译工作 (×)
二选择题(请前括号选择确切项作答案划勾划错)(4分40分)
1．词法分析器输出结果_____
A．( ) 单词种编码 B．( ) 单词符号表中位置
C．( ) 单词种编码身值 D．( ) 单词身值
2． 正规式 M 1 M 2 等价指_____
A．( ) M1M2状态数相等 B．( ) M1M2边条数相等
C．( ) M1M2识语言集相等 D．( ) M1M2状态数边条数相等
3． 文法G：S→xSx|y识语言_____
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*
4．果文法G二义句子α_____
A．( )左推导右推导应语法树必定相
B．( ) 左推导右推导应语法树
C．( ) 左推导右推导必定相
D．( )存两左推导应语法树相
5．构造编译程序应掌握______
A．( )源程序 B．( ) 目标语言
C．( ) 编译方法 D．( ) 三项
6．四元式间联系通_____实现
A．( ) 指示器 B．( ) 时变量
C．( ) 符号表 D．( ) 程序变量
7．表达式(┐A∨B)∧(C∨D)逆波兰表示_____
A ( ) ┐AB∨∧CD∨ B．( ) A┐B∨CD∨∧
C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨
8 优化生成_____目标代码
A．( ) 运行时间较短 B．( ) 占存储空间较
C．( ) 运行时间短占存空间 D．( ) 运行时间短占存储空间
9．列______优化方法针循环优化进行
A ( ) 强度削弱 B．( ) 删纳变量
C．( ) 删余运算 D．( ) 代码外提
10．编译程序_____区标识符作域
A ( ) 说明标识符程函数名
B．( ) 说明标识符程函数静态层次
C．( ) 说明标识符程函数动态层次
D ( ) 标识符行号
三填空题(空1分10分)
1．计算机执行高级语言编写程序两种途径：___解释____编译___
2．扫描器__词法分析器___接受输入__源程序___源程序进行___词法分析__识出单词符号输出结果单词符号供语法分析器
3．分析法采___移进__约错误处理___接受__等四种操作
4．LR分析器包括两部分：总控程序___张分析表__
5．缀式abc代表表达式___a(bc)__
6．局部优化__基块___范围进行种优化
四简答题（20分）
1 简说明语义分析基功
答：语义分析基功包括 确定类型类型检查语义处理某静态语义检 查
2 考虑文法 G[S]
S → (T) | a+S | a
T → TS | S
消文法左递提取公左子
解：消文法G[S]左递：
S→(T) | a+S | a
T→ST′
T′→ST′| ε
提取公左子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→ST′| ε
3 试表达式 w+(a+b)*(c+d(e10)+8) 写出相应逆波兰表示
解： w a b + c d e 10 + 8 + * +
4 三种基控制结构文法面语句翻译成四元式序列：
while (A
if (A ≥ 1) CC+1
else while (A ≤ D)
AA+2
}
解：该语句四元式序列(中E1E2E3分应A＜C∧B＜DA≥1A≤D关系运算符优先级高)：
100 (j
102 (j
104 (jA1106)
105 (j__108)
106 (+ C 1 C)
107 (j__112)
108 (j≤AD110)
109 (j__112)
110 (+ A 2 A)
111 (j__108)
112 (j__100)
113
5 已知文法 G[S] S → aSb|Sb|b 试证明文法 G[S] 二义文法
证明：
文法G[S]：S→aSb|Sb|b句子aabbbb应两棵语法树：
文法G[S]二义文法
五计算题（10分）
已知文法
A>aAd|aAb| ε
判断该文法否 SLR(1) 文法构造相应分析表输入串 ab# 出分析程
解：增加非终结符S产生原文法增广文法：
S'>A
A>aAd|aAb|ε
面构造LR(0)项目集规范族：
表出状态I0I2存移进约突该文法LR(0)文法I0说：FOLLOW(A)∩{a}{bd#}∩{a}ΦI0状态面输入符号a时移进bd#时约时报错I2说I0完全相结说移进约突解决该文法SLR(1)文法
SLR(1)分析表：
输入串ab#出分析程：
编译原理期末试题（二）
非题：
1文关文法开始符终结符非终结符 ( )
2句型直接短语唯 （ ）
3已证明文法二义性判定 （ ）
4基块DAG表示 （ ）
5程活动记录体积编译时静态确定 （ ）
62型文法定3型文法 （ ）
7句型定句子 ( )
8算符优先分析法次句柄进行约 X 应左素短语 ( )
9采三元式实现三址代码时利中间代码进行优化 （ ）
10编译程中语法分析器务分析单词样构成 ( )
11优先表定存相应优先函数 X ( )
12目标代码生成时应考虑充分利计算机寄存器问题 ( )
13递降分析法种分析法 ( )
14文法改写成LL(1)文法 ( )
15基块入口出口 ( )
16LL(1)文法定二义 ( )
17逆波兰法表示表达试称前缀式 ( )
18目标代码生成时应考虑充分利计算机寄存器问题 ( )
19正规文法产生语言文关文法描述 ( )
20优先表定存相应优先函数 ( )
213型文法定2型文法 ( )
22果文法存某句子应两棵语法树文法二义性 ( )
答案：1× 2× 3× 4√ 5√ 6× 7× 8× 9√ 10× 11×
12√ 13× 14√ 15√ 16√ 17× 18√ 19√ 20× 21√ 22√
二填空题：
2编译程分 （ 词法分析） （语法分析）（语义分析中间代码生成 ）（优化）（目标代码生成 ）五阶段
3果文法存某句子应两棵语法树称文法（ 二义性 ）
4功说程序语言语句体分（ 执行性 ）语句（说明性 ）语句两类
5语法分析器输入（ 单词符号 ）输出（ 语法单位 ）
6扫描器务（ 源程序中 ）中识出（ 单词符号 ）
7符号表中信息栏中登记名字关性质(类型种属占单元址）等等
8程相应DISPLAY表容(现行活动记录址外层新活动记录址)
10常两种动态存贮分配办法（栈式）动态分配（堆式）动态分配
11名字属性包括( 类型)(作域 )
12常参数传递方式(传址）（传值）（传名）
13根优化涉程序范围优化分成(局部优化）（循环优化）（全局优化）三级
14语法分析方法致分两类类（ ）分析法类（ ）分析法
15预测分析程序张（ 分析表 ）（ 符号栈 ）进行联合控制
17张转换图包含限状态中认（初）态实际少（终 ）态
19语法分析语言（语法 ）规进行中间代码产生语言（语义）规进行
21文法G预测分析表M含重定义该文法（LL(1) 文法）文法
22数空间存贮分配 FORTRAN采( 静态策略 PASCAL采( 动态)策略
24右推导称（规范推导）句型称（规范）句型
26文法G仅含终结符号句型称 ( 句子 )
27谓分析法指(开始符号出发推导推出句子）
29局限基块范围优化称（ 局部优化 ）
312型文法称（文关）文法3型文法称（正 ）文法
32条指令执行代价定义(指令访问存次数加1）
33算符优先分析法次(左素短语）进行约
三名词解释题：
1局部优化局限基块范围优化称
2二义性文法果文法存某句子应两棵语法树称文法二义性文法
3DISPLAY表程嵌套层次显示表记录该程外层程新活动记录起始址
5左推导步α>βα中右非终结符换
6语法组规形成产生组合式程序
7文法描述语言语法结构形式规
8基块指程序中序执行语句序列中入口出口入口中第语句出口中语句
9语法制导翻译语法分析程中根产生式应语义子程序进行翻译办法做语法制导翻译
10短语令G文法S划文法开始符号假定αβδ文法G句型果SαAδAβ称β句型αβδ相非终结符A短语
11信息果基块中四元式iA定值四元式j引A值ij间没A定值称j四元式i变量A信息
12规范句型规范推导句型
13扫描器执行词法分析程序
14超前搜索词法分析程中时确定词性需超前扫描干字符
15句柄句型左直接短语
16语法制导翻译语法分析程中根产生式应语义程序进行翻译方法 做语法制导翻译
17规范句型规范推导句型
18素短语素短语指样短语少含终结符身外含更素短语
19语法组规形成产生合式程序
20信息果基块中四元式iA定值四元式j引A值ij间没A定值称j四元式i变量A信息
21语义定义程序意义组规
四简答题：
注1写文法G 语言 0开头偶数集
2已知文法G(S)相应翻译方案
S→aAb {print 1}
S→a {print 2}
A→AS {print 3}
A→c {print 4}
输入acab 输出什？
3 已知文法G(S)
S→bAa
A→(B | a
B→Aa)
写出句子b(aa)b规范约程
4 考虑面程序：
…
procedure p(x y z)
begin
yx+y
zz*z
end
begin
A2
BA*2
P(A A B)
Print A B
end
试问参数传递方式分采传址传值时程序执行输出 A B值什
5．文法G(S)
S→dAB
A→aA| a
B→Bb| ε
描述语言什？
6 证明文法G(S)
S→SaS| ε
二义性
7 已知文法G(S)
S→BA
A→BS| d
B→aA| bS | c
预测分析表
a
b
c
d
#
S
S→BA
S→BA
S→BA
A
A→BS
A→BS
A→BS
A→d
B
B→aA
B→bS
B→c
出句子 adccd 分析程
8 写文法G 语言 L(G){albmclanbn| l>0 m>1 n>2}
9 已知文法G(S)
S→a| (T)
T→TS|S
优先关系表：
关系
a
(
)
a
>
>
(
<
<
<
)
>
>
<
<
>
>
请计算出该优先关系表应优先函数表
10 谓优化？涉程序范围分级优化？
11 目标代码种形式？生成目标代码时通常应考虑问题？
12 字母表Σ{a b}试写出Σa首字组成正规集相应正规式
13 基优化方法种？
14 写文法G 语言 L(G){abncn| n≥0}
15 考虑面程序：
…
procedure p(x y z)
begin
yy+z
zy*z+x
end
begin
a2
b3
p(a+b b a)
print a
end
试问参数传递方式分采传址传值时程序执行输出 a值什
16写出表达式a＋b*(cd)e逆波兰式三元序列
17证明文法G(A)
A→AA | (A)| ε
二义性
18令Σ{ab}正规式a*b|b*a 表示正规集什？
19谓DISPLAY表？作什？
20考虑面程序：
…
procedure p(x y z)
begin
yy+2
zz+x
end
begin
a5
b2
p(a+b ab a)
print a
end
试问参数传递方式分采传址传值时程序执行输出 a值什
21写文法G 语言 L(G){anbncm| n>0奇数 m>0偶数}
22写出表达式a(b+c)*e+(b+c)f逆波兰式三元序列
23文法GLL(1)文法充条件什？
24已知文法G[S]
S→S*aF | aF | *aF
F→+aF | +a
消文法左递提公左子
25符号表作什？符号表查找整理技术种？
答案：1求文法G[S]
S→AB |B A0
A→AD |C
B→2 |4 |6 |8
C→1 |3 |5 |7 |9 |B
D→0 |C
2输出4231
3句子b(aa)b规范约程：
步骤
符号栈
输入串
动作
0
#
b(aa)b#
预备
1
#b
(aa)b#
移进
2
#b(
aa)b#
移进
3
#b(a
a)b#
移进
4
#b(A
a)b#
约
5
#b(Ma
)b#
移进
6
#b(Ma)
b#
移进
7
#b(B
b#
约
8
#bA
b#
约
9
#bAb
#
移进
10
#S
#
接受
4传址 A6 B16
传值 A2 B4
5L(G){danbm |n>0 m≥0}
6证明：
文法G[S]存句子aa两左推导文法G[S]二义性
S>SaS>SaSaS>aSaS>aaS>aa
S>SaS>aS>aSaS>aaS>aa
7句子 adccd 分析程：
步骤
符号栈
输入串
产生式
0
#S
adccd#
1
#AB
adccd#
S→BA
2
#AAa
adccd#
B→aA
3
#AA
dccd#
4
#Ad
dccd#
A→d
5
#A
ccd#
6
#SB
ccd#
A→BS
7
#Sc
ccd#
B→c
8
#S
cd#
9
#AB
cd#
B→c
10
#Ac
d#
11
#A
d#
12
#d
d#
A→d
13
#
#
8求文法G[S]
S→AB
A→aAc | D
D→bD | b
B→aBb | aabb
9
函数
a
(
)
f
4
2
4
4
g
5
5
2
3
10优化：程序进行种等价变换变换程序出发产生更效目标代码
三种级：局部优化循环优化全局优化
11目标代码通常采三种形式：机器语言汇编语言装配机器语言模块
应着重考虑问题：
(1)生成目标代码较短
(2)充分利寄存器减少访问存次数
(3)充分利指令系统特点
12正规式 a ( a | b )*
13删余运算代码外提强度削弱变换循环控制条件合已知量复写传播删赋值
14文法G[S]
S→aB | a
B→bc |bBc
15传值 a2
传址 a15
16逆波兰式 abcd*e+
三元序列 op arg1 arg2
(1) c d
(2) * b (1)
(3) (2) e
(4) + a (3)
17证明：
文法G[S]存句子 () 两左推导文法G[S]二义性
A>AA>(A)A>()A>()
A>AA>A>(A)>()
18(a*b|b*a){ababbaaabbba……}
19Display表 嵌套层次显示表
程嵌套允许层程引外层程定义数程运行时必须踪外层程新活动记录起始址 display表登记外层程新活动记录起始址
20传址 a12
传值 a5
21求文法G[S]
S→AC
A→aaAbb | ab
C→ccC | cc
22逆波兰式 abc+e*bc+f+
三元序列 op arg1 arg2
(1) + b c
(2) * (1) e
(3) + b c
(4) (3) f
(5) + (2) (4)
(6) a (5)
23文法GLL(1)文法充条件
(1) FIRST(α) ∩FIRST(β)Ф
(2) 果 β*>ε FIRST(α) ∩FOLLOW(A) Ф
24消左递
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF | +a
提公左子文法 G’(S)
S→aFS’ | *aFS’
S’→*aFS’ | ε
F→+aF’
F’→F |ε
25作：登记源程序中出现种名字信息解阶段进展状况
技术：线性表折查找杂奏技术
五计算题：
1设文法G(S)
S→^ | a | (T)
T→TS | S
⑴ 消左递
⑵ 构造相应FIRSTFOLLOW集合
⑶ 构造预测分析表
2语句 if E then S
(1) 改写文法适合语法制导翻译
(2) 写出改写产生式语义动作
3设文法G（S）：
S→(T) | a
T→T+S | S
(1）计算FIRSTVT LASTVT
（2）构造优先关系表
4设某语言for语句形式
for i＝E(1) to E(2) do S
语义解释
i＝E(1)
LIMIT＝E(2)
again if i＜＝LIMIT then
Begin
S
i＝i＋1
goto again
End
（1）写出适合语法制导翻译产生式
（2）写出产生式应语义动作
5语句
while a<10 do
if c>0 then aa+1
else aa*31
翻译成四元式序列
6设基块
DAC
EA*C
FD*E
S2
TAC
QA*C
G2*S
JT*Q
KG*5
LK+J
ML
假设基块出口时M引请写出优化四元序列
7已知文法G(S)
S→a | ^ | (T)
T→TS | S
(1) 出句子(a(aa))左推导
(2) 出句型((TS)a)短语 直接短语句柄
8 C 语言do S while E语句
(1)改写文法适合语法制导翻译
(2)写出改写产生式语义动作
9已知文法G(S)
S→aAcBe
A→Ab| b
B→d
(1)出句子abbcde左推导画出语法树
(2)出句型aAbcde短语素短语
10设文法G(S)
S→(T) | aS | a
T→TS | S
⑴消左递提公左子
⑵构造相应FIRSTFOLLOW集合
⑶构造预测分析表
11语句
if X>0 ∨ Y<0
then while X>0 do XA*3
else YB+3
翻译成四元式序列
12已知文法G(S)
E→E+T | T
T→T*F| F
F→(E)| i
(1) 出句型 (i+i)*i+i左推导画出语法树
(2) 出句型 (E+T)*i+F 短语素短语左素短语
13设文法G（S）：
S→T | S∨T
T→U |T∧U
U→i |U
（1）计算FIRSTVT LASTVT
（2）构造优先关系表
答案：(1)消左递文法变G’[S]：
S→^ | a | (T)'
T→ST’ | S
T’→ST’ |ε
文法左公左子
(2)构造相应FIRSTFOLLOW集合：
FIRST(S){a ^ (} FOLLOW(S){# )}
FIRST(T){a ^ (} FOLLOW(T){}}
FIRST(T’){ ε} FOLLOW(F){)}
(3)构造预测分析表：
a
^
(
)
#
S
S→a
S→^
S→(T)'
T
T→ST’
T→ST’
T→ST’
T’
T’→ε
T’→ST’
2 (1)
C→if E then
S→CS(1)
(2)
C→if E then {BACK(ETC NXQ) CchainEFC}
S→CS(1) {SchainMERG(CChain S(1) Chain)}
3 (1) FIRSTVT(S){a ( }
FIRSTVT(T){+ aa (}
LASTVT(S){a ) }
LASTVT(T){+ a )}
(2)
a
+
(
)
a
>
>
+
<
>
<
>
(
<
<
<
)
>
>
>
4 (1) F→for iE(1) to E(2) do
S→FS(1)
(2) F→for iE(1) to E(2) do
{GEN( E(1)place _ entry(i))
Fplaceentry(i)
LIMITNewtemp
GEN( E(2)place _ LIMIT)
QNXQ
FQUADq
GEN(j≤ entry(i) LIMIT q+2)
FchainNXQ
GEN(j _ _ 0)}
S→FS(1)
{BACKPATCH(S(1)chain NXQ)
GEN(+ Fplace 1 Fplace)
GEN(j _ _ FQUAD)
SchainFchain
}
5 (1) (j< a 10’ (3))
(2) (j _ _ (12))
(3) (j> c 0’ (5))
(4) (j _ _ (8))
(5) (+ a 1’ T1))
(6) ( T1 _ a)
(7) (j _ _ (1))
(8) (* a 13’ T2)
(9) ( T2 1’ T3)
(10) ( T3 _ a)
(11) (j _ _ (1))
6优化四元序列
DAC
EA*C
FD*E
MF+20
7 左推导
S(T)>(TS)>(SS)>(aS)>(a(T))>(a(TS))>(a(SS))>(a(aS))>(a(aa))
短语
((TS)a)
(TS)a
(TS)
TS
a
直接短语
TS
a
句柄
TS
8(1)
S→do M1 S1 while M2 E
M→ε
(2)
M→ε {Mquadnestquad}
S→do M1 S1 while M2 E {backpatch(s1nextlist M2quad)
backpatch(Etruelist M1quad)
SnextlistEfalelist
}
9(1) S>aAcBe>AAbcBe>abbcBe>abbcde
(2) 短语 aAbcde Ab d
素短语 Ab d
10(1) S →(L) | aS’
S’→S |ε
L→SL’
L’→SL’ |ε
(2) FIRST(S){a (} FIRST(S’){a ( ε}
FIRST(L){a (} FIRST(L’){ ε}
FOLLOW(S){ ) #} FOLLOW(S’){ ) #}
FOLLOW(L){ )} FOLLOW(L’){ )}
(3)
(
)
a
#
S
S →(L)
S → aS’
S’
S’→S
S’→ε
S’→S
S’→ε
S’→ε
L
L→SL’
L→SL’
L’→SL’
L’
L’→ε
11(1) (j> X 0 (5))
(2) (j _ _ (3))
(3) (j< Y 0 (5))
(4) (j _ _ (11))
(5) (j>0 X 0 (7))
(6) (j _ _ (7))
(7) (* A 3 T1)
(8) ( T1 _ N)
(9) (j _ _ (5))
(10) (j _ _ (13))
(11) (+ B 3 T2)
(12) ( T2 _ Y)
12(1) E>E+T>T+T>T*F+T>F*F+T>(E)*F+T>(E+T)*F+T>(T+T)*F+T
>(F+T)*F+T>(i+T)*F+T>(i+F)*F+T>(i+i)*F+T>(i+i)*i+T
>(i+i)*i+F>(i+i)*i+i
(2) 短语 i F E+T (E+T) (E+T)*i (E+T)*i+F
素短语 i E+T
左素短语 E+T
13(1) FIRSTVT(S){∨ ∧ i }
FIRSTVT(T){∧ i }
FIRSTVT(U){i }
LASTVT(S){∨ ∧ i }
LASTVT(T){∧ i }
LASTVT(U){i }
(2)
i
∨
∧
S
>
>
∨
<
>
<
<
∧
<
>
>
<
<
>
>
<
编译原理期末试题（二）
1描述正规式b*(abb*)*(a| e)定义语言画出接受该语言简DFA
2证明文法E ® E + id | idSLR(1)文法
3面表达式赋值语句文法中and类型bool ´ bool ® bool+类型int ´ int ® int类型int ´ int ® bool 求id E类型int者bool该文法写语法制导定义翻译方案完成类型检查
S ® id E
E ® E and E | E + E | E E |id
4面C语言文件sc
f1(int x)
{
long x
x 1
}
f2(int x)
{
{
long x
x 1
}
}
某编译器编译时报错：
sc In function f1’
sc3 warning declaration of x’ shadows a parameter
请回答函数f2什没类似警告错误
5面C语言程序非优化编译运行时输入2结果
area12566360 addr1073743076
优化编译运行时输入2结果
area12566360 addr1073743068
请解释什输出结果区
main()
{
float s pi r
pi314159
scanf(f &r)
printf(areaf addrd\n spi*r*r &r)
}
6描述正规式b*a(bb*a) *b*定义语言画出接受该语言简DFA
7面文法产生代表正二进制数01串集：
B ® B 0 | B 1 | 1
面翻译方案计算种正二进制数十进制值：
B ® B1 0 {Bval B1val ´ 2 }
| B1 1 {Bval B1val ´ 2 +1}
| 1 {Bval 1 }
请消该基础文法左递重写翻译方案然计算种正二进制数十进制值
8 C语言中果变量ijlong类型请写出表达式&i表达式&i&j类型表达式帮助回答问题面出程序作提示运行时输出1
main() {
long i j
printf(d\n &i&j)
}
9C语言函数：
func(i) long i {
long j
j i – 1
func(j)
}
面左右两边汇编代码两版GCC编译器该函数产生代码左边代码调func前参数压栈调结束参数退栈右边代码参数传递处理方式没实质区请叙述右边代码参数传递处理方式推测带优点
func | func
pushl ebp | pushl ebp
movl esp ebp | movl esp ebp
subl 4 esp | subl 8 esp
movl 8(ebp) edx | movl 8(ebp) eax
decl edx | decl eax
movl edx 4(ebp) | movl eax 4(ebp)
movl 4(ebp) eax | movl 4(ebp) eax
pushl eax | movl eax (esp)
call func | call func
addl 4 esp | leave
leave | ret
ret |
编译原理试卷八答案
start
1
a
b
b
2
1正规式b*(abb*)*(a| e)定义语言字母表{a b}含子串aa串集合简DFA：
2先出接受该文法活前缀DFA：
E¢ ®·E
E ®·E + id
E ®·id
I0
E¢ ® E·
E ® E·+ id
I1
E ® id·
I2
E
id
+
E ® E +·id
I3
E ® E + id·
I4
id
I0I3移进项目肯定会引起突I2I4移进项目仅含约项目肯定会引起突I1中E¢继符号第2项目展符号+样I1肯定会引起突断定该文法SLR(1)
3语法制导定义
S ® id E { Stype if (idtype bool and Etype bool) or (idtype int and Etype int)then type_ok else type_error }
E ® E1 and E2 { Etype if E1type bool and E2type bool then bool else type_error }
E ® E1 + E2 { Etype if E1type int and E2type int then int else type_error }
E ® E1 E2 { Etype if E1type int and E2type int then bool else type_error }
E ® id { Etype lookup(identry) }
4函数f1局部变量x声明作域整函数体导致函数体中访问形式参数x合法C语言函数编译器出警告错误
函数f2局部变量x作域函数体部分会出现述问题编译器报错
5非优化编译时变量s pi r局部数区分配4字节空间优化编译时复写传播pi*r*r 变成314159*r*rpi314159成赋值删函数中pi引必pi分配空间类似s314159*r*r赋值（表达式计算赋值）必s分配空间样非优化情况相局部数区少8字节 r址高址方移动8字节
6正规式b*a(bb*a) *b*体现特点a左边干b非a第字母该正规式定义语言：少含a含子串aaab串集简DFA：
start
2
a
b
b
1
0
a
b
7 消左递文法：
B ® 1 B¢
B¢ ® 0 B¢ | 1 B¢ | e
相应翻译方案：
B ® 1 {B¢i 1 }B¢{Bval B¢val}
B¢ ® 0 {B¢1i B¢i ´ 2 } B¢1 {B¢val B¢1val}
| 1 {B¢1i B¢i ´ 2 +1} B¢1 {B¢val B¢1val}
| e {B¢val B¢i}
8表达式&i类型表达式pointer(long)表达式&i&j类型表达式longC语言规定指类型两指针相加减值差间元素数
9左边编译器版：般局部变量分配空间调函数前干次pushl指令参数压栈返回addl n esp次参数退栈（常数n根调前做少次pushl决定）
右边编译器版：局部变量分配空间外时函数中出现函数调参数分配空间参数空间栈顶调函数前movl指令参数移入栈顶调结束需参数退栈指令
优点次函数调结束需执行addl n esp指令外增加优化性
编译原理期末试题（三）
1 优化范围角度优化分两类？循环优化三种？
答：优化范围角度优化分局部优化全局优化两类
循环优化三种：循环变表达式外提纳变量删计算强度削减
2写出表达式ab*c+b*d应逆波兰式四元式序列三元式序列
答：逆波兰式： abc*bd*+
四元式序列： 三元式序列 OP ARG1 ARG2
(1) (* b c t1) (1) (* b c )
(2) (* b d t2) (2) (* b d )
(3) (+ t1 t2t3) (3) (+ (1) (2))
(4) ( t3 a) (4) ( (3) a)
3文法G(S)
S
b
M
(
T
M
a
b
L
)
答：1）
2） 短语 Ma) (Ma) b(Ma)b
直接短语 Ma) 句柄 Ma)
三 设字母表{ab}正规式R(ab|a)*
解：（1）
0
1
2
3
b
a
a
ε
ε
+
（2）（1）非确定限动机确定化
ε
a
b
0
1
1
3
12
2
1
+3
a
b
+013
123
+123
123
13
+13
123
0
1
2
a
a
b
a
+
+
+
（3）（2）DFA化简合状态02 状态2：
1
2
a
a
b
+
+
（4）令状态12分应非终结符BA
G A→aB|a|ε B→aB|bA|a|b|ε化简：G A→aB|εB→aB|bA|ε
四 设文法G改写成等价LL(1)文法构造预测分析表
G：S→S*aT|aT|*aT T→+aT|+a
解：消左递文法G’ S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公子文法G’’
S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT’
T’→T|ε
Select(S→aTS’){a}
Select(S→*aTS’){*}
Select(S→aTS’)∩Select(S→*aTS’)Ф
Select(S’→*aTS’){*}
Select(S’→ε)Follow(s’){#}
Select(S’→*aTS’)∩Select(S’→ε) Ф
Select(T→+aT’){+}
Select(T’→T)First(T) {+}
Select(T’→ ε)Follow(T’){*#}
Select(T’→T)∩Select(T’→ε) Ф
该文法LL(1)文法
预测分析表：
*
+
a
#
S
→*aTS’
→aTS’
S’
→*aTS’
→ε
T
→+aT’
T’
→ ε
→T
→ ε
6设文法G ：
S→AA→BA|εB→aB|b
解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4) B→aB (5) B→b FIRST(A) {ε a b}FIRST(B) {a b}
构造DFA
项目集规范族出存突动作∴该文法LR(1)文法
（2） LR(1)分析表：
(3)输入串abab 分析程：
简答题 3设文法G[S] S→S(S)S|ε该文法否二义文法？说明理 答：二义（）（）构造两棵语法树
S S
S ( S ) S S ( S ) S
ε ε S ( S ) S S ( S ) S ε ε
ε ε ε ε ε ε
五 定文法G[S]：
S→aA|bQ A→aA|bB|bB→bD|aQ Q→aQ|bD|bD→bB|aA E→aB|bF
F→bD|aE|b
构造相应DFA
解：先构造NFA： 子集法NFA确定化：
a
b
S
A
Q
A
A
BZ
Q
Q
DZ
BZ
Q
D
DZ
A
B
D
A
B
B
Q
D
SAQBZDZDB重新命名分0123456表示34中含z终态
a
b
0
1
2
1
1
3
2
2
4
3
2
5
4
1
6
5
1
6
6
2
5
令P0＝（｛01256｝｛34｝）b进行分割：
P1＝（｛05 6｝｛12｝｛34｝）b进行分割：
P2＝（｛0｝｛5 6｝｛12｝｛34｝）ab 进行分割变
令｛０｝A｛12｝B｛34｝C｛56｝D
化右图
六 文法G(S)：S → a | ^ | (T)T → TS | S
答：(1)
a
^
(
)
#
a
>
>
>
^
>
>
>
(
<
<
<
<
)
>
>
>
<
<
<
>
>
#
<
<
<
(2) 算符优先文法两终结符间种优先关系（2分）
(3) 出输入串(aa)#算符优先分析程
步骤
栈
前输入字符
剩余输入串
动作
1
#
(
aa#
#<( 移进
2
#(
a
a)#
(3
#(a
a)#
a> 约
4
#(N
a)#
(< 移进
5
#(N
a
)#
6
#(Na
)
#
a>) 约
7
#(NN
）
#
>) 约
8
#(N
)
#
() 移进
9
#(N)
#
)># 约
10
#N
#
接受
编译原理期末试题（四）
简述编译程序工作程（10）
编译程序工作程指输入源程序开始输出目标程序止整程非常复杂程言般划分五工作阶段：①词法分析构成源程序字符串进行扫描分解识出单词②语法分析根语言语法规单词符号串分解成类语法单位③语义分析中间代码产生类语法单位分析含义进行初步翻译④代码优化期产生更高效代码⑤目标代码生成中间代码变换成特定机器低级语言指令形式
二构造列正规式相应DFA（状态转换图表示）（15）
（1） 1（0 | 1）*1
01
（2） 0*10*10*10*1
（3） letter（letter | digit）*
3
1
0
2
1
（1）
0
0
5
1
（2）
1
0
4
1
3
0
2
1
1
letter
(3)
2
letter
1
digit
三出面语言相应文法：（15）
L1{an bn | n≥1} L2{anbm+nam | n≥1m≥0}
G1：
A→aAb |ab
G1：
S→AB
A→aAb | ab
B→bBa | ε
四面文法G：
S→a | b | （T）
T→TS | S
(1) 消文法左递等价文法G2
(2) 判断文法G2否LL（1）文法果出预测分析表（15）
G2：
S→a | b | （T）
T→ ST’
T’→S T’ | ε
G2LL（1）文法
a
b
（
）
#
S
S→a
S→b
S→（T）
T
T→ ST’
T→ ST’
T→ ST’
T’
T’→ ε
T’→S T’
五设文法G[A]：
A→BCc | gDB
B→bCDE |ε
C→DaB | ca
D→dD |ε
E→gAf | c
(1) 计算该文法非终结符FIRST集FOLLOW集
(2) 试判断该文法否LL（1）文法（15）
FIRST
FOLLOW
A
B
C
D
E
Abcdg
b
Acd
D
Cg
Acd
Cdg
Abcg
LL（1）文法
六表达式文法G：
E → E+T | T
T → T*F | F
F → (E) | I
（1）造非终结符FIRSTVTLASTVT集合
（2）构造文法算符优先关系表（15）
FIRSTVT
LASTVT
E
T
F
*+（i
*（i
（i
*+）i
*）i
）i
算符优先关系表
+
*
I
（
）
#
+
*
I
（
）
#
>
>
>
<
>
<
<
>
>
<
>
<
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
七定义二进制整数文法：
L →LB | B
B →0 | 1
构造翻译模式计算该二进制数值（十进制值）（15）
引入LB综合属性val翻译模式：
S →L {print(Lval)}
L →L1B {Lval L1val*2+Bval}
L →B {Lval Bval}
B →0 {Bval0}
B →1 {Bval1}
编译原理期末试题（五）
单项选择题(10题题2分20分)
1．语言
A．句子集合 B．产生式集合
C．符号串集合 D．句型集合
2．编译程序前三阶段完成工作
A．词法分析语法分析代码优化
B．代码生成代码优化词法分析
C．词法分析语法分析语义分析中间代码生成
D．词法分析语法分析代码优化
3．句型中称句柄该句型左
A．非终结符号 B．短语 C．句子 D．直接短语
4．推动机识语言
A．0型语言 B．1型语言
C．2型语言 D．3型语言
5．扫描器完成务字符串形式源程序中识出具独立含义语法单位
A． 字符 B．单词 C．句子 D．句型
6．应Chomsky四种文法四种语言间关系
A．L0ÌL1ÌL2ÌL3 B．L3ÌL2ÌL1ÌL0
C．L3L2ÌL1ÌL0 D．L0ÌL1ÌL2L3
7．词法分析务
A．识单词 B．分析句子含义
C．识句子 D．生成目标代码
8．常中间代码形式含
A．三元式 B．四元式 C．逆波兰式 D．语法树
9． 代码优化目
A．节省时间 B．节省空间
C．节省时间空间 D．编译程序进行等价交换
10．代码生成阶段务
A．高级语言翻译成汇编语言
B．高级语言翻译成机器语言
C．中间代码变换成赖具体机器目标代码
D．汇编语言翻译成机器语言
二填空题（题5题题2分10分）
1．编译程序首先识出源程序中(单词)然分析(句子)翻译意义
2．编译器常语法分析方法(底)(顶)两种
3．通常编译程分分析前端综合端两阶段词法语法语义分析源程序(分析)中间代码生成代码优化目标代码生成源程序(综合)
4．程序设计语言发展带日渐变运行时存储理方案分两类(静态存储分配)方案(动态存储分配)方案
5．编译程序言输入数(源程序)输出结果(目标程序)
三名词解释题(5题题4分20分)
1．词法分析
词法分析务左右扫描行源程序符号词法规
构成源程序字符串中识出具独立意义语法单位
转换成统部表示(token)送语法分析程序
2．LL(1)文法
文法两产生式A ® a | b满足面两条件：
（1）FIRST(a ) Ç FIRST(b ) f
（2）b Þ* e FIRST(a ) Ç FOLLOW( A ) f
满足两条件文法做LL(1)文法中第L代表左
右扫描输入第二L表示产生左推导1代表决定分析器步
动作时前输入符号没公左子外LL(1)文法
明显性质二义含左递
3．语法树
句子树结构表示法称语法树(语法分析树语法推导树)
定文法G(VNVTPS)G句型构造关联
语法树棵树具列特征：
(1)根节点标记开始符号S
(2)节点标记V中符号
(3)棵子树根节点A直接子孙标记左右排列
次序A1A2…ARA®A1A2…AR定P中条产生式
(4)标记A节点少外子孙AVN
(5)树叶节点标记左右排列字符串ww文法G
句型w中仅含终结符号w文法G产生句子
4．LR(0)分析器
谓LR(0)分析指左右扫描底语法分析分析
步须根分析栈前已移进约出全部文法符号
前查0输入符号确定相某产生式左部符号句柄否
已分析栈顶部形成确定前应采取分析动作 (
移进某产生式进行约等)
5．语言文法
文法语言结构定义描述穷非空产生式集合
文法G定义四元组形式：
G(VNVTPS)
中：VN 非空穷集合称非终结符号集合VT 非空穷集合
称终结符号集合P产生式集合(非空)S开始符号(识符号)
里VN∩VTÆSVNVVN∪VT称文法G字母表出现
文法产生式中切符号集合
文法G描述语言L(G)表示文法G产生全部句子组成
L(G){x| SÞ*x中S文法开始符号 }
简单说文法描述语言该文法切句子集合
四简答题(4题题5分20分)
1．编译程序高级语言什区
汇编语言高级语言编写程序必须先送入计算机转换成机器
语言表示目标程序（程编译）计算机执行执行转换程
程序编译程序汇编程序指没编译汇编语言源文件编译程序转
换目标程序机器语言
编译程序工作情况三种：汇编型解释型编译型汇编型编译程序
汇编语言编写程序应关系转换成机器语言表示程序
解释型编译程序高级语言程序语句先解释成组机器语言指令
然立执行执行完取组语句解释执行继续完成程序
止解释型编译程序执行速度慢进行计算机话时
修改高级语言程序BASIC语言解释型高级语言编译型编译程序
级语言编写程序次会部翻译成机器语言表示程序程进行快
程中进行机话修改FORTRAN语言编译型高级语言
2．编译程序工作分阶段
词法分析语法分析语义分析源程序进行分析(称编译程序前端)
中间代码生成代码优化代码生成三阶段合称源程序进行综合(称
编译程序端)源程序中间表示建立起源程序等价目标程序
3．简述分析方法
谓分析法输入串开始逐步进行约直约文法
开始符号者说语法树末端开始步步约直根节点
4．简述代码优化目意义
代码优化量生成代码编译阶段程序代码进行
种等价变换保证变换前代码执行结果相前提量目
标程序运行时需时间短时占存储空间少
五综合应题(3题题10分30分)
1．证明述文法G：
S®aSbS|aS|d
二义性文法
解：
文法果存某句子棵语法分析树应称
文法二义性文法
句子aadbd两棵语法树图：
S
a
S
S
a
b
S
d
d
d
S
S
a
b
S
S
a
d
(1) (2)
知S®aSbS|aS|d定义文法二义性文法
A
S
B
b
B
S
a
b
2．文法G[S]：S®ABA®Aa|bBB®a|Sb求句型baSb全部短语直接短语句柄？
句型baSb语法树图五(2)示
解：baSb句型baSb相S短语ba句型baSb相A短语Sb句型baSb相B短语直接短语a句型baSb相B短语直接短语句柄
3．设非确定限动机NFA M({ABC}{01}d{A}{C})中：
d (A0){C} d (A1){AB} d (B1){C} d (C1){C}请画出状态转换距阵状态转换图
解：状态转换距阵：
d
0
1
A
C
AB
B
Æ
C
C
Æ
C
状态转换图1
1
0
1
1
编译原理期末试题（六）
编译原理 样题
1．____型文法称正规文法
[A] 0 [B] 1 [C] 2 [D] 3
2．____文法LL(1)
[A] 递 [B] 右递 [C] 2型 [D] 含公左子
3． 文法E→E+E|E*E|i句子i*i+i*i语法分析树总数______
[A]1 [B]3 [C]5 [D]7
4．四元式间联系通 实现
[A]时变量 [B]指示器 [C]符号表 [D]程序变量
5．心集合会产生新突
[A]二义 [B]移进移进 [C]移进约 [D]约约
6．代码优化时
[A]语法规 [B]词法规 [C]等价变换规 [D]语义规
7．表达式a(b)*c逆波兰表示
[A]ab@c* [B]ab@c* [C]ab@ [D]ab@c* （注：@单目减运算符）
8．程DISPLAY表记录
[A]程连接数 [B]程嵌套层次
[C]程返回址 [D]程入口址
二 填空题
3．文法G1G2L(G1)L(G2) （ G1G2语言相）称文法G1G2等价
4．文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i句型T+T*F+i句柄T 左素短语 T*F
5．右推导逆程称规范约 称 左约
6．规范规约中规约串句柄 算符优先分析中规约串 左素短语
7．（A∨ B）∧（C∨ ¬D∧ E） 逆波兰式ＡＢ∨ＣＤ¬Ｅ∧∨∧
8．属性文法中文法符号两种属性分称继承属性 综合属性（次序换）
9．符号表项名字栏 址分配 两栏目组成目标代码生成阶段符号表 址分配
10．程DISPLAY表容 直接外层 DISPLAY表容加
程SP址
三 穷动机M接受字母表S＝{01}满足述条件串：10直接右边构造DFA MM等价正规式
四 证明正规式(ab)*a 正规式a(ba)*等价 （构造DFA方法）
答案：
五 写文法语言：
L ＝ { 1n0m1m0n | mn≥0 }
五 文法G：S → 1S0 | A
A → 0A1 | ε
六 文法G[S]
S → aSb | P
P → bPc | bQc
Q → Qa | a
(1) 否算符优先文法？请构造算符优先关系表
(2) 文法G[S]消左递提取左公子否LL（1）文法？请证实
1求出G[S]FIRSTVT集LASTVT集：
FIERSTVT（S）{ab} LASTBVT（S）{bc}
FIERSTVT(P){b} LASTBVT（P）{c}
FIERSTVT(Q){a} LASTBVT（Q）{a}
构造优先关系表：
a
b
c
a
< >
<
>
b
< >
c
>
>
优先关系中时出现aab
2 消左递提取左公子文法：
S → aSb | P
P → bP’
P’→ Pc |Qc
Q → aQ’
Q’→ aQ’|ε
求具相左部两产生式Select集交集：
Select(S→aSb)∩Select(S→P) {a}∩First(P) {a}∩{b} Ф
Select(P’→Pc)∩Select(P’→Qc) First(P)∩First(Q){b}∩{a} Ф
Select(Q’→aQ’)∩Select(Q’→ε) {a}∩Follow(Q) {a}∩{c} Ф
修改文法LL（1）文法
七 已知文法G
（0） S′→ S
（1） S → aAd
（2） S → bAc
（3） S → aec
（4） S → bed
（5） A → e
试构造LR（1）项目集前缀图LR（1）分析表
答案：
e
c
A
d
I0
S′→· S #
S→· aAd #
S→ · bAc #
S→ ·aec #
S→ · bed #
I2：
S→a · Ad #
S→a · ec #
A→· e d
a
I1：S′→S · #
S
I3 S→b · Ac #
S→b · ed #
A→· e c
b
I6 S→bA·c#
A
I7：S→be · d #
A→e · c
I11：
S→bed · #
d
I10：
S→bAc · #
I4：S→aA· d #
I5：S→ae· c # A→e · d
e
I8：S→aAd · #
I9：S→aec · #
c
构造LR(1)分析表
：
r4
11
S10
6
r2
10
r3
9
r1
8
S11
r5
7
r5
S9
5
S8
4
6
S7
3
4
S5
2
acc
1
A
#
S3
b
e
d
c
1
S
goto
a
S2
action
0
状态
八 已知源程序：
prod0
i1
while i≤20 do
begin
prodprod+a[i]*b[i]
ii+1
end
试语法制导翻译法源程序翻译成四元式序列（设A数组a起始址B数组b起始址机器字节编址数组元素占四字节）
答案：
九 设程序段
procedure P(xyz)
begin
Yy*3
ZX+z
end
begin
a5 b2
p(a*baa)
print(a)
end
参数传递方法分（1）传值（2）传址（3）传名试问结果分什？
十 （1）传值 5 （2）传址 25 （3）传名 45
十 文法请写出关括号嵌套层数属性文法(SL引入属性h记录输出配括号数)
文法规
语 义 规
S→(T)
S→i
T→TS
T→S
答案：
十 PL0语言while语句 while 条件B DO 语句S 编译程序
请空缺处填空完成该语句编译算法：
switch (SYM) { ……
case WHILESYM
CX1CX
GetSym()
CONDITION(SymSetAdd(DOSYMFSYS)LEVTX)
CX2CX
GEN(JPC00)
if (SYMDOSYM)
GetSym()
else Error(18)
STATEMENT(FSYSLEVTX)
GEN(JMP0CX1)
CODE[CX2]ACX
break
……}
编译原理期末试题（七）
回答列问题：(30分)
1．什S属性文法？什L属性文法？间什关系？
解答：
S属性文法含综合属性属性文法 （2分）
L属性文法求产生式AàX1X2…Xn语义规中属性者综合属性者Xj继承属性该属性仅赖：
（1） 产生式Xj左边符号X1X2…Xj1属性
（2） A继承属性 （2分）
S属性文法L属性文法特例 （2分）
2．什句柄？什素短语？
句型左直接短语称该句型句柄（3分）素短语样短语少包含终结符包含更素短语（3分）
3．划分程序基块时确定基块入口语句条件什？
解答：
（1）程序第语句
（2）条件转移语句条件转移语句转移语句
（3）紧条件转移语句面语句
4．(6分)运行时DISPLAY表容什？作什？
答：DISPLAY表嵌套层次显示表进入程建立活动记录区时建立张嵌套层次显示表diaplay假定现进入程层次idiaplay表含i+1单元顶单元次存放着现行层直接外层…直外层(程序0层)等层程新活动记录起始址通DISPLAY表访问外层程变量
5．(6分)列四元式序列生成目标代码：
AB*C
DE+F
GA+D
HG*2
中H基块出口活跃变量 R0R1寄存器
答：
LD R0 B
MUL R0 C
LD R1 E
ADD R1 F
ADD R0 R1
MUL R0 2
ST R0 H
注二设S{01}正规集S倒数第二字符1字符串组成请出该字集应正规式构造识该正规集DFA(8分)
答：
构造相应正规式：(0|1)*1(0|1) (3分)
NFA (2分)
1 1
1
0
4
3
2
e e e e 1
0 0
确定化：(3分)
I
{012}
{12}
{123}
{12}
{12}
{123}
{123}
{124}
{1234}
{124}
{12}
{123}
{1234}
{124}
{1234}
0
1
4
3
2
1
0
0 1 0 0
0 1
1 1
三写文法语言L(G){ anbmambn | mn≥1}(6分)
答：文法G(S)
S ® aSb | B
B ® bBa | ba
四文法G(E) (8分)
E®T|E+T
T®F|T*F
F®(E)|i
E
T
F
(
E
)
E
+
T
F
i
T
T
*
F
1 写出句型(T*F+i)右推导画出语法树
2 写出述句型短语直接短语句柄素短语
答：
1 (4分)
EÞTÞFÞ(E) Þ(E+T) Þ(E+F)
Þ(E+i) Þ(T+i) Þ(T*F+i)
2 (4分)
短语：(T*F+i) T*F+i T*F i
直接短语：T*F i
句柄：T*F
素短语：T*F i
五设文法G(S)：(12分)
1． 构造非终结符FIRSTVTLASTVT集合
2． 构造优先关系表优先函数(12分)
答：(6分)
FIRSTVT(S){ i+)( }
FIRSTVT(A){ +)( }
FIRSTVT(B){ )( }
LASTVT(S){ i+*( }
LASTVT(A){ +*( }
LASTVT(B){ *( }
优先关系表 (3分)
i
+
(
)
*
i
>
<
<
<
+
>
>
<
<
>
(
>
>
>
)
<
<
<
*
>
>
>
优先函数 (3分)
i
+
(
)
*
f
2
6
6
1
6
g
1
4
6
6
1
六设某语言dowhile语句语法形式 (9分)
S ® do S(1) While E
语义解释：
真
假
S(1)代码
E代码
针语法分析器求构造该语句翻译模式：
(1) 写出适合语法制导翻译产生式
(2) 写出产生式应语义动作
答：(1) 适合语法制导翻译文法(3分)
G(S)
R® do
U®R S(1) While
S®U E
(2) (6分)
R® do
{ RQUADNXQ }
U®R S(1) While
{ UQUADRQUAD
BACKPATCH(SCHAIN NXQ) }
S®U E
{ BACKPATCH(ETC UQUAD)
SCHAINEFC }
答案二：
(1) S ® do M1 S(1) While M2 E
M ®ε (3分)
(2) M ®ε { MQUAD NXQ } (6分)
S ® do M1 S(1) While M2 E
{
BACKPATCH(S(1)CHAIN M2QUAD)
BACKPATCH(ETC M1QUAD)
SCHAINE FC
}
七(8分)语句
if (A
翻译成四元式(8分)
答：
100 (j< A X 102)
101 (j 109)
102 (j> B 0 104)
103 (j 109)
104 (j> C 0 106)
105 (j 109)
106 (+ C D T1)
107 ( T1 C)
108 (j 104)
109
(控制结构3分5分)
八(10分) 设基块：
T1S+R
T2 3
T3 12T2
T4SR
AT1T4
T5S+R
BT5
T6T5*T3
BT6
(1)画出DAG图
(2)设AB出基块活跃变量请出优化四元式序列
T1T5 B
3
T2
4
S
R
+
*
_
T3
T4
A
T6B
n4
n5
n1
n2
n3
n6
n8
n7
答：(1) DAG右图：(6分)
(2) 四元式序列：(4分)
T1S+R
T4SR
AT1T4
BT1*4
九(9分) 设已构造出文法G(S)：
(1) S ® BB
(2) B ® aB
(3) B® b
LR分析表
ACTION
GOTO
状态
a
b
#
S
B
0
s3
s4
1
2
1
acc
2
s6
s7
5
3
s3
s4
8
4
r3
r3
5
r1
6
s6
s7
9
7
r3
8
r2
r2
9
r2
假定输入串abab请出LR分析程(步骤出状态符号输入串变化程)
答：
步骤 状态 符号 输入串
0 0 # abab#
1 03 #a bab#
2 034 #ab ab#
3 038 #aB ab#
4 02 #B ab#
5 026 #Ba b#
6 0267 #Bab #
7 0269 #BaB #
8 025 #BB #
9 01 #S # acc
编译原理期末试题（八）
1．（10分）处* *间串构成注解注解中间没*画出接受种注解DFA状态转换图
2．语言L ＝ {ambn | 0 £ m £ 2n}（a数超b数两倍）
写LR（1）文法准超6产生式（超6产生式分写文法LR（1）文法5分）
3．（10分）构造面文法LL（1）分析表
D ® TL
T ® int | real
L ® id R
R ® id R | e
4．（15分）面文法
S ® ( L) | a L ® L S | S
· 出语法制导定义输出配括号数
· 出翻译方案输出a嵌套深度
句子(a (a a) )第题输出2第二题输出1 2 2
5．（10分）Pascal语言for语句含义见教材第222页题713请该语句设计种合理中间代码结构第215页图717方式者第219页图719方式写出设计需写产生中间代码语法制导定义
6．（5分）C语言程序：
func(i1i2i3)
long i1i2i3
{
long j1j2j3
printf(Addresses of i1i2i3 ooo\n&i1&i2&i3)
printf(Addresses of j1j2j3 ooo\n&j1&j2&j3)
}
main()
{
long i1i2i3
func(i1i2i3)
}
该程序某种机器Linux运行结果：
Addresses of i1i2i3 277777754602777777546427777775470
Addresses of j1j2j3 277777754442777777544027777775434
面结果出func 函数3形式参数址次升高3局部变量址次降低试说明什会区
7．（15分）C语言程序某种机器linux操作系统编译结果根生成汇编程序解释程序中四变量作域生存期置初值方式等方面区
static long aa 10
short bb 20
func()
{
static long cc 30
short dd 40
}
file staticc
version 0101
gcc2_compiled
data
align 4
type aa@object
size aa4
aa
long 10
globl bb
align 2
type bb@object
size bb2
bb
value 20
align 4
type cc2@object
size cc24
cc2
long 30
text
align 4
globl func
type func@function
func
pushl ebp
movl espebp
subl 4esp
movw 402(ebp)
L1
leave
ret
Lfe1
size funcLfe1func
ident GCC (GNU) egcs29166 19990314Linux (egcs112 release)
8．（10分）C语言种类型语言强类型语言编译时类型检查保证接受程序没运行时类型错误例编译时类型检查般保证运行时没数组越界请举样例子说明C语言强类型语言
9．（10分）果A机器C语言编译器CCA源码SA（C语言写成）利通量少工作B机器C语言编译器CCB
10．（5分）表达式(lx(lyz(x + y) + z) 3) 4 5(lx(lyz(x + y) + z) 3 5) 4样结果抽象机FAM表达式应目标代码执行效率高？什？
参考答案
1．
1
2
4
start
5
2
others
others
*
*
*
2．LR（1）文法 LR（1）文法 二义文法
S ® AB | aABb S ® AB S ® AASb | e
A ® aaAb | e A ® aaAb | ab | e A ® a | e
B ® Bb | e B ® Bb | e
3． int real id
D D®TL D®TL
T T®int T®real
L L®id R
R R ® id R R ® e
4． S¢ ® S print(Snum)
S ® (L) Snum Lnum +1
S ® a Snum 0
L ® L1S Lnum L1num + Snum
L ® S Lnum Snum
S¢ ® {Sdepth 0} S
S ® {Ldepth Sdepth +1} (L)
S ® a {print(Sdepth)}
L ® {L1depth Ldepth} L1 {Sdepth Ldepth} S
L ® { Sdepth Ldepth} S
5． t1 initial
t2 final
if t1 > t2 goto L1
v t1
L2 stmt
if v t2 goto L1
v v + 1
goto L2
L1
6．实参表达式反序进入活动记录局部变量序活动记录中分配
7．aa静态外部变量bb外部变量分配静态数区（data伪指令开始）bb伪指令globl指明全局解决文件中bb外部引aa文件引cc静态局部变量aabb样生存期整程序分配静态数区cc源程序中作域函数func体目标文件中作域少已整文件避免源文件中外部变量函数静态局部变量名字突进行改名成cc2cc全局cc2前面没伪指令globldd动变量作域函数func体生存期该函数激活期间分配栈区置初值运行时赋值实现
8．例联合体类型检查般编译时完成然面例子静态判断类型错误
union U { int u1 int *u2} u
int *p
uu1 10
p uu2
*p 0
9． · 修改源码SA 代码生成部分产生B机器代码称结果程序SB
· SB提交CCA进行编译执行程序
· SB提交述执行程序进行编译需编译器CCB
10．第表达式执行lyz(x + y) + z) 3时出现参数数足情况FUNVAL值进入栈顶然发现参数数足做成FANVAL情况第二表达式执行(lyz(x + y) + z) 3 5会出现参数数足情况第二表达式执行效率第表达式高
编译原理期末题
1 注设文法G（S）试消左递
G（S）：S—>Ac|c
A—>Bb|b
B—>Sa|a
解：S→abcS′|bcS′|cS′ S′→abcS′|
2 试构造面G（S）等价左递文法
G（S）：S—>Sa|Nb|c
N—>Sd|Ne|f
解：S→fN′bS′|cS′ S′→aS′|dN′bS′| N′→eN′|
3 设文法G（S）：
S—>aBc|bAB
A—>aAb|b
B—>b|ε
①求产生式FIRST集FOLLOW(A)FOLLOW(B)产生式SELECT集
②构造LL(1)分析表分析符号串baabbb否
解：（1）FIRST(aBc){a} FIRST(bAB){b} FIRST(aAb){a} A→b FIRST(A→b){b} B→b FIRST(b) {b} FIRST(ε){ε}
FOLLOW(A){b #} FOOLOW(B){c #}
SELECT(S→aBc){a} SELECT(S→bAB) {b} SELECT(A→aAb){a} SELECT(A→b){b} SELECT(B→b){b} SELECT(B→){c #}
LL(1)分析表表A4示
表A4 LL(1)分析表
输入
VN
输入符号
a
b
c
#
S
S→aBc
S→bAB
A
A→aAb
A→b
B
B→b
B→
B→
（2）分析符号串baabbb成功baabbb该文法句子图A16示
图A16 识串baabbb程
4 列文法G(S)：
S—>D(R) R—>RP|P
P—>S|I D—>i
①计算文法G中非终结符FIRSTVT集LASTVT集
②构造文法G算符优先关系矩阵
解：（1）FIRSTVT(S){( i}FIRSTVT(D) {i}FIRSTVT(R){ ( i}FIRSTVT(P){i (}LASTVT
(S){)}LASTVT(D){i}LASTVT(R) { ) i}LASTVT(P){i )}
（2）算符优先矩阵表A5示
表A5 优先矩阵
(
)
i
#
(
)
i
#
5 已知文法G(S)：
S—>a|(T)
T—>TS|S
①出句子((aa)a)左推导画出语法树②出句型(Ta(T))短语直接短语素短语左素短语句柄活前缀
解：（1）左推导：S(T)(TS)(SS) (aS)(a(T))(a(TS))(a(SS))(a(a S))(a(aa))
语法树：图A16示
图A16 (a(aa))语法树
（2）句型(T a (T))短语直接短语素短语左素短语句柄活前缀语法树（图A17）
短语：a || Ta || (T) || T a (T) || (T a (T))
直接短语：a || (T)
素短语：a || (T)
左素短语：a
句柄：a
活前缀： || ( || (T || (T || (T a
图A17 (Ta(T))语法树
6 设文法Ｇ（Ｓ）：
Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ
Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε
求①ＬＲ（０）项目集族②构造识文法Ｇ（Ｅ）ＤＦＡ
③构造文法Ｇ（Ｅ）SLR（１）分析表
④分析句子ａ１１００ｂ识程
解：（1）（2）LR(0)项目集族识活前缀DFA图A19示
图A19 LR(0)
项目集族DFA
（3）（4）略
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
