标号区编译原理

⑴ 编译原理全部的名词解释

书上有别那么懒!.
编译过程的六个阶段：词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成
解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序.解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句.
编译程序：就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序).
解释程序和编译程序的根本区别：是否生成目标代码
句子的二义性（这里的二义性是指语法结构上的.）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导),或者存在两棵不同的语法树,则称这个句子是二义性的.
文法的二义性:一个文法如果包含二义性的句子,则这个文法是二义文法,否则是无二义文法.
LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)
第1个L：从左到右扫描输入串 第2个L：生成的是最左推导
1 ：向右看1个输入符号便可决定选择哪个产生式
某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归
文法符号的属性:单词的含义,即与文法符号相关的一些信息.如,类型、值、存储地址等.
一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G：上下文无关文法.
V：属性的有穷集.每个属性与文法的一个终结符或非终结符相连.属性与变量一样,可以进行计算和传递.
F：关于属性的断言或谓词(一组属性的计算规则)的有穷集.断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.
综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属
继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性.
(1)非终结符既可有综合属性也可有继承属性,但文法开始符号没有继承属性.
(2) 终结符只有综合属性,没有继承属性,它们由词法程序提供.
在计算时： 综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递.
语法制导翻译：是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作.
语法制导翻译实现：对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算.
中间代码（中间语言）
1、是复杂性介于源程序语言和机器语言的一种表示形式.
2、一般,快速编译程序直接生成目标代码.
3、为了使编译程序结构在逻辑上更为简单明确,常采用中间代码,这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理,并且可以在中间代码一级进行优化工作,使得代码优化比较容易实现.
何谓中间代码：源程序的一种内部表示,不依赖目标机的结构,易于代码的机械生成.
为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言.
(2)便于移植,便于修改,便于进行与机器无关的优化.
中间代码的几种形式：逆波兰记号 ,三元式和树形表示 ,四元式
符号表的一般形式：一张符号表的的组成包括两项,即名字栏和信息栏.
信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏.主栏的内容称为关键字（key word）.
符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性.(3)作为目标代码生成阶段地址分配的依据
符号的主要属性及作用：
1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）
4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）
存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式.
静态存储分配
1、基本策略
在编译时就安排好目标程序运行时的全部数据空间,并能确定每个数据项的单元地址.
2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）
3、静态存储分配的要求：不允许递归调用,不含有可变数组.
FORTRAN程序是段结构,不允许递归,数据名大小、性质固定. 是典型的静态分配
动态存储分配
1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间,那么,就需要采用动态存储管理技术.
2、两种动态存储分配方式：栈式,堆式
栈式动态存储分配
分配策略：将整个程序的数据空间设计为一个栈.
【例】在具有递归结构的语言程序中,每当调用一个过程时,它所需的数据空间就分配在栈顶,每当过程工作结束时就释放这部分空间.
过程所需的数据空间包括两部分
一部分是生存期在本过程这次活动中的数据对象.如局部变量、参数单元、临时变量等；
另一部分则是用以管理过程活动的记录信息(连接数据).
活动记录（AR）
一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区 (块)叫做一个活动记录.
构成
1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；
5、控制链；6、实参；7、返回地址
什么是代码优化
所谓优化,就是对代码进行等价变换,使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加快或占用存储空间减少.
优化原则：等价原则：经过优化后不应改变程序运行的结果.
有效原则：使优化后所产生的目标代码运行时间较短,占用的存储空间较小.
合算原则：以尽可能低的代价取得较好的优化效果.
常见的优化技术
(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (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
哈哈，估计认识！！

⑶ 编译原理课程设计－词法分析器设计（C语言）

#include"stdio.h"/*定义I/O库所用的某些宏和变量*/

#include"string.h"/*定义字符串库函数*/

#include"conio.h"/*提供有关屏幕窗口操作函数*/

#include"ctype.h"/*分类函数*/

charprog[80]={''},

token[8];/*存放构成单词符号的字符串*/

charch;

intsyn,/*存放单词字符的种别码*/

n,

sum,/*存放整数型单词*/

m,p;/*p是缓冲区prog的指针，m是token的指针*/

char*rwtab[6]={"begin","if","then","while","do","end"};

voidscaner(){

m=0;

sum=0;

for(n=0;n<8;n++)

token[n]='';

ch=prog[p++];

while(ch=='')

ch=prog[p++];

if(isalpha(ch))/*ch为字母字符*/{

while(isalpha(ch)||isdigit(ch))/*ch为字母字符或者数字字符*/{

token[m++]=ch;

ch=prog[p++];}

token[m++]='';

ch=prog[p--];

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)/*字符串的比较*/{

syn=n+1;

break;}}

else

if(isdigit(ch))/*ch是数字字符*/{

while(isdigit(ch))/*ch是数字字符*/{

sum=sum*10+ch-'0';

ch=prog[p++];}

ch=prog[p--];

syn=11;}

else

switch(ch){

case'<':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='>'){

syn=21;

token[m++]=ch;}

elseif(ch=='='){

syn=22;

token[m++]=ch;}

else{

syn=20;

ch=prog[p--];}

break;

case'>':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=24;

token[m++]=ch;}

else{

syn=23;

ch=prog[p--];}

break;

case':':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=18;

token[m++]=ch;}

else{

syn=17;

ch=prog[p--];}

break;

case'+':syn=13;token[0]=ch;break;

case'-':syn=14;token[0]=ch;break;

case'*':syn=15;token[0]=ch;break;

case'/':syn=16;token[0]=ch;break;

case'=':syn=25;token[0]=ch;break;

case';':syn=26;token[0]=ch;break;

case'(':syn=27;token[0]=ch;break;

case')':syn=28;token[0]=ch;break;

case'#':syn=0;token[0]=ch;break;

default:syn=-1;}}

main()

{

printf(" Thesignificanceofthefigures: "

"1.figures1to6saidKeyword "

"2. "

"3.figures13to28saidOperators ");

p=0;

printf(" pleaseinputstring: ");

do{

ch=getchar();

prog[p++]=ch;

}while(ch!='#');

p=0;

do{

scaner();

switch(syn){

case11:printf("(%d,%d) ",syn,sum);break;

case-1:printf(" ERROR; ");break;

default:printf("(%d,%s) ",syn,token);

}

}while(syn!=0);

getch();

}

程序测试结果

对源程序beginx:=9:ifx>9thenx:=2*x+1/3;end#的源文件，经过词法分析后输出如下图5-1所示：

具体的你在修改修改吧

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

⑸ 编译原理，子集法将NFA确定为DFA，求问，表格中的部分都是怎么来的

我也在看这个。
先以S开始，经过任意个ε得到的结点就是第一个I，这道题就是{X，1,2}，
然后将{X，1,2}中的每一个字符经过a（中间可以有ε）后得到的结点加起来，X的Ia={1,2}，
1的Ia={1,2}，2的Ia是空集，所以这一行的Ia={1,2}。
后面的Ib也是一样，只不过是经过b后得到的结点的集合。
然后分别将前面的Ia和Ib作为I计算新的Ia和Ib。
再将这些集合依次标号，这道题是{X，1,2}为X，{1,2}为1，{1,2,3}为2，{1,2，Y}为3，根据上面那个表就可以把图画出来了。

⑹ 【编译原理】第二章：语言和文法

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：

产生式

可以简写为：

如上例中，

可以简写为：

给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。

如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。

推导的反过程称为 归约 。

如果 ，则称 是 的一个 句型（sentential form ）。

由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：

例
文法

表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。
如上例表示为：

中必须包含一个 非终结符 。

产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。

上下文有关文法不包含空产生式（ ）。

产生式的一般形式：
即产生式左边都是非终结符。

右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：

正则文法能描述程序设计语言中的多数单词。

正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。

根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。

直接短语一定是某产生式的右部，但反之不一定。

如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。

二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。

⑺ 给力！2011年新年散分啦。高分求助编译原理高手帮忙做几道模拟题

三、（ 8 分）化简文法 G[S] ：
S → ASe | BCaD | aD | AC
A → Cb | DBS
C → bC | d
B → Ac
D → Ad
化简后： S → ASe|AC A → Cb C → bC | d
四、（ 12 分） 设 L í {a,b,c}* 是满足下述条件的符号串构成的语言：
(1)若出现 a ，则其后至少紧跟两个 c ；
(2)若出现 b ，其后至少紧跟一个 c 。
试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。
答：DFA 如图所示。相应的正规式为 (c|acc|bc)* 。

五、（ 12 分） 已给文法 G[S] ： S → SaP | Sf | P P → qbP | q
将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。
答：改造后的文法： S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e
各候选式的 FIRST 集，各非终结符的 FOLLOW 集为
产生式 FIRST 集 FOLLOW 集
S → PS' {q} {#}
S' → aPS'
→ fS'
→ e {a}
{f}
{ e } {#}
P → qP' {q} {a,f,#}
P' → bP
→ e {b}
{ e } {a,f,#}
LL(1) 分析表为

六、（ 12 分） 给定文法 G[S] ： S → Aa|dAb|Bb|dBa A → c B → c
构造文法 G[S] 的 LR （ 1 ）分析表。
分析表如下图所示

七、（ 8 分） 将下面的条件语句表示成逆波兰式和四元式序列：
if a>b then x:=a+b*c else x:=b-a;
答：（ 1 ）逆波兰式：
,其中， BLE 表示汪或等于时的转向指令； [ … ] 表示标号。
（ 2 ）四元式：
(1) ( j>, a, b, (3))
(2) ( j, , , (7) )
(3) ( *, b, c, T1)
(4) ( +, a, T1, T2)
(5) ( :=, T2, , x)
(6) ( j, , , (9))
(7) ( -, b, a, T3)
(8) ( :=, T3, , x)
(9) ( … … )
八、（ 8 分） 给定基本块：
A:=3*5
B:=E+F
C:=A+12
D:=E+F
A:=D+12
C:=C+1
E:=E+F
假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。
答：化简后的的四元式序列为
A :=D+12
E :=E+F
C :=28

⑻ 陈火旺编译原理什么是符号表 符号表有哪些重要作用

符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方...

⑼ 编译原理 词法分析

C语言词法分析器
#include<iostream>
#include<stdio.h>
#include<string>

using namespace std;

FILE *f; //定义一个文件变量
static int line = 1; //表示光标所在的行数
struct ID{ char *name; int count;}id[100];//用于存放ID号码
static int I = 0; //用于记录ID存放的数量
int Number[100]; //用于存放数字
static int P = 0; //用于记录存放数字的个数
int error[100] = {0}; //用于记录错误所在的行数
static int K = 0; //记录错误次数
void Error(); //记录错误
void loginID(char *); //注册ID号
void loginNumber(int &); //记录数字
void noteLine(char &); //记录光标所在的行数
void print(); //输出分析结果
int same(char *chr); //判断单词是否已经存在

void Error()
{ error[K++] = line; }

void loginID(char *chr) //注册ID号
{
int k = 0;
int h = 0;
for(int i = 0; i < I; i++)
{
if(!strcmp(chr,id.name)) //如果单词已经存在
{
id.count++;
k = 1;
}
}
if(k == 0) //该单词不存在
{
h = I + 1;
//I = h;
id[h].count++;
id[h].name = chr;
//strcpy(id[h].name ,chr);
}

}

void loginNumber(int &nu)
{ Number[P++] = nu; }

void noteLine(char &ch)
{
if ( ch == ' ' )
++line;
}

void print()//输出部分
{
//cout << "关键字以及变量:" << endl;
//for(int i = 0; i < 100; i++)
//cout << i <<" " << id.name << " " << id.count << endl;
cout << "数字：" << endl;
for(int i = 1; i <= P; i++)
cout << i << ": " << Number[i-1] << endl;
if(error[0] != 0)
{
cout << "出现的错误！" << endl;
for(int i = 1; i <= K; i++)
cout << "第" << i << "个错误： " << "第" << error[i-1] << "行" << endl;
}
else cout << "没有错误！" << endl;
}

//文件处理部分
void noblank( char &ch) //跳过空格，回车
{
noteLine(ch);
while(ch == ' ' || ch == ' ')
ch = fgetc(f);
}

void identifier(char name[],char &ch)//字母变量
{

int i;
for(i = 0; i < 20; i++)
name = '';
i = 0;
while (('0'<= ch && ch <= '9')||('a'<= ch&&ch <= 'z')||('A'<= ch&&ch <='Z'))
{
name = ch;
i++;
ch = fgetc(f);
}
loginID(name);
//for(int j = 0; j < i; j++)
//{cout << name[j];}
// cout << ' ';

}

int number(char &ch)//数字
{
int num=0;
while('0'<= ch && ch <= '9')
{
num = num* 10 + (ch-'0');
ch = fgetc(f);
}
if( ('a'<= ch&&ch <= 'z')||('A'<= ch&&ch <='Z'))
{
Error();
}
else if( ch == '.')
{;}
loginNumber(num); //记录数字
return num;
}

void test(char &ch)//符号
{
char str[2]={'0/'};
if(ch == '*')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '.')
{ str[0] = ch; ch = fgetc(f);}
if(ch == ',')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '"')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '/')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '%')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '^')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '-')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '{')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '}')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '[')
{ str[0] = ch; ch = fgetc(f);}
if(ch == ']')
{ str[0] = ch; ch = fgetc(f);}
if(ch == ';')
{str[0] = ch; ch = fgetc(f);}
if(ch == ':')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '?')
{ str[0] = ch; ch = fgetc(f);}
if(ch == '(')
{ str[0] = ch; ch = fgetc(f);}
if(ch == ')')
{str[0] = ch; ch = fgetc(f);}
if(ch =='+')
{

str[0] = ch;
if((ch = fgetc(f)) == '+' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

//cout << str[0]<< endl;
}
if(ch == '-')
{

str[0] = ch;
if((ch = fgetc(f)) == '-' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

//cout << str[0]<< endl;
}
if(ch == '&')
{

str[0] = ch;
if((ch = fgetc(f)) == '&' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

//cout << str[0]<< endl;
}
if(ch == '|')
{

str[0] = ch;
if((ch = fgetc(f)) == '|' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

//cout << str[0]<< endl;
}
if(ch == '!')
{

str[0] = ch;
if((ch = fgetc(f)) == '=' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

//cout << str[0]<< endl;
}
if(ch == '=')
{

str[0] = ch;
if((ch = fgetc(f)) == '=' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

}
if(ch == '>')
{

str[0] = ch;
if((ch = fgetc(f)) == '=' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}
else
if(ch == '>' )
{
str[1] = ch;
ch = fgetc(f);
//cout << str[0] << str[1] << endl;
}

}
if(ch == '<')
{
str[0] = ch;
if((ch = fgetc(f)) == '=' )
{
str[1] = ch;
ch = fgetc(f);
}
else
if(ch == '<' )
{
str[1] = ch;
ch = fgetc(f);
}

}

}

int main()
{
char ch;
char name[30];
for(int i = 0; i < 30; i++)
name = '/0';
f = fopen("c.txt","r"); //打开指定输入文件
if (f == NULL)
cout<<"文件不存在！"<<endl;
ch = fgetc(f);
while(!feof(f))
{
noblank( ch ); //跳过回车，空格
if( ( ch >= 'a' && ch <= 'z' )||( ch >= 'A' && ch <= 'Z' ))
{ identifier(name,ch); } //处理字母
else if( ch >= '0'&& ch <= '9')
{ number(ch); } //处理数字
else
{ test(ch); } //处理符号
}
print(); //打印词法分析结果
fclose(f); //关闭文件
system("pause");
return 0;
}

⑽ 编译程序有编译和翻译两种方式分别对其说明并比较 急 在线等

编译程序 编译程序
compiler
把用高级程序设计语言书写的源程序，翻译成等价的计算机汇编语言或机器语言的目标程序的翻译程序。编译程序属于采用生成性实现途径实现的翻译程序。它以高级程序设计语言书写的源程序作为输入，而以汇编语言或机器语言表示的目标程序作为输出。编译出的目标程序通常还要经历运行阶段，以便在运行程序的支持下运行，加工初始数据，算出所需的计算结果。编译程序的实现算法较为复杂。这是因为它所翻译的语句与目标语言的指令不是一一对应关系,而是一多对应关系;同时也因为它要处理递归调用、动态存储分配、多种数据类型，以及语句间的紧密依赖关系。但是，由于高级程序设计语言书写的程序具有易读、易移植和表达能力强等特点，编译程序广泛地用于翻译规模较大、复杂性较高、且需要高效运行的高级语言书写的源程序。
功能 编译程序的基本功能是把源程序翻译成目标程序。但是,作为一个具有实际应用价值的编译系统,除了基本功能之外，还应具备语法检查、调试措施、修改手段、覆盖处理、目标程序优化、不同语言合用以及人-机联系等重要功能。①语法检查:检查源程序是否合乎语法。如果不符合语法，编译程序要指出语法错误的部位、性质和有关信息。编译程序应使用户一次上机，能够尽可能多地查出错误。②调试措施：检查源程序是否合乎设计者的意图。为此，要求编译程序在编译出的目标程序中安置一些输出指令，以便在目标程序运行时能输出程序动态执行情况的信息，如变量值的更改、程序执行时所经历的线路等。这些信息有助于用户核实和验证源程序是否表达了算法要求。③修改手段：为用户提供简便的修改源程序的手段。编译程序通常要提供批量修改手段（用于修改数量较大或临时不易修改的错误）和现场修改手段（用于运行时修改数量较少、临时易改的错误）。④覆盖处理：主要是为处理程序长、数据量大的大型问题程序而设置的。基本思想是让一些程序段和数据公用某些存储区，其中只存放当前要用的程序或数据;其余暂时不用的程序和数据,先存放在磁盘等辅助存储器中，待需要时动态地调入。⑤目标程序优化：提高目标程序的质量,即占用的存储空间少,程序的运行时间短。依据优化目标的不同，编译程序可选择实现表达式优化、循环优化或程序全局优化。目标程序优化有的在源程序级上进行，有的在目标程序级上进行。⑥不同语言合用：其功能有助于用户利用多种程序设计语言编写应用程序或套用已有的不同语言书写的程序模块。最为常见的是高级语言和汇编语言的合用。这不但可以弥补高级语言难于表达某些非数值加工操作或直接控制、访问外围设备和硬件寄存器之不足，而且还有利于用汇编语言编写核心部分程序,以提高运行效率。⑦人-机联系：确定编译程序实现方案时达到精心设计的功能。目的是便于用户在编译和运行阶段及时了解内部工作情况，有效地监督、控制系统的运行。
早期编译程序的实现方案，是把上述各项功能完全收纳在编译程序之中。然而，习惯做法是在操作系统的支持下，配置调试程序、编辑程序和连接装配程序，用以协助实现程序的调试、修改、覆盖处理，以及不同语言合用功能。但在设计编译程序时，仍须精心考虑如何与这些子系统衔接等问题。
工作过程 编译程序必须分析源程序，然后综合成目标程序。首先，检查源程序的正确性，并把它分解成若干基本成分；其次，再根据这些基本成分建立相应等价的目标程序部分。为了完成这些工作，编译程序要在分析阶段建立一些表格,改造源程序为中间语言形式,以便在分析和综合时易于引用和加工（图1）。
数据结构 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序。符号表由源程序中所用的标识符连同它们的属性组成，其中属性包括种类（如变量、数组、结构、函数、过程等）、类型（如整型、实型、字符串、复型、标号等），以及目标程序所需的其他信息。常数表由源程序中用的常数组成，其中包括常数的机内表示，以及分配给它们的目标程序地址。中间语言程序是将源程序翻译为目标程序前引入的一种中间形式的程序，其表示形式的选择取决于编译程序以后如何使用和加工它。常用的中间语言形式有波兰表示、三元组、四元组以及间接三元组等。
分析部分 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序）完成，其任务是识别单词（即标识符、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法。如不合乎语法，则输出语法出错信息；如合乎语法，则分解源程序的语法结构，构造中间语言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序是进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。
综合部分 综合阶段必须根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成。代码优化是通过重排和改变程序中的某些操作，以产生更加有效的目标程序。存储分配的任务是为程序和数据分配运行时的存储单元。代码生成的主要任务是产生与中间语言程序符等价的目标程序，顺序加工中间语言程序，并利用符号表和常数表中的信息生成一系列的汇编语言或机器语言指令。
结构 编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、 语义分析、 代码优化、存储分配和代码生成等六个相继的逻辑步骤。这六个步骤只表示编译程序各部分之间的逻辑联系，而不是时间关系。编译过程既可以按照这六个逻辑步骤顺序地执行，也可以按照平行互锁方式去执行。在确定编译程序的具体结构时，常常分若干遍实现。对于源程序或中间语言程序，从头到尾扫视一次并实现所规定的工作称作一遍。每一遍可以完成一个或相连几个逻辑步骤的工作。例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍。反之，为了适应较小的存储空间或提高目标程序质量，也可以把一个逻辑步骤的工作分为几遍去执行。例如，代码优化可划分为代码优化准备工作和实际代码优化两遍进行。
一个编译程序是否分遍,以及如何分遍,根据具体情况而定。其判别标准可以是存储容量的大小、源语言的繁简、解题范围的宽窄，以及设计、编制人员的多少等。分遍的好处是各遍功能独立单纯、相互联系简单、逻辑结构清晰、优化准备工作充分。缺点是各遍之中不可避免地要有些重复的部分，而且遍和遍之间要有交接工作，因之增加了编译程序的长度和编译时间。
一遍编译程序是一种极端情况，整个编译程序同时驻留在内存,彼此之间采用调用转接方式连接在一起(图2)。当语法分析程序需要新符号时，它就调用词法分析程序；当它识别出某一语法结构时，它就调用语义分析程序。语义分析程序对识别出的结构进行语义检查，并调用“存储分配”和“代码生成”程序生成相应的目标语言指令。
随着程序设计语言在形式化、结构化、直观化和智能化等方面的发展，作为实现相应语言功能的编译程序，也正向自动程序设计的目标发展，以便提供理想的程序设计工具。
参考书目
陈火旺、钱家骅、孙永强编：《编译原理》，国防工业出版社，北京，1980。
A.V.Aho, Principles of Compiler Design,Addison Wes-ley, Reading, Massachusetts, 1977.
--------------------------------------------------------------------------------
编译程序 (compiler)
将用高级程序设计语言书写的源程序，翻译成等价的用计算机汇编语言、机器语言或某种中间语言表示的目标程序的翻译程序。用户利用编译程序实现数据处理任务时，先要经历编译阶段，再经历运行阶段。编译阶段以源程序作为输入，以目标程序作为输出，其主要任务是将源程序翻译成目标程序。运行阶段的任务是运行所编译出的目标程序，实现源程序中指定的数据处理任务，其工作通常包括：输入初始数据，对数据或文件进行数据加工，输出必要信息和加工结果等。编译程序的实现算法较为复杂。这是因为它所翻译的语句与目标语言的指令不是一一对应关系，而是一多对应关系；同时因为它要在编译阶段处理递归调用、动态存储分配、多种数据类型 实现 、 代码生成与代码优化等繁杂技术问题；还要在运行阶段提供良好、有效的运行环境。由于高级程序设计语言书写的程序具有易读、易移植和表达能力强等特点，所以编译程序广泛地用于翻译规模较大、复杂性较高、且需要高效运行的高级语言书写的源程序。
功能 编译程序的基本功能是把源程序翻译成目标程序。此外，还要具备语法检查、调试措施、修改手段、覆盖处理、目标程序优化、不同语言合用以及人机联系等具有实际应用价值的重要功能。①语法检查。检查源程序是否合乎语法 。②调试措施。检查源程序是否合乎用户的设计意图。③修改手段。为用户提供简便的修改源程序的手段。④覆盖处理。主要为处理程序较长、数据量较大的大型问题程序而设置。基本思想是让一些程序段和数据公用某些存储区，其中只存放当前要用的程序段或数据，其余暂时不用的程序段和数据均存放在磁盘等辅助存储器中，待需要时动态地调入存储区中运行。⑤目标程序优化。提高目标程序的质量，即使编译出的目标程序运行时间短、占用存储少。⑥不同语言合用 。便于用户利用多种程序设计语言编写应用程序或套用已有的不同语言书写的程序模块。最为常见的是高级语言和汇编语言的合用。⑦人机联系。便于用户在编译和运行阶段及时了解系统内部工作情况，有效地监督、控制系统的运行。
早期编译程序的实现方案，是把上述各项功能完全收纳在编译程序之中 。后来的习惯方法是在操作系统的支持下，配置编辑程序、调试程序、连接装配程序等实用程序或工具软件，目的是创造一个良好的开发环境和运行环境，便于应用软件的编程、修改、调试、集成以及报表生成、界面设计等工作。但编译程序设计者设计编译方案时，仍需精心考虑上述各项功能，较好地解决目标程序与这些实用程序或软件工具之间的配合与衔接等问题。
工作过程 编译程序必须分析源程序，然后综合成目标程序。为达到这个目的，编译程序要在分析阶段建立一些表格，改造源程序为中间语言形式，以便在分析和综合时易于引用和加工。
数据结构 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序。符号表由源程序中所用的标识符连同它们的属性组成，其中属性包括种类（如变量、数组、结构、函数、过程等）、类型（如整型、实型、字符串、复型、标号等），以及目标程序所需的其他信息。常数表由源程序中用的常数组成，其中包括常数的机内表示以及分配给它们的目标程序地址。中间语言程序是将源程序翻译成目标程序前引入的一种中间形式的程序，其表示形式的选择取决于编译程序以后如何使用它和如何加工它。常用的中间语言形式有波兰表示、三元组、四元组以及间接三元组等。
分析部分 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序 ）完成，其任务是识别单词（即标识符 、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法，并分解源程序。如果不合乎语法，则输出语法出错信息；如果合乎语法，则分解源程 序的语法结构， 构造中间语 言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。
综合部分 综合阶段根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成。代码优化是通过重排和改变程序中的某些操作，以产生更加有效的目标程序。存储分配是为程序和数据分配运行时的存储单元。 代码生成是产 生与中间语 言程序等价的目标程序，亦即，顺序加工中间语言程序，利用符号表和常数表中的信息生成一系列的汇编语言或机器语言指令。
动态 20世纪80年代以后，程序设计语言在形式化、结构化、直观化和智能化等方面有了长足的进步和发展，主要表现在两个方面：①随着程序设计理论和方法的发展，相继推出了一系列新型程序设计语言，如结构化程序设计语言、并发程序设计语言、分布式程序设计语言、函数式程序设计语言、智能化程序设计语言、面向对象程序设计语言等；②基于语法、语义和语用方面的研究成果，从不同的角度和层次上深刻地揭示了程序设计语言的内在规律和外在表现形式。与此相应地，作为实现程序设计语言重要手段之一的编译程序，在体系结构、设计思想、实现技术和处理内容等方面均有不同程度的发展、变化和扩充。另外，编译程序已作为实现编程的重要软件工具，被纳入到软件支援环境的基本层软件工具之中。因此，规划编译程序实现方案时，应从所处的具体软件支援环境出发，既要遵循整个环境的全局性要求和规定，又要精心考虑与其他诸层软件 工具之间的相互支援、配合和衔接关系。