一个简单语言的编译实例.docx
《一个简单语言的编译实例.docx》由会员分享，可在线阅读，更多相关《一个简单语言的编译实例.docx（33页珍藏版）》请在冰点文库上搜索。
一个简单语言的编译实例
一个简单语言的编译实例
1语言的文法产生式集合
·程序定义
<程序>program<标识符><分程序>.
<分程序><变量说明><复合语句>
·语句定义
<变量说明>var<标识符表>：
<类型>；
<标识符表><标识符>，<标识符表>|<标识符>
<复合语句>begin<语句表>end
<语句表><赋值语句>；<语句表>|<赋值语句>
<赋值语句><标识符>:
=<算术表达式>
·算术表达式定义
<算术表达式><算术表达式>ω0<项>|<项>
<项><项>ω1<因子>|<因子>
<因子><算术量>|（<算术表达式>）
<算术量><标识符>|<常数>
·类型定义
<类型>integer|real|char
·单词集定义
<标识符><字母>|<标识符><数字>|<标识符><字母>
<常数><整数>|<实数>
<整数><数字>|<整数><数字>
<实数><整数>.<整数>
·字符集定义
<字母>A|B|C|…|Z|a|b|c|…|z
<数字>0|1|2|3|4|5|6|7|8|9
其中：
ω0—+或-
ω1—*或/
例：
·源程序：
programexample
vara,b:
integer;
begin
a:
=2;
b:
=2*5+a
end.
·推导过程：
<程序>program<标识符><分程序>.
programexample
<分程序>.
programexample
<变量说明>
<复合语句>.
programexample
var<标识符表>：
<类型>；
<复合语句>.
programexample
vara，b：
<类型>；
<复合语句>.
programexample
vara，b：
integer；
<复合语句>.
programexample
vara，b：
integer；
begin<语句表>end.
programexample
vara，b：
integer；
begin
<赋值语句>；
<赋值语句>
end.
programexample
vara，b：
integer；
begin
a:
=2；
b:
=2*5+a
end.
·对应的目标代码程序：
exampleSEGMENT
aDB4DUP（0）
bDB4DUP（0）
tDB4DUP（0）
ASSUMECS:
example,DS:
example
MOVAX,2
MOVa,AX
MOVAX,10
ADDAX,a
MOVt,AX
MOVAX,t
MOVb,AX
INT21H
RET
exampleENDS
2关键字表和界符表
编号
关键字
编号
界符
1
program
1
2
var
2
:
3
integer
3
;
4
real
4
:
=
5
char
5
*
6
begin
6
/
7
end
7
+
8
-
9
.
10
（
11
）
3编译过程：
1．词法分析和语法分析：
·Token序列：
（k,1）,（i,1）,
（k,2）,（i,2）,（p,1）,（i,3）,（p,2）,（k,3）,（p,3）,
（k,6）,
（i,2）,（p,4）,（c,1）,（p,3）,
（i,3）,（p,4）,（c,1）,（p,5）,（c,2）,（p,7）,（i,2）,
（k,7）,（p,9）,
符号表I常数表C
example2
a5
b
2．语义分析：
（1）（k,1）,（i,1）,
·填写符号表：
符号表I
example程序标识符
a
b
·生成中间代码：
①（program,I1,_,_）
（2）（k,2）,（i,2）,（p,1）,（i,3）,（p,2）,（k,3）,（p,3）,
·填写符号表：
假设整型域宽为4；
符号表I
example程序标识符，过程占用总域宽为8
a变量标识符，integer，offset=0
b变量标识符，integer，offset=4
（3）（k,6）,
·无语义动作；
（4）（i,2）,（p,4）,（c,1）,（p,3）,
·生成中间代码：
②（:
=,C1,_,I2）
（5）（i,3）,（p,4）,（c,1）,（p,5）,（c,2）,（p,7）,（i,2）,
·生成中间代码：
③（*,C1,C2,t1）
④（+,t1,I2,t2）
⑤（:
=,t2,_,I3）
·建立中间变量表：
中间变量表I’
t1integer
t2integer
（6）（k,7）,（p,9）,
·生成中间代码：
⑥（end,_,_,_）
中间代码序列为：
①（program,I1,_,_）
②（:
=,C1,_,I2）
③（*,C1,C2,t1）
④（+,t1,I2,t2）
⑤（:
=,t2,_,I3）
⑥（end,I1,_,_）
4．优化：
·优化中间代码：
①（program,I1,_,_）
②（:
=,C1,_,I2）
③（+,10,I2,t2）
④（:
=,t2,_,I3）
⑤（end,I1,_,_）
·中间变量t2填入符号表：
符号表I
example程序标识符，过程占用总域宽为12
a变量标识符，integer，offset=0
b变量标识符，integer，offset=4
t2变量标识符，integer，offset=8
5．目标代码生成：
①（program,I1,_,_）exampleSEGMENT
DB12DUP（0）
ASSUMECS:
example,DS:
example
②（:
=,C1,_,I2）MOVAX,2
MOV[0000H],AX
③（+,10,I2,I4）MOVAX,10
ADDAX,[0000H]
MOV[0008H],AX
④（:
=,I4,_,I3）MOVAX,[0008H]
MOV[0004H],AX
⑤（end,I1,_,_）INT21H
RET
exampleENDS
4上机实践
1）．文法：
PROGRAMprogramidSUB_PROGRAM.
SUB_PROGRAMVARIABLECOM_SENTENCE
VARIABLEvarID_SEQUENCE：
TYPE；
ID_SEQUENCEid{，id}
TYPEinteger|real|char
COM_SENTENCEbeginSEN_SEQUENCEend
SEN_SEQUENCEEVA_SENTENCE{；EVA_SENTENCE}
EVA_SENTENCEid:
=EXPRESSION
EXPRESSIONEXPRESSION+TERM|TERM
TERMTERM*FACTOR|FACTOR
FACTORid|cons|（EXPRESSION）
其中：
id—标识符；
cons—常数；
2）．语法分析---递归下降子程序框图：
（1）PROGRAM:
入口
program?
nerr
y
read（w）
id?
nerr
y
read（w）
SUB_PROGRAM
.?
nerr
y
read（w）
出口
（2）SUB_PROGRAM:
入口
VARIABLE
COM_SENTENCE
出口
（3）VARIABLE:
入口
var?
nerr
y
read（w）
ID_SEQUENCE
:
?
nerr
y
read（w）
TYPE
;?
nerr
y
read（w）
出口
（4）ID_SEQUENCE:
入口
id?
nerr
y
read（w）
?
n
y
read（w）read（w）
id?
nerr
y
出口
（5）TYPE:
入口
char?
real?
integer?
nnnerr
yyy
read（w）
出口
（6）COM_SENTENCE:
入口
begin?
nerr
y
read（w）
SEN_SEQUENCE
end?
nerr
y
read（w）
出口
（7）SEN_SEQUENCE:
入口
EVA_SENTENCE
;?
n
y
read（w）
EVA_SENTENCE
出口
（8）EVA_SENTENCE:
入口
id?
nerr
y
read（w）
:
=?
nerr
y
read（w）
EXPRESSION
出口
（9）EXPRESSION:
使用算符优先翻译。
3）．语法分析源程序清单：
//sample.h---类的定义
//
#defineN18
//Pascal常数自动机
intPas_aut[8][5]={2,0,0,0,0,2,3,5,8,8,4,0,0,0,0,4,0,5,8,8,
7,0,0,6,0,7,0,0,0,0,7,0,0,8,8,0,0,0,0,0};//状态转换矩阵
//关键字表
charKeys[N][15]={"program","var","integer","real","char","begin","end",
",",":
",";",":
=","*","/","+","-",".","（","）"};
structTokenType
{intcode,value;};//Token结构
structSemRecord//符号表结构
{charname[15];
};
//---------Pascal常数处理机类------------------------------------
classPascalCons
{
private:
intaut[8][5];.//状态转换矩阵
ints;//当前状态
intn,p,m,e,t;//尾数值，指数值，小数位数，指数符号，类型
doublenum;//常数
charch;//当前符号
public:
PascalCons（）;
doublenumber（char*line,int*p）;//拼一个常数
private:
voidProcError（）;
intmap（charch）;
intfind（ints,charch）;
voidact（ints,charch）;
};
//---------扫描器类------------------------------
classScan
{
private:
char*keywords[N];//关键字表、界符表
charline[50];//当前行
inti_line;
charch;//当前字符
charstrToken[15];//当前单词
inti_str;
intcode,value;
inti;
PascalConsnum;//常数对象
SemRecord*p_ID;//符号表指针
int*p_m;
double*p_Cons;//常数表指针
int*p_n;
ifstreamfin;//源程序文件
public:
Scan（）;
Scan（SemRecord*p1,int*p2,double*p3,int*p4）;
voidRead（TokenType*token）;//read（w）
intopenfile（char*filename）;
private:
voidProcError（）;
intIsLetter（charch）;
intIsDigit（charch）;
intReserve（char*strToken）;
intInsertID（char*strToken）;
intInsertConst（doublenum）;
};
//----------语法分析类------------------------------
classSyntax//递归子程序分析
{
private:
TokenTypeToken;//单词Token
ScansExam;//扫描器对象
public:
Syntax（）;
Syntax（SemRecord*p1,int*p2,double*p3,int*p4）;
voidParse（）;
private:
voidPROGRAM（）;//主程序
voidSUB_PROGRAM（）;//分程序
voidVARIABLE（）;//变量说明
voidID_SEQUENCE（）;//标识符表
voidTYPE（）;//类型定义
voidCOM_SENTENCE（）;//复合语句
voidSEN_SEQUENCE（）;//语句表
voidEVA_SENTENCE（）;//赋值语句
voidEXPRESSION（）;//表达式
intmap（intcode）;
};
//-------------------------------------------------------
//------------------------------------------------------
//Pascal常数处理机类成员定义
PascalCons:
:
PascalCons（）
{
inti,j;
for（i=0;i<8;i++）//初始化自动机矩阵
for（j=0;j<5;j++）
aut[i][j]=Pas_aut[i][j];
ch='';
};
voidPascalCons:
:
ProcError（）
{
cout<<"err!
"<};
intPascalCons:
:
map（charch）
{intj;
if（ch>='0'&&ch<='9'）
j=0;
elseif（ch=='.'）
j=1;
elseif（ch=='E'||ch=='e'）
j=2;
elseif（ch=='+'||ch=='-'）
j=3;
else
j=4;
returnj;
}
intPascalCons:
:
find（ints,charch）//s---当前状态；ch---当前符号
{inti,j;//行和列
i=s-1;//将s映射到行标记i
j=map（ch）;//将ch映射到列标记j
returnaut[i][j];//返回下一个状态值
}
voidPascalCons:
:
act（ints,charch）
{
switch（s）
{
case1:
n=0;m=0;p=0;t=0;e=1;num=0;break;
case2:
n=10*n+ch-48;break;
case3:
t=1;break;
case4:
n=10*n+ch-48;m++;break;
case5:
t=1;break;
case6:
if（ch=='-'）e=-1;break;
case7:
p=10*p+ch-48;break;
case8:
num=n*pow（10,e*p-m）;
}
}
doublePascalCons:
:
number（char*line,int*p）//拼一个常数
{
s=1;
act（s,ch）;//执行q1
while（s!
=8）
{
ch=line[*p];//读取当前符号到ch中
（*p）++;
s=find（s,ch）;//查状态表
if（s==0）
break;
act（s,ch）;//执行qs
}
if（s==8）
returnnum;//输出num
else
{
ProcError（）;
return0;//错误处理
}
};
//--------------------------------------------------------
//扫描器类成员定义
Scan:
:
Scan（SemRecord*p1,int*p2,double*p3,int*p4）
{
p_ID=p1;//扫描器用符号表和常数表的指针初始化
p_m=p2;
p_Cons=p3;
p_n=p4;
inti;
for（i=0;ikeywords[i]=Keys[i];
i_line=0;
line[i_line]='\0';
};
intScan:
:
openfile（char*filename）
{
fin.open（filename）;
if（!
fin）
{
cout<<"Can'topeninputfile.\n";
return0;
}
return1;
};
voidPrint（structTokenTypetoken）//输出Token
{
printf（"（%d%d）",token.code,token.value）;
}
voidScan:
:
ProcError（）
{
printf（"err!
"）;
}
intScan:
:
IsLetter（charch）//判断ch是否为字母
{if（ch>='A'&&ch<='Z'||ch>='a'&&ch<='z'）
return1;
else
return0;
}
intScan:
:
IsDigit（charch）//判断ch是否为数字
{if（ch>='0'&&ch<='9'）
return1;
else
return0;
}
intScan:
:
Reserve（char*strToken）
//用strToken中的单词去查关键字表。
查到了，则返回该关键字的编码；
//否则，返回0
{inti=0;
while（i{if（!
strcmp（keywords[i],strToken））
return（i+3）;
i++;
}
return0;
}
intScan:
:
InsertID（char*strToken）
//用strToken中的单词去查符号表。
查到了，则返回该单词在表中的位置值；
//否则，将strToken中的单词插入符号表的尾部，并返回位置值
{inti=0;
while（i<*p_m）//设m为符号表中已有的标识符的个数
{if（!
strcmp（（p_ID+i）->name,strToken））
returni;
i++;
}
strcpy（（p_ID+i）->name,strToken）;
（*p_m）++;
returni;
}
intScan:
:
InsertConst（doublenum）
//用拼好的num去查常数表。
查到了，则返回该单词在表中的位置值；
//否则，将num插入常数表的尾部，并返回位置值
{inti=0;
while（i<*p_n）//设n为常数表中已有的常数的个数
{if（p_Cons[i]==num）
returni;
i++;
}
p_Cons[i]=num;
（*p_n）++;
returni;
}
voidScan:
:
Read（TokenType*token）
{
doubleconst_num;//常数值变量
if（line[i_line]=='\0'）//当行缓冲区空时，读入一行
{
if（fin.getline（line,50,'\n'））//读到了一行
i_line=0;
else
{
token->code=0;//文件结束，返回Token（0，-1）
token->value=-1;
return;
}
};
ch=line[i_line++];//读取当前单词的第一个符号到ch中
while（ch==''）//滤除空格
ch=line[i_line++];
i_str=0;
if（IsLetter（ch））
{
while（IsLetter（ch）||IsDigit（ch））//拼关键字或标识符
{strToken[i_str++]=ch;//将ch中的字符拼接到strToken中
ch=line[i_line++];//读取当前字符到ch
}
i_line--;//Retract（）
strToken[i_str]='\0';
code=Reserve（strToken）;//查关键字表；
if（!
code）//未查到，是一个标识符
{
value=InsertID（strToken）;//将strToken中的单词插入到符号表中
token->code=1;
token->value=value;
}
else
{
token->code=code;
token->value=-1;
}
}
elseif（IsDigit（ch））//处理常数
{
i_line--;
const_num=num.number（line,&i_line）;//拼常数到const_num
升级会员 