编译原理词法分析器语法分析器实验报告.docx
《编译原理词法分析器语法分析器实验报告.docx》由会员分享，可在线阅读，更多相关《编译原理词法分析器语法分析器实验报告.docx（21页珍藏版）》请在冰点文库上搜索。
编译技术
班
级
网络 0802
学
号3080610052
姓名
叶晨舟
指导老师 朱 玉 全
2011年7 月4日
一、目的
编译技术是理论与实践并重的课程， 而其实验课要综合运用一、 二年级所学的多门课程
的内容，用来完成一个小型编译程序。
从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。
二、任务及要求
基本要求：
1.词法分析器 产生下述小语言的单词序列
这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：
单词符号
种别编码
助记符
内码值
DIM
1
$DIM
-
IF
2
$IF
-
DO
3
$DO
-
STOP
4
$STOP
-
END
5
$END
-
标识符
6
$ID
-
常数（整）
7
$INT
内部字符串
=
8
$ASSIGN
标准二进形式
+
9
$PLUS
-
*
10
$STAR
-
**
11
$POWER
-
，
12
$COMMA
-
（
13
$LPAR
-
）
14
$RPAR
-
对于这个小语言，有几点重要的限制：
首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。
所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。
例如，下面的写法是绝对禁止的：
IF （5）=x
其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。
也就是说，对于关键字不专设对应的转换图。
但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表） 。
当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。
再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。
例如，一个条件语句应写为
而绝对不要写成
IFi>0i=1;
IFi>0i=1;
因为对于后者，我们的分析器将无条件地将 IFI 看成一个标识符。
这个小语言的单词符号的状态转换图，如下图：
2.语法分析器能识别由加+减-乘*除/乘方^括号（）操作数所组成的算术表达式，其文法如下：
E→E+T|E-T|T
T→T*F|T/F|FF→P^F|Pp→（E）|i
使用的算法可以是：
预测分析法；递归下降分析法；算符优先分析法；
LR分析法等。
3.中间代码生成器 产生上述算术表达式的中间代码（四元式序列）
三、实现过程
给出各题目的详细算法描述，数据结构和函数说明，流程图。
开始
输入源文
件路径
否
路径是否有
效
是
打开源文件
初始化文件指针
识别指针内容
文件结束？
是
结束
否
是空格，空白或换
行吗
否
是字母吗
否
是数字吗
否
是界符吗
将字符加入字符数
否
组Word[]
是
是
是
跳过该字符
将字符加入字符数
组Word[]
将字符加
入字符数组Word[]
将字符
加入字符数组Word[]
指向下一字符
指向下一字符
是
将字符
加入字符数组
Word[]
指向下一字符
是
是字母惑数字
吗
识别指针内容
输出word
为界符
输出Word
内容为不可识别
回退
否
是数字吗
将word与关键
字表key进行匹配
否
输出word为
普通标示符
否
匹配？
输出word
为常数
指向下一字符
是
输出word
为关键字
1、词法分析器的流程图
2、语法分析器主程序图
3、中间代码生成器流程图：
四、源程序
词法分析器:
#include#include
#includeusingnamespacestd;typedefstructtable
{
//分析表存储结构
charm[100];
}table;
tableM[100][100]; //定义分析表
typedefstructstacknode //定义栈内元素节点 （带头结点（为空）的 ）
{
chardata;
structstacknode*next;
}stackk;
voidinitlink（stackk*&s）
{
//初始化新栈
s=（stackk*）malloc（sizeof（stackk））;s->next=NULL;
}
voidpoplink（stackk*&s）
{
stackk*p;charv;
if（s->next!
=NULL）
{
//顶元素出栈
}
free（p）;
}
p=s->next;v=p->data;
s->next=p->next;
voidpushlink（stackk*&s,charx） //新元素入栈
{
stackk*p;
p=（stackk*）malloc（sizeof（stackk））;p->data=x;
p->next=s->next;s->next=p;
}
voiddisplay（stackk*s）
{
//打印 现实显示 栈内元素
stackk*p;inti=0,j;charst[100];p=s->next;
while（p!
=NULL）
{
st[i++]=p->data;p=p->next;
}
for（j=i-1;j>=0;j--）
printf（"%c",st[j]）;
for（j=0;j<16-i;j++） //打印对齐格式
printf（"%c",''）;
}
chargettop（stackk*s）
{
//返回栈顶元素值
if（s->next==NULL）return0;
else
returns->next->data;
}
intfind（charc,chararray[]）
{
inti;
intflag=0;for（i=0;i<100;i++）
{
if（c==array[i]）flag=1;
//查找函数，
}
returnflag;
}
intlocation（charc,chararray[]）// 定位函数,指出字符所在位置
{
inti;
for（i=0;i<100;i++）
{
if（c==array[i]）
returni;
}
}
voiderror（）
{
//出错函数定义
printf（"%15c 出错!
\n",''）;
}
voidanalyse（charVn[],charVt[]）
{
inti,j,m,p,q,length,t,h;charw,X;
charstr[100];opt0:
scanf（"%s",str）;for（i=0;i{
if（!
find（str[i],Vt））
{
printf（"输入字符串有误 !
请重新输入!
"）;gotoopt0;
break;
}
}
stackk*st;initlink（st）;pushlink（st,'#'）;
pushlink（st,Vn[0]）; //#与识别符号入栈j=0;
h=1;
w=str[0];
printf（"步骤%-12c分析栈%-24c剩余输入串%-12c所用产生式\n",'','',''）;opt1:
printf（"%-16d",h）; //显示步骤
h++;
display（st）;X=gettop（st）;poplink（st）;
for（intk=0;k<14+j;k++）
printf（"%c",''）;
//显示分析栈中内容
//上托栈顶符号放入 X
//打印对齐格式
for（t=j;t{
printf（"%c",str[t]）; //显示剩余字符串
}
if（find（X,Vt）&&X!
='#'） //分析栈的栈顶元素和剩余输入串的第一个元素相比较
{
if（X==w）
{
printf（"%15c匹配\n",X）;j++;
w=str[j];gotoopt1;
}
else
error（）;
}
else
{
if（X=='#'）
{
if（X==w）
{
}
else
{
}
else
printf（"%8c是该文法的句子！
\n",''）;
error（）;
p=location（X,Vn）;q=location（w,Vt）;
char*S1="null",*S2="NULL";if（strcmp（M[p][q].m,S1）==0||strcmp（M[p][q].m,S2）==0）// 查找产生式
error（）;
else
{
charstr0[100];strcpy（str0,M[p][q].m）;
printf（"%15c-->%s\n",X,str0）; //显示对应的产生式
if（strcmp（str0,"$"）==0）gotoopt1;
else
{
length=strlen（str0）; //逆序进栈for（m=length-1;m>=0;m--）
{
pushlink（st,str0[m]）;
}
gotoopt1;
}
}
}
}
}
intmain（）
{
inti,k,n,r;
charVn[100],Vt[100],select;
printf（"******************************************************************\n"）;
printf（"printf（"
对任意输入LL
（1）文法的分析表，判断验证字符串是否为该文法的句子并能给出分析和演示过程。
\n"）;
\n"）;
printf（"******************************************************************\n"）;opt2:
printf（"请输入各终结符（ #号表示结束 ）Vt[i]:
\n"）;
for（i=0;i<100;i++）
{
scanf（"%c",&Vt[i]）;
if（Vt[i]=='#'）
{
r=i;break;
}
}
printf（"请输入非终结符个数
scanf（"%d",&n）;getchar（）;
:
\n"）;
for（i=0;i{
printf（"请输入非终结符 Vn[%d]:
\n",i）;
scanf（"%c",&Vn[i]）;getchar（）;
printf（"请输入此非终结符对应各终结符的产生式右部 （null或NULL表示出错;$表示空串）:
\n"）;
for（k=0;k<=r;k++）
{
}
}
opt3:
scanf（"%s",M[i][k].m）;getchar（）;
opt4:
{
}
}
printf（"请输入要分析的字符串，且以 #结束:
\n"）;analyse（Vn,Vt）;
printf（"******************** 请选择***********************\n"）;
printf（" 1:
输入字符串 \n"）;
printf（" 2:
输入新分析表 \n"）;
printf（" 0:
退出 \n"）;printf（"*************************************************\n"）;
cin>>select;switch（select）
case'1':
{gotoopt3;break;}case'2':
{gotoopt2;}
case'0':
{break;}
default:
{printf（" 输入错误!
请重新选择:
"）;
gotoopt4;break;}
return0;
运行结果：
语法分析器 源程序：
#include#includeusingnamespacestd;charprog[100],token[10];charch;
intsyn,p,m=0,n,row,sum=0;
char*rwtab[20]={"dim","if","do","stop","end","and","begin","bool","case","char",
"false","for","int","not","or","set","then","true","until","while"
};
voidscaner（）
{
for（n=0;n<9;n++）token[n]=NULL;ch=prog[p++];
while（ch==''）
{
ch=prog[p];p++;
}
if（（ch>='a'&&ch<='z'）||（ch>='A'&&ch<='Z'））
{
m=0;
while（（ch>='0'&&ch<='9'）||（ch>='a'&&ch<='z'）||（ch>='A'&&ch<='Z'））
{
token[m++]=ch;ch=prog[p++];
}
token[m++]='\0';p--;
syn=21;for（n=0;n<20;n++）
{
if（strcmp（token,rwtab[n]）==0）
{
syn=n+1;break;
}
}
}
elseif（（ch>='0'&&ch<='9'））
{
{
sum=0;while（（ch>='0'&&ch<='9'））
{
}
}
p--;
sum=sum*10+ch-'0';ch=prog[p++];
syn=7+15;if（sum>32767）
syn=-1;
}
elseswitch（ch）
{
case'=':
syn=8+15;token[0]=ch;break;case'+':
syn=9+15;token[0]=ch;break;case'*':
m=0;
token[m++]=ch;ch=prog[p++];if（ch=='*'）
{
}
else
{
}
syn=11+15;token[m++]=ch;
syn=10+15;p--;
break;
case',':
syn=12+15;token[0]=ch;break;case'（':
syn=13+15;token[0]=ch;break;case'）':
syn=14+15;token[0]=ch;break;case'#':
syn=0;token[0]=ch;break;case'<':
m=0;token[m++]=ch;
ch=prog[p++];if（ch=='>'）
{
syn=17+15;token[m++]=ch;
}
elseif（ch=='='）
{
}
else
{
}
syn=16+15;token[m++]=ch;
syn=15+15;p--;
break;case'>':
m=0;token[m++]=ch;
ch=prog[p++];if（ch=='='）
{
}
else
{
syn=19+15;token[m++]=ch;
syn=18+15;p--;
}
break;case':
':
m=0;token[m++]=ch;
ch=prog[p++];if（ch=='='）
{
}
else
{
}
syn=21+15;token[m++]=ch;
syn=20+15;p--;
break;case'/':
syn=22+15;token[0]=ch;break;case'-':
syn=23+15;token[0]=ch;break;case';':
syn=24+15;token[0]=ch;break;default:
syn=-1;break;
}
}
voidmain（）
{
p=0;
row=1;cout<cout<<"*************************** 小 型 词 法 分 析 器
**********************************"<cout<<"请输入一段程序（以 #结束）:
";do
{
cin.get（ch）;prog[p++]=ch;
}
while（ch!
='#'）;
p=0;
cout<*********************************"<cout<<" 种别编码 自身值"<{
scaner（）;
switch（syn）
{
case22 :
cout<<" （"<"<break;
case-1:
cout<<" Errorinrow"<"<default:
cout<<" （"<"<}
}
while（syn!
=0）;
}
运行结果：
}
中间代码生成器源程序 ：
表达式生成四元式递归子程序法
#include#includeusingnamespacestd;
#defineDEFAULT_SIZE100
charEMachine（charw）; //表达式E的自动机charTMachine（charw）; //表达式T的自动机charFMachine（charw）; //表达式F的自动机boolZMachine（）; //表达式Z的自动机stringintToString（inta）; //整形变成字符串形函数
classstack //栈类定义
{
private:
inttop;
string*stacka;intmaxsize;
public:
stack（intsize=DEFAULT_SIZE）;
~stack（）{delete[]stacka;}voidpush（conststring&item）;stringpop（void）;
stringgettop（void）const;
boolempty（void）const{return（top==-1）;}
boolfull（void）const{return（top==maxsize-1）;}voidclear（void）{top=-1;}
};
stack:
:
stack（intsize）
{
//栈类的构造函数
top=-1;maxsize=size;
stacka=newstring[maxsize];
if（!
stacka）
{
cerr<<"allocatememoryfailed."<exit
（1）;
}
}
voidstack:
:
push（conststring&item）
{
//压栈操作
if（full（））
{
cerr<<"stackfull,cannotpush."<}
top++;
stacka[top]=item;
}
stringstack:
:
pop（void）
{
//出栈操作
if（empty（））
{
cerr<<"stackempty,cannotpop."<（1）;
}
stringitem=stacka[top];top--;
returnitem;
}
stringstack:
:
gettop（void）const{
if（empty（））
{
//取栈顶操作
cerr<<"stackempty,cannotgettop."<exit
（1）;
}
returnstacka[top];
}
staticstackwordStack; //符号栈
staticintnoOfQuet=0; //静态四元式个数记录
staticintnoOfT=1; //静态状态个数记录
voidmain（）{ //主函数
charyesOrNo; //
升级会员 