词法分析与语法分析程序设计.doc
《词法分析与语法分析程序设计.doc》由会员分享，可在线阅读，更多相关《词法分析与语法分析程序设计.doc（54页珍藏版）》请在冰点文库上搜索。
l实验三词法分析与语法分析程序设计
一．实验目的
基本掌握计算机语言的词法分析程序和语法分析程序的设计方法。
二．实验要求、内容及步骤
实验要求：
1.根据以下的正规式，画出状态图；
标识符：
<字母>（<字母>|<数字字符>）*
关键字：
ifthenelsewhiledo
十进制整数：
0|（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*
运算符和分隔符：
+-*/><=（）。
2.根据状态图，设计词法分析函数intscan（），从键盘读入数据，分析出一个单词。
3.对于只含有+、*运算的算术表达式的如下文法，编写相应的语法分析程序，要求用LL
（1）分析表实现，并以id+id*id为例进行测试：
E—＞TE′
E′—＞+TE′|ε
T—＞FT′
T′—＞*FT′|ε
F—＞（E）|id
实验步骤：
1.根据状态图，设计词法分析算法；
2.采用C++语言，实现该算法；
3.调试程序：
输入一组单词，检查输出结果；
4.编制给定文法的非递归的预测分析程序，并加以测试。
三．实验设备
计算机、Windows操作系统、VisualC++程序集成环境。
四．实验原理
1.词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序列。
产生下述小语言的单词序列。
这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：
单词符号
种别编码
助记符
内码值
DIM
IF
DO
STOP
END
标识符
常数（整）
=
+
*
**
，
（
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
$DIM
$IF
$DO
$STOP
$END
$ID
$INT
$ASSIGN
$PLUS
$STAR
$POWER
$COMMA
$LPAR
$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|F
F→P^F|P
p→（E）|i
使用的算法可以是：
预测分析法；递归下降分析法；算符优先分析法；LR分析法等。
分析表格式：
id
+
*
（
）
$
E
E—＞TE′
E—＞TE′
E′
E′—＞+TE′
E′—＞ε
E′—＞ε
T
T—＞FT′
T—＞FT′
T′
T′—＞ε
T′—＞*FT′
T′—＞ε
T′—＞ε
F
F—＞id
F—＞（E）
3.中间代码生成器产生上述算术表达式的中间代码（四元式序列）。
五．实验代码及结果
词法分析代码：
#include
#include
usingnamespacestd;
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'））
{
sum=sum*10+ch-'0';
ch=prog[p++];
}
}
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=='*'）
{
syn=11+15;
token[m++]=ch;
}
else
{
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=='='）
{
syn=16+15;
token[m++]=ch;
}
else
{
syn=15+15;
p--;
}
break;
case'>':
m=0;token[m++]=ch;
ch=prog[p++];
if（ch=='='）
{
syn=19+15;
token[m++]=ch;
}
else
{
syn=18+15;
p--;
}
break;
case':
':
m=0;token[m++]=ch;
ch=prog[p++];
if（ch=='='）
{
syn=21+15;
token[m++]=ch;
}
else
{
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<<"种别编码自身值"< do
{
scaner（）;
switch（syn）
{
case22:
cout<<"（"< case-1:
cout<<"Errorinrow"<"<default:
cout<<"（"< }
}
while（syn!
=0）;
}
词法分析结果：
语法分析代码：
#include
#include
#include
usingnamespacestd;
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）
{
p=s->next;
v=p->data;
s->next=p->next;
}
free（p）;
}
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）;//上托栈顶符号放入X
poplink（st）;
for（intk=0;k<14+j;k++）//打印对齐格式
printf（"%c",''）;
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）
{
printf（"%8c是该文法的句子！
\n",''）;
}
else
error（）;
}
else
{
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（"对任意输入LL
（1）文法的分析表，判断验证字符串是否为该文法的句子\n"）;
printf（"并能给出分析和演示过程。
\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（"请输入非终结符个数:
\n"）;
scanf（"%d",&n）;
getchar（）;
for（i=0;i{
printf（"请输入非终结符Vn[%d]:
\n",i）;
scanf（"%c",&Vn[i]）;
getchar（）;
printf（"请输入此非终结符对应各终结符的产生式右部（null或NULL表示出错;$表示空串）:
\n"）;
for（k=0;k<=r;k++）
{
scanf（"%s",M[i][k].m）;
getchar（）;
}
}
opt3:
printf（"请输入要分析的字符串，且以#结束:
\n"）;
analyse（Vn,Vt）;
printf（"请选择\n"）;
printf（"1:
输入字符串\n"）;
printf（"2:
输入新分析表\n"）;
printf（"0:
退出\n"）;
opt4:
cin>>select;
switch（select）
{
case'1':
{gotoopt3;break;}
case'2':
{gotoopt2;}
case'0':
{break;}
default:
{printf（"输入错误!
请重新选择:
"）;
gotoopt4;
break;}
}
return0;
}
语法分析结果：
六．实验小结
通过实验了解到了词法分析和语法分析二者的不同：
1.词法规则通常非常简单，不必动用强大的文法来描述；
2.对于词法记号，正规式比上下文无关文法提供了更简洁且易于理解的定义；
3.从正规式可以自动的构造出有效的词法分析器，从任何文法都很难构造词法分析器；
4.把语言的语法结构分成词法和非词法两部分为编译器前端的模块划分提供了方便的途径。
一、目的
<<编译技术>>是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。
从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。
二、任务及要求
基本要求：
1．词法分析器产生下述小语言的单词序列
这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：
单词符号
种别编码
助记符
内码值
升级会员 