《编译原理》实验指导书.docx
《《编译原理》实验指导书.docx》由会员分享，可在线阅读，更多相关《《编译原理》实验指导书.docx（28页珍藏版）》请在冰点文库上搜索。
《编译原理》实验指导书
武汉科技大学
计算机科学与技术学院
编译原理实验指导书
实验一词法分析器设计
【实验目的】
1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。
2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。
3．通过完成词法分析程序，了解词法分析的过程。
【实验内容】
用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。
【实验步骤和要求】
1．要求绘出词法分析过程的流程图。
2．根据词法分析的目的以及内容，确定完成分析过程所需模块。
3．写出每个模块的源代码，必要的部分要写明注释。
4．整理程序清单及所得结果。
【说明】
运行成功以后，检查程序，实验报告要求分组完成个功能子程序的打印。
辅助库函数scanerLib设计以及使用说明：
下面内容给出了一个辅助库函数的接口说明以及具体实现。
接口设计
//字符类
classToken
{
TokenTypetype;
Stringstr;
Intline;
}
//词法分析结果输出操作类
classTokenWriter
{
ArrayListtokens;//用来记录所识别出来的token
TokenWriter（）;//构造函数指定输入文件名，创建文件输出流
VoidAdd（Token）;//将词法分析器中分析得到的Token添加到tokens中
WriteXML（）;//将tokens写出到目标文件.xml中
}
//词法分析操作词法分析生成文件接口<暂时不需要对该类的操作；下一步做语法分析的时候使用>
classTokenReader
{
ArrayListtokens;
TokenReader（）;//构造函数输入文件名；初始化
TokenNext（）;//返回下一个Token；
TokenBack（）;//回退一个Token，并返回回退后的当前Token
ReadXML（）;//从文件中读出所有Token到tokens
}
使用：
TokenWritertw=newTokenWriter（）;
While（）{
Tokentok=getToken（）;
Tw.Add（tok）;
}
tw.WriteXML（）;
TokenReadertr=newTokenReader（）;
Tok,ReadXML（）;
Tokentok=newToken（）;
While（）{
Tok=tr.Next（）;
Process（tok）;
}
类图：
TokenWriter
-tokens:
ArrayList
-scanfile:
string
+TokenWriter（string）
+Add（Token）:
void
+WriteXML（）:
void
TokenReader
-tokens:
ArrayList
-scanfile:
string
-pos:
int
+TokenWriter（string）
+Next（）:
Token
+Back（）:
Token
+WriteXML（）:
void
操作类库源码
Token.cs//字符类
ReservedWord.cs//保留字类
TokenWriter.cs//结果输出
TokenReader.cs//操作词法分析生成文件，进行下一步的工作
使用时注意事项：
1）定义文法中涉及到的所有字符类型，修改Token.cs文件中
publicenumTokenType
{
//自己定义的所有字符类型
};
2）对于保留字，在词法分析的过程中进行定义，例如：
HashtablereservedWords=newHashtable（）;
reservedWords.Add（"if",TokenType.IF）;
reservedWords.Add（"else",TokenType.ELSE）;
reservedWords.Add（"while",TokenType.WHILE）;
reservedWords.Add（"return",TokenType.RETURN）;
reservedWords.Add（"void",TokenType.VOID）;
reservedWords.Add（"int",TokenType.INT）;
可以继续添加其它的保留字；也可以讲保留字表定义为其它的类型结构进行存储。
3）进行词法分析，词法分析的过程中，可以使用Token、ReservedWord的类型定义以及TokenWriter类中给出的接口函数进行操作。
4）同时还给出了一个较复杂的语言文法的词法分析程序scanner.cs。
示例程序举例：
设置输入：
prime.cm
输出：
prime.xml
实验二LL
（1）语法分析程序设计
【实验目的】
1．熟悉判断LL
（1）文法的方法及对某一输入串的分析过程。
2．学会构造表达式文法的预测分析表。
【实验内容】
编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。
【实验步骤和要求】
1．从键盘读入输入串，并判断正误；
2．若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL
（1）文法；
3．若符合LL
（1）文法，由程序自动构造LL
（1）分析表；
4．由算法判断输入符号串是否为该文法的句型。
（可参考教材96页的例题1）
【说明】
语法分析主要是将从词法分析那里得来的记号构成一棵语法树。
例：
SHMA#
adbe#
S->aH
H->aMd
H->d
M->Ab
M->
A->aM
A->e
分析例句：
aaabd#
/*-------------------LL
（1）语法分析--------------------*/
#include"stdio.h"
#include"stdlib.h"
#defineMaxRuleNum8
#defineMaxVnNum5
#defineMaxVtNum5
#defineMaxStackDepth20
#defineMaxPLength20
#defineMaxStLength50
structpRNode /*产生式右部结构*/
{
intrCursor; /*右部序号*/
structpRNode*next;
};
structpNode /*产生式结点结构*/
{
intlCursor; /*左部符号序号*/
intrLength; /*右部长度*/
/*注当rLength=1时，rCursor=-1为空产生式*/
structpRNode*rHead; /*右部结点头指针*/
};
charVn[MaxVnNum+1]; /*非终结符集*/
intvnNum;
charVt[MaxVtNum+1]; /*终结符集*/
intvtNum;
structpNodeP[MaxRuleNum]; /*产生式*/
intPNum; /*产生式实际个数*/
charbuffer[MaxPLength+1];
charch; /*符号或stringch;*/
charst[MaxStLength];/*要分析的符号串*/
structcollectNode /*集合元素结点结构*/
{
intnVt; /*在终结符集中的下标*/
structcollectNode*next;
};
structcollectNode*first[MaxVnNum+1]; /*first集*/
structcollectNode*follow[MaxVnNum+1]; /*follow集*/
intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];
/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#（-1）*/
intanalyseStack[MaxStackDepth+1]; /*分析栈*/
inttopAnalyse; /*分析栈顶*/
/*intreverseStack[MaxStackDepth+1]; /*颠倒顺序栈*/
/*inttopReverse; /*倒叙栈顶*/
voidInit（）;/*初始化*/
intIndexCh（charch）;
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
voidInputVt（）; /*输入终结符*/
voidInputVn（）;/*输入非终结符*/
voidShowChArray（char*collect,intnum）;/*输出Vn或Vt的内容*/
voidInputP（）;/*产生式输入*/
boolCheckP（char*st）;/*判断产生式正确性*/
voidFirst（intU）;/*计算first集,U->xx...*/
voidAddFirst（intU,intnCh）; /*加入first集*/
boolHaveEmpty（intnVn）;/*判断first集中是否有空（-1）*/
voidFollow（intV）;/*计算follow集*/
voidAddFollow（intV,intnCh,intkind）;/*加入follow集，
kind=0表加入follow集，kind=1加入first集*/
voidShowCollect（structcollectNode**collect）;/*输出first或follow集*/
voidFirstFollow（）;/*计算first和follow*/
voidCreateAT（）;/*构造预测分析表*/
voidShowAT（）;/*输出分析表*/
voidIdentify（char*st）;/*主控程序,为操作方便*/
/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/
voidInitStack（）;/*初始化栈及符号串*/
voidShowStack（）;/*显示符号栈中内容*/
voidPop（）;/*栈顶出栈*/
voidPush（intr）;/*使用产生式入栈操作*/
#include"LL1.h"
voidmain（void）
{
chartodo,ch;
Init（）;
InputVn（）;
InputVt（）;
InputP（）;
getchar（）;
FirstFollow（）;
printf（"所得first集为：
"）;
ShowCollect（first）;
printf（"所得follow集为：
"）;
ShowCollect（follow）;
CreateAT（）;
ShowAT（）;
todo='y';
while（'y'==todo）
{
printf（"\n是否继续进行句型分析？
（y/n）:
"）;
todo=getchar（）;
while（'y'!
=todo&&'n'!
=todo）
{
printf（"\n（y/n）?
"）;
todo=getchar（）;
}
if（'y'==todo）
{
inti;
InitStack（）;
printf（"请输入符号串（以#结束）:
"）;
ch=getchar（）;
i=0;
while（'#'!
=ch&&i {
if（''!
=ch&&'\n'!
=ch）
{
st[i++]=ch;
}
ch=getchar（）;
}
if（'#'==ch&&i {
st[i]=ch;
Identify（st）;
}
else
printf（"输入出错！
\n"）;
}
}
getchar（）;
}
voidInit（）
{
inti,j;
vnNum=0;
vtNum=0;
PNum=0;
for（i=0;i<=MaxVnNum;i++）
Vn[i]='\0';
for（i=0;i<=MaxVtNum;i++）
Vt[i]='\0';
for（i=0;i {
P[i].lCursor=NULL;
P[i].rHead=NULL;
P[i].rLength=0;
}
PNum=0;
for（i=0;i<=MaxPLength;i++）
buffer[i]='\0';
for（i=0;i {
first[i]=NULL;
follow[i]=NULL;
}
for（i=0;i<=MaxVnNum;i++）
{
for（j=0;j<=MaxVnNum+1;j++）
analyseTable[i][j]=-1;
}
}
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
intIndexCh（charch）
{
intn;
n=0; /*isVn?
*/
while（ch!
=Vn[n]&&'\0'!
=Vn[n]）
n++;
if（'\0'!
=Vn[n]）
return100+n;
n=0; /*isVt?
*/
while（ch!
=Vt[n]&&'\0'!
=Vt[n]）
n++;
if（'\0'!
=Vt[n]）
returnn;
return-1;
}
/*输出Vn或Vt的内容*/
voidShowChArray（char*collect）
{
intk=0;
while（'\0'!
=collect[k]）
{
printf（"%c",collect[k++]）;
}
printf（"\n"）;
}
/*输入非终结符*/
voidInputVn（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的非终结符，注意：
"）;
printf（"请将开始符放在第一位，并以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n {
Vn[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n {
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vn[n++]=ch;
vnNum++;
}
ch=getchar（）;
}
Vn[n]='#'; /*以“#”标志结束用于判断长度是否合法*/
k=n; /*k用于记录n以便改Vn[n]='\0'*/
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
;
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vn[k]='\0';
ShowChArray（Vn）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*输入终结符*/
voidInputVt（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的终结符，注意：
"）;
printf（"以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n {
Vt[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n {
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vt[n++]=ch;
vtNum++;
}
ch=getchar（）;
}
Vt[n]='#'; /*以“#”标志结束*/
k=n; /*k用于记录n以便改Vt[n]='\0'*/
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vt[k]='\0';
ShowChArray（Vt）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*产生式输入*/
voidInputP（）
{
charch;
inti=0,n,num;
printf（"请输入文法产生式的个数：
"）;
scanf（"%d",&num）;
PNum=num;
getchar（）; /*消除回车符*/
printf（"\n请输入文法的%d个产生式,并以回车分隔每个产生式：
",num）;
printf（"\n"）;
while（i {
printf（"第%d个：
",i）;
/*初始化*/
for（n=0;n buffer[n]='\0';
/*输入产生式串*/
ch='';
n=0;
while（'\n'!
=（ch=getchar（））&&n {
if（''!
=ch）
buffer[n++]=ch;
}
buffer[n]='\0';
/* printf（"%s",buffer）;*/
if（CheckP（buffer））
{
/*填写入产生式结构体*/
pRNode*pt,*qt;
P[i].lCursor=IndexCh（buffer[0]）;
pt=（pRNode*）malloc（sizeof（pRNode））;
pt->rCursor=IndexCh（buffer[3]）;
pt->next=NULL;
P[i].rHead=pt;
n=4;
while（'\0'!
=buffer[n]）
{
qt=（pRNode*）malloc（sizeof（pRNode））;
qt->rCursor=IndexCh（buffer[n]）;
qt->next=NULL;
pt->next=qt;
pt=qt;
n++;
}
P[i].rLength=n-3;
i++;
/*调试时使用*/
}
else
printf（"输入符号含非法在成分，请重新输入！
\n"）;
}
}
/*判断产生式正确性*/
boolCheckP（char*st）
{
intn;
if（100>IndexCh（st[0]））
returnfalse;
if（'-'!
=st[1]）
returnfalse;
if（'>'!
=st[2]）
returnfalse;
for（n=3;'\0'!
=st[n];n++）
{
if（-1==IndexCh（st[n]））
returnfalse;
}
returntrue;
}
/*====================first&follow======================*/
/*计算first集,U->xx...*/
voidFirst（intU）
{
inti,j;
for（i=0;i {
if（P[i].lCursor==U）
{
stru
升级会员 