编译原理翻译成三元式例题

Ⅰ 《编译原理》的一道题 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列

逆波兰式可能是这样,上学期刚考完一个假期有点忘了（abc）（ab）d+*/+-
三元式已经忘得一干二净了

Ⅱ 编译原理问题，求解答

好，我来帮你理解一下，先看基本知识：
四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG@及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a∶=b*c+b*d的四元式表示如下：
（1）（*，b，c，t1）
（2）（*，b，d，t2）
（3）（+， t1， t2， t3）
（4）（∶=，t3， －， a）
四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。
有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成：
（1）t1∶=b*c
（2）t2∶=b*d
（3）t3∶=t1+t2
（4）a∶=t3
把（jump，－，－，L）写成goto L
把（jrop，B，C，L）写成if B rop C goto L
好，下面分析一下a<b
这是一个表达式，它的结果要么是0，要么是1，因为没有指定这个表达式存放在哪，所以需要一个临时变量来存放它的，在你的问题中，就是T。很显然T有2个值：0或者1
因此，有
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:（程序继续执行）

Ⅲ 有关编译原理的几个问题

最左推到就是从最左边的非终结符开始替换，一个一个替换，直到替换为题目要求的。预测分析表什么的太烦了，不高兴写。你按着书上例题步骤一步一步写就可以了。给你写个第五题。

Ⅳ 编译原理 写出表达式 三元序列

三元式
(1)（a，b，+）
(2)(a,b,-)
(3)((1),(2),/)
(4)(b,c,*)
(5)(a,(4),+)
(6)((3),(5),-)
四元式
（a，b，+,x1）
(a,b,-,x2)
(x1,x2,/,x3)
(b,c,*,x4)
(a,x4,+,x5)
(x3,x5,-,x6)

Ⅳ 编译原理 对于输入的任一算术表达式

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>

#define DEBUG

#define NULL 0
#define ERROR -1
#define STACKSIZE 20

/* 定义字符类型栈 */
typedef struct{
char stackname[20];
char *base;
char *top;
} Stack;

/* ----------------- 全局变量--------------- */
Stack OPTR, OPND; /* 定义前个运算符栈，后个操作数栈 */
char expr[255] = ""; /* 存放表达式串 */
char *ptr = expr;
int step = 0; /* 计算的步次 */

int InitStack(Stack *s, char *name)
{
s->base=(char *)malloc(STACKSIZE*sizeof(char));
if(!s->base) exit (ERROR);
strcpy(s->stackname, name);
s->top=s->base;
return 1;
}

int In(char ch)
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}

void OutputStatus(void)
{
char *s;

/* step */
printf("\n%-8d", ++step);

/* OPTR */
for(s = OPTR.base; s < OPTR.top; s++)
printf("%c", *s);
printf("\t");

/* OPND */
for(s = OPND.base; s < OPND.top; s++)
printf("%d ", *s);

/* input char */
printf("\t\t%c", *ptr);
}

int Push(Stack *s,char ch)
{
#ifdef DEBUG
char *name = s->stackname;
OutputStatus();
if(strcmp(name, "OPND") == 0)
printf("\tPUSH(%s, %d)", name, ch);
else
printf("\tPUSH(%s, %c)", name, ch);
#endif
*s->top=ch;
s->top++;
return 0;
}

char Pop(Stack *s)
{
char p;
#ifdef DEBUG
OutputStatus();
printf("\tPOP(%s)", s->stackname);
#endif
s->top--;
p=*s->top;
return (p);
}

char GetTop(Stack s)
{
char p=*(s.top-1);
return (p);
}

/* 判断运算符优先权，返回优行权高的 */
char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={ '>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};

switch(c1)
{
/* i为下面array的横标 */
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}
switch(c2)
{
/* j为下面array的纵标 */
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); /* 返回运算符 */
}

/*操作函数 */
int Operate(int a,char op,int b)
{
#ifdef DEBUG
OutputStatus();
printf("\tOPERATE(%d, %c, %d)", a, op, b);
#endif

switch(op)
{
case '+' : return (a+b);
case '-' : return (a-b);
case '*' : return (a*b);
case '/' : return (a/b);
}
return 0;
}

int EvalExpr(void)
{
char c,theta,x,m,ch;
int a,b;

c = *ptr++;
while(c!='#'||GetTop(OPTR)!='#')
if(!In(c))
{
m=atoi(&c);
Push(&OPND,m);
c = *ptr++;
}
else
switch(Precede(GetTop(OPTR),c))
{
case '<':
Push(&OPTR,c);
c = *ptr++;
break;
case '=':
x=Pop(&OPTR);
c = *ptr++;
break;
case '>':
theta=Pop(&OPTR);
b=Pop(&OPND); a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}

return GetTop(OPND);
}

int main(void)
{
/*
printf("Input the expression(end with \"#\" sign):");
do{
gets(expr);
}while(!*expr); */

//strcpy(expr, "2*(2+3)#");
char *pc;
printf("Input the expression(end with \"#\" sign):");
gets(expr);
pc=expr;
if(expr[0]=='\0')
{
printf("Please input a valid expression!\n");
printf("Input the expression again(end with \"#\" sign):");
gets(expr);
}
else
{
while(*pc!='\0')
pc++;
pc--;
if(*pc!='#')
{
printf("Please asure the expression end with \"#\" sign!\n");
printf("Input the expression again(end with \"#\" sign):");
gets(expr);
}
}

InitStack(&OPTR, "OPTR"); /* 初始化运算符栈 */
Push(&OPTR,'#'); /* 将#压入运算符栈 */
InitStack(&OPND, "OPND"); /* 初始化操作数栈 */

printf("\n\nresult:%d\n", EvalExpr());
system("pause");

return 0;
}

Ⅵ 一些关于编译原理的题目（选择，判断）

2年前还会做，现在都忘了

Ⅶ 请将表达式a *(b+c) - d * (b+c) 后缀式 三元式 间接三元式 四元式.

B 这个这样分析 ((a*(b+c))-d) => (a*(b+c)),d,- => a,(b+c),*,d,- => a,b,c,+,*,d,-

Ⅷ 编译原理三元式a:=0怎么样表示呢

一.(15分)有表达式如下:A+B*(C-D)**N (**为幂乘) (1)给出该表达式的逆波兰式表示(后缀式); (2)给出上述表达式的四元式和三元式序列. 一起考研社区真情奉献 二.(15分)有C程序如下: main() { printf("%d,%d,%d\n",10); } (1)试着写出上述printf语句输出的结果; (2)从运行环境和printf的实现分析为什么会有这样的输出结果. www.17ky.cn独家资料 三.(5分)构造一个DFA(确定的有限自动机),使之接受含偶数个"1"的0,1串集. www.17ky.cn会员奉献 四.(5分)有文法G,其产生式如下: S->S(S), S->ε /*空产生式*/ 试写出一个语法制导定义,它输出配对的括号个数. www.17ky.cn独家提供 五.(10分)已知某语言L={a^(m)b^(n)|n>m>=0}.试写出产生该语言的两个文法G1和 G2,其中G1是LR(1)文法,G2是非LR(1)和非二义性文法. 更多考研真题，请光临www.17ky.cn 六.填空(每空一分,共20分) 1.现代操作系统的两个最基本的特征是___和___. 2.进程控制块的初始化工作包括___,___和___. 3.在操作系统中引入线程概念的主要目的是___. 4.unix系统v中,系统向用户提供的用于创建新进程的系统调用是___;用于建立无名 管道的系统调用是___;用于创建有名管道的系统调用是___. 5.unix系统v中,引起进程调度的原因有___,___,___和___等. 6.在分区分配算法中,首次适应算法倾向于优先利用内存中___部分的空闲分区,从 而保留了___部分的大空闲区. 7.进行设备分配时所需的数据表格主要有___,___,___和___等. 8.利用符号链实现文件共享时,对文件主删除了共享文件后造成的指针悬空问题,解 决的方法是___. 更多考研真题，请光临www.17ky.cn 七.(8分)在消息传递通信方式下, A.发送进程和接收进程在通信过程中可以采用那三种同步方式? B.试以下面给出的发送进程和接收进程(将接收到的数据存入S)为例,说明当接收进 程执行到标号为L2的语句时,采用这三种同步方式,X的值可能各是多少? 一起考研社区真情奉献 发送进程P: 接收进程Q: M=10; L1: send M to Q; L1: receive S from P; L2: M=20; L2: X:=S+1; goto L1; 更多考研真题，请光临www.17ky.cn 八.(8分)一系统具有150个存储单元,在T0时刻按下表所示分配给3个进程: 进程Maximum demand Current allocation P1 70 25 P2 60 40 P3 60 45 对下列请求应用银行家算法分析判定是否是安全的: A.第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元. B.第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元. 如果是安全的请给出一个可能的进程安全执行序列.如果是不安全的,请说明原因. 更多考研真题，请光临www.17ky.cn 九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号 是十进制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为 1024字节. A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程. B.下列虚地址对应与什么物理地址: (1)5499; (2) 2221; 虚页号 状态位 访问位 修改位 物理块号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 --- 3 1 0 0 2 4 0 0 0 --- 5 1 0 1 0 www.17ky.cn独家提供 注释:访问位---当某页被访问时,其访问位被置为1. www.17ky.cn考研人的成功俱乐部 编译原理与操作系统 参考答案 一. (1)后缀式:ABCD-*+ECD-N**/+ (2) 四元式 三元式 (1)( - , C , D , t1) (1)( - , C , D ) (2)( * , B , t1, t2) (2)( * , B ,(1)) (3)( +, A , t2, t3) (3)( +, A ,(2)) (4)( - , C , D, t4) (4)( - , C , D ) (5)(**, t4, N , t5) (5)(**, (4), N) (6)( / , E , t5, t6) (6)( / ,E ,(5)) (7)( +, t3, t6, t7) (7)( +,(3),(6))

Ⅸ 编译原理问题，高手进。

回答下列问题：(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
哈哈，估计认识！！

Ⅹ 编译原理 题目,谁会的,帮忙看看,头都大了!

1D 2C 3B 4D 5 A 6D 7D 8B 9C 10 B
11C 12D 13 C 14A 15C 16C 17C 18B 19B 20C
21A 22B