编译原理实验报告.doc

编译方法实验报告

实验1：扫描器的设计
一、 实验目的
熟悉并实现一个扫描器（词法分析程序）。
二、 实验要求
(1) 设计扫描器的有限自动机（识别器）；
(2) 设计翻译、生成Token的算法（翻译器）；
(3) 编写代码并上机调试运行通过。
·输入——源程序文件或源程序字符串；
·输出——相应的Token序列；
关键字表和界符表；
符号表和常数表；
三、 实验步骤
流程：
初始化；
打开用户源程序文件；
while （文件未结束）
{ 读入一行到w[i]，i=0;
do //处理一行，每次处理一个单词
{ 滤空格，直到第一个非空的w[i]；
i--；
s=1; //处理一个单词开始
while （s!=0） //拼单词并生成相应Token
{
act(s); //执行qs
if （s>=11 && s<=14） //一个单词处理结束
break;
i++; //getchar()
s=find(s, w[i]);
}
if （s==0）
词法错误；
}while （w[i]!=换行符）；
}
关闭用户源程序文件；
生成Token文件；
输出关键字表；
输出Token序列；
输出符号表；
输出常数表；

有限自动机的状态转换图：
e
d d d
+|- -1/+/-
11
+① d ② . ③ d ④ e ⑤ ⑥ d ⑦
d -
-1/+/-
l/d -1/+/-
12
-1
l ⑧ -
13
-1
b ⑨ b ⑩ -
14
-1
-
15
-1
-
其中：d为数字，l为字母，b为界符，-1代表其它符号（如在状态8处遇到了非字母或数字的其它符号，会变换到状态12）。

关键字表和界符表：
Program
;
Begin
:
End
(
Var
)
While
,
Do
:=
Repeat
+
Until
-
For
*
To
/
If
>
Then
>=
Else
==

<

<=

四、 主要数据结构
①状态转换矩阵：int aut[10][7]={ 2, 0, 0, 0, 8, 9, 15,
2, 3, 5,11, 0, 0, 11,
4, 0, 0, 0, 0, 0, 0,
4, 0, 5,11, 0, 0, 11,
7, 0, 0, 6, 0, 0, 0,
7, 0, 0, 0, 0, 0, 0,
7, 0, 0,11, 0, 0, 11,
8, 0, 0, 0, 8, 0, 12,
0, 0, 0, 0, 0, 10, 14,
0, 0, 0, 0, 0, 0, 13};

②关键字表：
char keywords[30][12]={“program”,”begin”,”end”,”var”,”while”,”do”,
”repeat”,”until”,”for”,”to”,”if”,”then”,”else”, “;”, ”:”, ”(“, ”)”, ”,”, ”:=”, ”+”, ”-“, ”*”, ”/”,
”>”, ”>=”, ”==”, “<”, “<=”};
③符号表：char ID[50][12]; //表中存有源程序中的标识符
④常数表：float C[20];
⑤其它变量： struct token
{ int code;
int value}; //Token结构
struct token tok[100]; //Token数组
int s; //当前状态
int n,p,m,e,t; //尾数值，指数值，小数位数，指数符号，类型
float num; //常数值
char w[50]; //源程序缓冲区
int i; //源程序指针,当前字符为w[i]
char strTOKEN[12]; //当前已经识别出的单词

五、 实验核心代码
int main(int argc, char* argv[])
{
FILE *fp;
int s; //当前状态 *有限自动机中的状态
fp=fopen("exa.txt","r");
while (!feof(fp))
{
fgets(w,50,fp);
i=0;
//*处理一行
do
{
printf("%c ",w[i]); //测试 显示每个token的首字母

//*处理一个token
while (w[i]==' ') //滤空格
i++;

if (w[i]>='a' && w[i]<='z') //判定单词类别 *是字母（关键字或标识符）
{
ptr=col2; num_map=2;
}
else if (w[i]>='0' && w[i]<='9') //*是数字（常量的开头）
{
ptr=col1; num_map=4;
}
else if (strchr(col3[0].str,w[i])==NULL) //*其他字符 算为非法字符
{
printf("非法字符%c\n",w[i]);
i++;
continue;
}
else //界符
{
ptr=col3; num_map=1;
}

i--; //*向后退一个字符
s=1; //开始处理一个单词
while (s!=0)
{
act(s);
if (s>=11 && s<=14) //*判断是否是终止状态 *是终止状态，则形成一个token
break;
i++; //getchar() *读取下一个字符
s=find(s,w[i]); //状态转换
}
if (s==0)
{
strTOKEN[i_str]='\0';
printf("词法错误：%s\n",strTOKEN);
}

}while (w[i]!=10);
}

printf("关键字表："); //输出结果
for (i=0;i<30;i++)
printf("%s ",keywords[i]);
printf("\n");
printf("Token序列：");
for (i=0;i<num_token;i++)
printf("(%d,%d)",tok[i].code,tok[i].value);
printf("\n");
printf("符号表：");
for (i=0;i<num_ID;i++)
printf("%s ",ID[i]);
printf("\n");
printf("常数表：");
for (i=0;i<num_C;i++)
printf("%d ",C[i]);
printf("\n");

fclose(fp);
printf("Hello World!\n");
return 0;
}

//*状态转换后，达到新的状态之后，记录的变化
void act(int s)
{
int code;
switch (s)
{
case 1:n=0;m=0;p=0;t=0;e=1;num=0;i_str=0;
strTOKEN[i_str]='\0'; //其它变量初始化
break;
case 2:n=10*n+w[i]-48;
break;
case 3:t=1;
break;
case 4:n=10*n+w[i]-48; m++;
break;
case 5:t=1;
break;
case 6:if (w[i]=='-') e=-1;
break;
case 7:p=10*p+w[i]-48;
break;
case 8:strTOKEN[i_str++]=w[i]; //将ch中的符号拼接到strTOKEN的尾部；
break;
case 9:strTOKEN[i_str++]=w[i]; //将ch中的符号拼接到strTOKEN的尾部；
break;
case 10:strTOKEN[i_str++]=w[i]; //将ch中的符号拼接到strTOKEN的尾部；
break;
case 11:num=n*pow(10,e*p-m); //计算常数值
tok[i_token].code=2; tok[i_token++].value=InsertConst(num); //生成常数Token
num_token++;
break;
case 12:strTOKEN[i_str]='\0';
code=Reserve(strTOKEN); //查关键字表
if (code)
{ tok[i_token].code=code; tok[i_token++].value=0; } //生成关键字Token
else
{ tok[i_token].code=1;
tok[i_token++].value=InsertID(strTOKEN); } //生成标识符Token
num_token++;
break;
case 13:strTOKEN[i_str]='\0';
code=Reserve(strTOKEN); //查界符表
if (code)
{ tok[i_token].code=code; tok[i_token++].value=0; } //生成界符Token
else
{
strTOKEN[strlen(strTOKEN)-1]='\0'; //单界符
i--;
code=Reserve(strTOKEN); //查界符表
tok[i_token].code=code; tok[i_token++].value=0; //生成界符Token
}
num_token++;
break;
case 14:strTOKEN[i_str]='\0';
code=Reserve(strTOKEN); //查界符表
tok[i_token].code=code; tok[i_token++].value=0; //生成界符Token
num_token++;
break;
}
}

//*状态转换
int find(int s,char ch)
{
int i,col=7;
struct map *p;
p=ptr;
for (i=0;i<num_map;i++)
if (strchr((p+i)->str,ch))
{
col=(p+i)->col;
break;
}
return aut[s][col];
}

//*向常量表中插入常量
int InsertConst(double num)
{
int i;
for (i=0;i<num_C;i++)
if (num==C[i])
return i;
C[i]= (int)num;
num_C++;
return i;
}

int Reserve(char *str)
{
int i;
for (i=0;i<num_key;i++)
if (!strcmp(keywords[i],str))
return (i+3);
return 0;
}

//*向符号表中插入新的符号
int InsertID(char *str)
{
int i;
for (i=0;i<num_ID;i++)
if (!strcmp(ID[i],str)) //*符号已经存在，则返回地址
return i;
strcpy(ID[i],str);
num_ID++;
return i;
}

六、 实验结果

实验思考题：
1.扫描器的任务是什么？
答：词法分析程序又称扫描器，任务有：
(1) 识别单词
——从用户的源程序中把单词分离出来;
(2) 翻译单词
——把单词转换成机内表示，便于后续处理。

2.扫描器、识别器、翻译器三者之间的关系是怎样的？
答：扫描器、识别器、翻译器三者之间的关系是：
扫描器的实现要通过识别器和翻译器

1. 为什么说有限自动机是词法分析的基础？
答：因为词法分析的包括：识别--- 识别单词的有限自动机。
和翻译--- 根据有限自动机所识别出的对象，完成从单词串到单词的TOKEN串的翻译。我们可以看出，不论是识别还是分析，都是应用有限自动机，所以可以说有限自动机是词法分析的基础。

实验2：中间代码生成器的设计
一、 实验目的
熟悉算术表达式的语法分析与中间代码生成原理。
二、 实验要求
(1) 设计语法制导翻译生成表达式的四元式的算法；
(2) 编写代码并上机调试运行通过。
·输入——算术表达式
·输出——语法分析结果
相应的四元式序列
(3) 本实验已给出递归子程序法的四元式属性翻译文法的设计，鼓励学生在此基础上进行创新，即设计LL(1)分析法或LR(0)分析法的属性翻译文法，并根据这些属性翻译文法，使用扩展的语法分析器实现语法制导翻译。
三、 设计概要
(1) 算术表达式文法
G(E)： E à E ω0 T | T
T à T ω1 F | F
F à i | (E)

(2) 文法变换
G’(E) E à T {ω0 T}
T à F {ω1 F}
F à i | (E)

(3) 属性翻译文法：
E à T {ω0 “push(SYN, w)” T “QUAT”}
T à F {ω1 “push(SYN, w)” F “QUAT”}
F à i “push(SEM, entry(w))” | (E)
其中：· push(SYN, w) — 当前单词w入算符栈SYN;
· push(SEM, entry(w)) — 当前w在符号表中的入口值压入语义栈SEM;
· QUAT — 生成四元式函数
i．T = newtemp;
ii．QT[j] =( SYN[k], SEM[s-1], SEM[s], T); j++;
iii．pop( SYN, _ ); pop( SEM, _ ); pop( SEM, _ );
push( SEM, T );

(4) 递归下降子程序：
·数据结构：SYN —算符栈；
SEM —语义栈；

E: 入口 T: 入口

T F

n ω0? n ω1?
y y
出口 push(SYN, w) 出口 push(SYN, w)

read(w) QUAT read(w) QUAT

T F

F: 入口 主程序：Z àE

( ? n i ? n err
read(w) read(w)
push(SEM, entry(w)) E
E
err n # ?
err n ) ? y
y 输出四元式序列
read(w)
结束
开始

出口

四、 实验核心代码
void main() //主函数
{ t = 1;
cout<<"输入表达式，以#结束:"<<endl;
Z();
}
string its(int a){ //整形变成字符串形函数
string d;
char b='0',c;
int i;
while(a!=0){
i = a%10;
a = a/10;
c = (int)b + i;
d = c + d;
}
return d;
}

char F(char w){ //F自动机
string theWord;
if(w>='a'&&w<='z'||w>='A'&&w<='Z'){
theWord = w; //当前字符是字母
markStack.push(theWord); //则压栈
}
else if(w == '('){ //是左括号
cin>>w; //则读取下一字符
w = E(w);
if(w!=')'){ //不是右括号则输入有误，报错
cerr<<"输入错误!"<<endl;
exit(0);
}
}
else{ //否则有误，报错
cerr<<"输入错误!"<<endl;
exit(0);
}
cin>>w; //读取下一字符
return w;
}

char E(char w){ //E自动机
string operate,a,b,c;
string state[5];
w = T(w);
while(w=='+'||w=='-'){ //是加或减符号
operate = w;
cin>>w; //读入下一字符
w = T(w);
b = markStack.pop(); //字符栈弹出
a = markStack.pop(); //两个操作字符
cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<t<<")"<<endl;
c = "t"+its(t); //输出四元式
markStack.push(c); //新状态压栈
t++; //状态计数加一
}
return w;
}

char T(char w){
string operate,a,b,c;
string state[5];
w = F(w);
while(w=='*'||w=='/'){
operate = w;
cin>>w; //读取下一字符
w = F(w);
b = markStack.pop(); //符号栈弹出
a = markStack.pop(); //两个操作字符
cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<t<<")"<<endl;
c = "t"+its(t);
markStack.push(c);
t++;
}
return w;
}

bool Z(){ //Z自动机
char w;
cin>>w;
w = E(w);
if(w=='#'){ //遇到"#"则结束
return true;
}
else{
return false;
}
}

五、 实验结果

实验思考题：
1. 语法分析分为几类？其关键技术各是什么？
答： 自顶向下法（推导法）
从开始符号出发，采用推导运算，试图自顶向下构造语法树。
自底向上法（归约法）
从给定的符号串出发，采用归约运算，试图自底向上构造语法树。

2. 什么是递归下降子程序法，什么是LL(1)分析法？二者对文法各有什么要求？
答： 递归下降子程序法：递归子程序法属于自顶向下语法分析方法。故又名递归下降法。要求文法是LL(1)文法。
LL(1)分析法：LL(1)分析法是指从左到右扫描(第一个 L) 、最左推导(第二个 L)和只查看一个当前符号(括号中的 1)之意；LL(1)分析法又称预测分析法，属于自顶向下确定性语法分析方法。要求文法是LL(1)文法。

3. 比较LL(1)分析法和递归下降子程序法的异同。
答： 相同点：都要求文法是LL(1)文法；都是自顶向下的分析方法；都通过分析下个字符来判断该进入哪个状态或者调用哪个函数。
不同点：LL(1)分析法先建立起预测分析表，通过对分析栈的不断操作(出栈，入栈)来进行;递归下降子程序法是通过函数间的函数调用来实现不同状态间的转换，并简化了代码。

4. 什么是语法制导翻译技术？其核心技术是什么？
答：语法制导翻译是在语法分析过程中，随着分析(推导或归约)的逐步进展，每识别出一个语法结构，根据文法的每个规则所对应的语义子程序进行翻译的方法；核心技术是构造属性翻译文法。

5. 表达式的四元式属性翻译文法如何设计？
答： 假定：SEM(m)-- 语义栈(属性传递、赋值场所)；
QT[q] – 四元式区；
G``(E)：E -> T | E+T{GEQ(+)} | E-T{GEQ(-)} T -> F | T*F{GEQ(*)} | T/F{GEQ(/)}
F -> i{PUSH(i)} | ( E )
其中：
⑴ PUSH(i)– 压栈函数(把当前 i 压入语义栈)；
⑵ GEQ(w) – 表达式四元式生成函数:
生成一个四元式送QT[q]过程：
① t := NEWT; { 申请临时变量函数；}
② SEND(w,SEM[m-1],SEM[m],t)
③ POP;POP;PUSH(t)