编译原理表达式

❶ 编译原理三元式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))

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

三元式
(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)

❸ 编译原理正则表达式化简

你好，语言L={a}{a,b}∗({ϵ}∪({.,_}{a,b}{a,b}∗))L={a}{a,b}
∗
({ϵ}∪({.,_}{a,b}{a,b}
∗
))
这个语言是指，由a开头，后接任意长度的a、b串，然后再接空串（代表结束）。或者是接以.或_开头的，后接长度大于等于1的a、b串。

正则表达式（Regular Expression, RE）是一种用来描述正则语言的更紧凑的表示方法。

❹ 【编译原理】构造下述文法G[S]的确定有限自动机，并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a

通过联立方程组求正规表达式：
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根据方程X=Xt+r 必有X=t*r解的论断，可得A=(a+ab)*(b+a)，进而可求得：
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正规表达式为： (a|ab)*(b|a)a。
注意：以上求解的过程中“|”和“+”是等价的，都表示“或”的意思，它们的相互替换是为了描述的方便。

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

#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;
}

❻ 编译原理，正则表达式的低级基础问题

1、正则表达式：0(0|1)*1
2、由于不方便画图，最简DFA用状态表表示如下：
（1）开始状态S------输入0------->状态A
（2）状态A-------输入0-------->状态A
（3）状态A-------输入1-------->状态B（可接受状态）
（4）状态B-------输入0-------->状态A
（5）状态B-------输入1-------->状态B（可接受状态）

❼ 编译原理四元式

四元式的一般形式为(op, arg1, arg2, result)，其中：op为一个二元（也可以是零元或一元）运算符。arg1和arg2为两个运算对象，可以是变量、常数或者系统定义的临时变量名。result为运算结果。
第一步:T1=a*b，
第二步:T2=c*d，
第三步:T3=T2/e，
第四步:T4=T1-T3，
第五步：f=T4.