编译原理switch生成四元式
㈠ 编译原理问题,高手进。
回答下列问题:(30分)
(6分)对于下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若参数传递的方法分别为(1)传值、(2)传地址,(3)传名,请写出程序执行的输出结果。
答: (1) 3 (2) 16 (3) 16 (每个值2分)
(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合,并判断该文法是否是LL(1)的,请说明理由。
G(M):
M → TB
T → Ba |
B → Db | eT |
D → d |
解答:
计算文法的FIRST和FOLLOW集合:(4分)
FIRST(M) = { a,b,e,d, } FIRST(T) = { a,b,e,d, }
FIRST(B) = {b,e,d, } FIRST(D) = {d,}
FOLLOW (M) = {#} FOLLOW (T) = { a,b,e,d,#}
FOLLOW (B) = {a,# } FOLLOW (D) = { b}
检查文法的所有产生式,我们可以得到:
1. 该文法不含左递归,
2. 该文法中每一个非终结符M,T,B,D的各个产生式的候选首符集两两不相交。
3. 该文法的非终结符T、B和D,它们都有候选式,而且
FIRST(T)∩FOLLOW(T)={ a,b,e,d }≠
所以该文法不是LL(1)文法。(2分)
(4分)考虑下面的属性文法
产 生 式 语 义 规 则
S→ABC
A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
画出字符串abc的语法树;
对于该语法树,假设S.u的初始值为5,属性计算完成后,S.v的值为多少。
答:(1) (2分)
(2) S.v的值为18 (2分)
(4分)运行时的DISPLAY表的内容是什么?它的作用是什么?
答:DISPLAY表是嵌套层次显示表。每当进入一个过程后,在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i,则它的diaplay表含有i+1个单元,自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序,0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。
(5分)对下列四元式序列生成目标代码:
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中,H在基本块出口之后是活跃变量, R0和R1是可用寄存器。
答: 目标代码序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H
(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
答:
逆波兰式:(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象语法树:(2分)
(8分)构造一个DFA,它接受={a,b}上所有包含ab的字符串。
答:
(2分)构造相应的正规式:(a|b)*ab(a|b)*
(3分)
a a
a b
b b
(3分)确定化:
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a
a b b
b
最小化:
{0,1,2} {3,4,5}
{0, 2},1, {3,4,5}
(6分)写一个文法使其语言为L(G)={anbncm| m,n≥1,n为奇数,m为偶数}。
答:
文法G(S):
(8分)对于文法G(S):
1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语,直接短语和句柄。
答:
1. (4分)
2. (4分)
短语: Ma), (Ma), b(Ma)b
直接短语: Ma)
句柄: Ma)
(12分)对文法G(S):
S → a | ^ | (T)
T → T,S | S
(1) 构造各非终结符的FIRSTVT和LASTVT集合;
(2) 构造算符优先表;
(3) 是算符优先文法吗?
(4) 构造优先函数。
答:
(1) (4分)
(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >
(3) 是算符优先文法,因为任何两个终结符之间至多只有一种优先关系。 (1分)
(4) 优先函数(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3
(8分)设某语言的do-while语句的语法形式为
S do S(1) While E
其语义解释为:
针对自下而上的语法分析器,按如下要求构造该语句的翻译模式,将该语句翻译成四元式:
(1) 写出适合语法制导翻译的产生式;
(2) 写出每个产生式对应的语义动作。
答:(1). 适合语法制导翻译的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }
UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }
SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }
答案二:
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}
(10分)将语句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻译成四元式。
答:
100 (j>, C, 0, 102)
101 (j, -, -, 112)
102 (jnz, A, -, 106)
103 (j, -, -, 104)
104 (j=, B, 0, 106)
105 (j, -, -, 109)
106 (+, C, D, T1)
107 (:=, T1, -, C)
108 (j, -, -, 100)
109 (*, C, D, T2)
110 (:=, T2, -, C)
111 (j, -, -, 100)
112
(10分)设有基本块如下:
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
画出DAG图;
设L,M,N 是出基本块后的活跃变量,请给出优化后的四元式序列。
答:
1. (6分)
L
*
T2,M T4 T2,N
* - +
T1 T3
3 A B 12 C D
2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D
(8分)文法G(S)及其LR分析表如下,请给出串baba#的分析过程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答:
步骤 状态 符号 输入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈,估计认识!!
㈡ 编译原理 四元式
四元式是一种比较普遍采用的中间代码形式。
代码段的四元式表达式:
101 T:=0 (表达式为假的出口)
103 T:=1 (表达式为真的出口)
因为用户的表达式只有一个A<B,因此A<B的真假出口就是表达式的真假出口,所以
100: if a<b goto 103 (a<b为真,跳到真出口103)
101: T:=0(否则,进入假出口)
102: goto 104 (要跳过真出口,否则T的值不就又进入真出口了,为真)
103: T:=1
104:(程序继续执行)
(2)编译原理switch生成四元式扩展阅读:
四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理,因此,在目前许多编译程序中得到了广泛的应用。
四元式实际上是一种“三地址语句”的等价表示。它的一般形式为:
(op,arg1,arg2,result)
其中, op为一个二元 (也可是一元或零元)运算符;arg1,arg2分别为它的两个运算 (或操作)对象,它们可以是变量、常数或系统定义的临时变量名;运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式:
result ∶= arg1 op arg2
需要指出的是,每个四元式只能有一个运算符,所以,一个复杂的表达式须由多个四元式构成的序列来表示。例如,表达式A+B*C可写为序列
T1∶=B*C
T2∶=A+T1
其中,T1,T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时,arg2甚至arg1应缺省,即result∶=op arg1或 op result ;对应的一般形式为:
(op,arg1,,result)
或
(op,,,result)
㈢ 编译原理中 文法 文法G定义为四元组(Vn ,Vt,P,S)这4个是什么意思 另外 终结符和非终结符是什么意思
文法G是一个四元式(Vt,Vn,S,P)
其中Vt是一个非空有限集,它的每个元素称为终结符号
Vn是一个非空有限集,它的每个元素称为非终结符号(Vt和Vn的交集为空)
S是一个非终结符号,称为开始符号
P是一个产生式集合(有限),每个产生式的形式是P-->a
开始S必须在某个产生式的左部出现一次
终结符指组成语言的基本符号(如基本字、标识符、常数、算符、界符)
非终结符号(也称语法变量)表示一定符号串的集合。
你看到小写字母一般是终结符,大写字母肯定是非终结符
不明白可以联系。
㈣ 编译原理课设,将c语言程序翻译成四元式,求大神给思路
财富算神马?10000分能值一块钱么?你喊给100RMB,看看有多少人会给你回
㈤ 编译原理四元式
四元式的一般形式为(op, arg1, arg2, result),其中:op为一个二元(也可以是零元或一元)运算符。arg1和arg2为两个运算对象,可以是变量、常数或者系统定义的临时变量名。result为运算结果。
第一步:T1=a*b,
第二步:T2=c*d,
第三步:T3=T2/e,
第四步:T4=T1-T3,
第五步:f=T4.
㈥ 编译原理用C++生成四元式的程序,如果把生成四元式当成一个类来写,那这个类应该有哪些函数
四元式的四个组成成分是:算符op,第一和第二运算对象ARG1和ARG@及运算结果RESULT。
你所有的事情也都是围绕这四个东东来做呀,间接地就是生成“三地址指令”或是转换成“语句”(例如 if B rop C goto L)之类的。
㈦ 跪求 编译原理实验 中间代码生成(生成四元式)及目标代码生成(汇编语言) 要求可以处理if 及while循环
利用ADC0809采用中断式设计一个温度测控系统,在LED数码显示器上显示温度值,并对温度进行测试和控制
㈧ 编译原理 把下面程序段翻译成四元式序列
四元式类似于三地址指令:波兰式。
0:(=,M,—,A); 简单赋值表达式翻译:a = m;
1:(=,N,—,B); B=N;
2:(<,A,B,4) ; 控制语句翻译 :IF A<B GOTO 4;
3:(jump,—,—,6); 直接转移语句;JUMP TO 6;
4:(=,N,—,T); T=N;
5:(jump,—,—,7) jump to 7;
6:(=,M,—,T) T=M;
7:(=,T,—,C). C=T;
㈨ 编译原理写出语句 if(a<b)then x:=y z;else x:=y-z ;的四元式表示
(100) if a<b goto (102)
(101) goto (105)
(102) t:=y+z //若不是+,需要进行相应修改
(103) x:=t
(104) goto (107)
(105) t:=y-z
(106) x:=t
(107)…
注: 原题if(a<b)then x:=y z,y和z之间的运算符没给出,四元式中写成了+,若是其他运算符进行相应修改即可