编译原理报告(6) 本文关键词：编译，原理，报告
编译原理报告(6) 本文简介：华中科技大学计算机学院编译原理实验报告课程实验报告课程名称：《编译原理》专业班级：信息安全1302学号：姓名：指导教师：报告日期：2015年11月07日计算机科学与技术学院目录目录21实验一词法分析31.1实验目的31.2实验要求31.3算法思想41.4实验程序设计说明61.5词法分析实现61.6词
编译原理报告(6) 本文内容：
华中科技大学计算机学院
编译原理实验报告
课
程
实
验
报
告
课程名称：
《编译原理》
专业班级：
信息安全1302
学
号：
姓
名：
指导教师：
报告日期：
2015年11月07日
计算机科学与技术学院
目录
目录2
1
实验一
词法分析3
1.1实验目的3
1.2实验要求3
1.3算法思想4
1.4实验程序设计说明6
1.5词法分析实现6
1.6词法实验结果及结果分析12
2
实验二
语法分析13
2.1
实验目的13
2.2
实验要求13
2.3
算法思想14
2.4
实验程序设计说明16
2.5
语法分析实现16
2.6
词法实验结果及结果分析31
3
实验中遇到的问题及解决32
参考资料32
1
实验一
词法分析
1.1
实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
1.2
实验要求
1、待分析的简单的词法
（1）关键字：
begin
if
then
while
do
end
所有的关键字都是小写。
（2）运算符和界符
：
=
+
-
/
>
>=
=
;
(
)
#
（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：
ID
=
letter
(letter
|
digit)*
NUM
=
digit
digit*
（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。
2、
各种单词符号对应的种别码：
表1
各种单词符号对应的种别码
单词符号
种别码
单词符号
种别码
bgin
1
：
17
If
2
：=
18
Then
3
21
do
5
23
lettet（letter|digit）*
10
>=
24
dight
dight*
11
=
25
+
13
；
26
—
14
(
27
15
)
28
/
16
#
0
3、
词法分析程序的功能：
输入：所给文法的源程序字符串。
输出：二元组（syn,token或sum）构成的序列。
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整型常数。
例如：对源程序begin
x:=9:
if
x>9
then
x:=2*x+1/3;
end
#的源文件，经过词法分析后输出如下序列：
(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)……
1.3
算法思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
1、
主程序示意图：
主程序示意图如图1所示。其中初始包括以下两个方面：
⑴
关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：
Charrwtab[6]
=
{“begin”,“if”,“then”,“while”,“do”,“end”,};
开始
置初值
调用扫描子程序
输出单词二元组
输入串结束?
否
结束
是
图1
主程序示意图
（2）程序中需要用到的主要变量为syn,token和sum
2、
扫描子程序的算法思想：
首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图2所示。
开始
变量初始化
忽略空格
是否文件结束?
否
返回
是
拼数
拼字符串
字母
Syn=11
关键字?
Syn=10
否
是
Syn为对应关键字的种别码
对不同符给出相应的syn值
报错
其他符号
运算符界符等
返回
数字
图2
扫描子程序流程图
1.4
实验程序设计说明
1、数据结构的设计
先来看看WORD结构的设计：
typedef
struct
{
int
typenum;//用于存储该字符串的种别码；
charword;
//用于存储字符串；
}
这个词法分析中，我们要将我们识别到的字符串输出他们，而且还要将他们的相应的种别码输出，因此我们得用一个结构体来将这两个属性放在一个结构体中。
2、算法的设计
首先将输入端的字符串读入然后进行前期的处理，如去掉空白符号。之后在一个字符一个字符的进行处理，判断下一个字符串所属类型，然后给出相应类型的种别码，返回给主函数进行输出。其中主要部分就是分类属性的判断以及判断之后不同属性种别码的赋值，这就是整个程序中的主要部分。
1.5
词法分析实现
#include
#include
#include
#include
#define
_KEY_WORD_END
“waiting
for
your
expanding“/*定义关键字结束标志*/
HANDLE
gh_std_out;
//标准输出设备句柄
typedef
struct
/*单词二元组的结构，可以根据需要继续扩充*/
{
int
typenum;
char
word;
}
WORDS;
char
input[255];
/*输入缓冲区*/
char
token[255]=““;/*单词缓冲区*/
int
p_input;/*输入缓冲区指针*/
int
p_token;/*单词缓冲区指针*/
char
ch;
/*当前读入字符*/
char*
KEY_WORDS[]={“begin“,“if“,“then“,“while“,“do“,“end“,_KEY_WORD_END};/*可扩充的关键字数组*/
WORDS*
scaner();/*词法扫描函数，获得一个单词*/
int
main()
{
int
over=1;
WORDS*
oneword=new
WORDS;
printf(“Enter
Your
words(end
with
#):/n“);
scanf(“%[^#]s“,input);/*读入源程序字符串到缓冲区，以#结束，允许多行输入*/
getchar();
p_input=0;
printf(“Your
words:/n%s/n“,input);
printf(“The
sequence
as
follow:/n(
字符/t,种别码
)/n“);
while(overtypenumword);
printf(“/t,%5d
)/n“,oneword->typenum);/*打印种别码和单词自身的值*/
}
over=oneword->typenum;
}
return
0;
}
/**************需要用到的自编函数参考实现从输入缓冲区读取一个字符到ch中*************************/
char
m_getch(){
ch=input[p_input];
p_input=p_input+1;
return
(ch);
}
/**************去掉空白符*************/
void
getbc(){
while(ch==
||ch==10){
ch=input[p_input];
p_input=p_input+1;
}
}
/**************拼接单词*************/
void
concat(){
token[p_token]=ch;
p_token=p_token+1;
token[p_token]=
/0
;
}
/**************判断是否为字母*************/
int
letter(){
if(ch>=
a
myword->word=““;
p_token=0;
m_getch();
getbc();
if(letter()){
while(letter()||digit()){
concat();
m_getch();
}
retract();
myword->typenum=reserve();
myword->word=token;
return(myword);
}
else
if(digit()){
while(digit()){
concat();
m_getch();
}
retract();
myword->typenum=11;
myword->word=token;
return(myword);
}
else
switch(ch){
case
=
:
m_getch();
if
(ch==
=
){
myword->typenum=39;
myword->word=“==“;
return(myword);
}
retract();
myword->typenum=21;
myword->word=“=“;
return(myword);
break;
case
+
:myword->typenum=13;
myword->word=“+“;
return(myword);
break;
case
-
:myword->typenum=14;
myword->word=“-“;
return(myword);
break;
case
:myword->typenum=15;
myword->word=“*“;
return(myword);
break;
case
/
:myword->typenum=16;
myword->word=“/“;
return(myword);
break;
case
(
:myword->typenum=27;
myword->word=“(“;
return(myword);
break;
case
)
:myword->typenum=28;
myword->word=“)“;
return(myword);
break;
case
[
:myword->typenum=29;
myword->word=“[“;
return(myword);
break;
case
]
:myword->typenum=30;
myword->word=“]“;
return(myword);
break;
case
{
:myword->typenum=31;
myword->word=“{“;
return(myword);
break;
case
}
:myword->typenum=32;
myword->word=“}“;
return(myword);
break;
case,:myword->typenum=33;
myword->word=“,“;
return(myword);
break;
case
:
:m_getch();
if
(ch==
=
){
myword->typenum=18;
myword->word=“:=“;
return(myword);
}
retract();
myword->typenum=17;
myword->word=“:“;
return(myword);
break;
case
;
:myword->typenum=26;
myword->word=“;“;
return(myword);
break;
case
>
:
m_getch();
if
(ch==
=
){
myword->typenum=24;
myword->word=“>=“;
return(myword);
}
retract();
myword->typenum=23;
myword->word=“>“;
return(myword);
break;
case
typenum=22;
myword->word=“typenum=20;
myword->word=“typenum=21;
myword->word=“!=“;
return(myword);
}
retract();
myword->typenum=-1;
myword->word=“ERROR“;
return(myword);
break;
case
/0
:myword->typenum=1000;
myword->word=“OVER“;
return(myword);
break;
default:myword->typenum=-1;
myword->word=“ERROR“;
return(myword);
}
1.6
词法实验结果及结果分析
输入begin
x:=9:
if
x>9
then
x:=2*x+1/3;
end
#
程序输出序列的结果如下图3所示：
图3
程序运行结果
2
实验二
语法分析
2.1
实验目的
编写语法分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。
2.2
实验要求
利用C语言编写词法分析程序，并对语言进行语法分析。
2.2.1、待分析的简单语言的语法
用扩充的BNF表示如下：
（1）
::=beginend
（2）
::={；语句}
（3）
::=
（4）
::=ID:=
（5）
::={+|-}
（6）
::={*|/}
（7）
::=ID|NUM|()
2.2.2、实验要求说明
输入单词串，以“#”结束，如果文法是正确的句子，则输出成功信息，打印“success”，否则输出“error”并给出相应的错误提示。
例如：
输入
begin
a:=9;x:=2*3;b:=a+x;end#
输出
success
输入
x:=a+b*c;end#
输出
error
缺少begin
2.3
算法思想
2.3.1
主程序流程图如下：
2.3.2
语句串分析示意图：
2.3.3
语句分析函数judge流程图：
2.4
实验程序设计说明
程序中定义了一个结构变量如下：
typedef
struct
DisplayTable
{
int
Index;
//标识符所在表的下标
int
type;
//标识符的类型
int
line;
//标识符所在表的行数
char
symbol[20];//标识符所在表的名称
}Table;
Tabletable
=
new
Table[Max];
表table用来存放经词法分析后的结果的信息，包含单词的值、单词的类型嘛、单词所在源程序的行数，以及分析后单词在表中的下标。
另外还使用到几张关键字表、运算符表、界符表如下：
//关键字
const
char*
const
KeyWord[MaxKeyWord]
=
{“and“,“array“,“begin“,“case“,“char“,“constant“,“do“,“else“,“end“,“false“,“for“,“if“,“not“,“of“,“or“,“procedure“,“repeat“,“then“,“until“,“var“,“while“};
//
A类运算符
const
char
OptA[]
=
{
+,-,*,/,=,#,};
//B类运算符
const
charOptB[]
=
{“=“,“:=“,““};
//
界符
const
char
End[]
=
{
(,),,,;,.,[,],:,{,},“};
输入的源程序经过Scanner函数进行词法分析后，分析结果存放在table表中，然后再主函数中通过下标依次对table表中的单词进行句型判断等语法分析。
2.5
语法分析实现
语法分析器具体代码实现如下：
#include
#include
#include
#include
#include
#include
using
namespace
std;
#define
Max
655
//最大代码长度
#define
WordMaxNum
256
//变量最大个数
#define
DigitNum
256//常量最大个数
#define
MaxKeyWord21//关键字数量
#define
MaxOptANum
8//运算符最大个数
#define
MaxOptBNum
4//运算符最大个数
#define
MaxEndNum
11//界符最大个数
typedef
struct
DisplayTable
{
int
Index;
//标识符所在表的下标
int
type;//标识符的类型
int
line;//标识符所在表的行数
char
symbol[20];//标识符所在表的名称
}Table;
int
TableNum
=
0;
//display表的表项总数
char
Word[WordMaxNum][20];
//标识符表
char
Digit[WordMaxNum][20];
//数字表
int
WordNum
=
0;
//变量表的下标
int
DigNum
=
0;
//常量表的下标
bool
errorFlag
=
0;
//错误标志
int
TableIndex
=
-1;
//display
表的下标索引
int
beginCount
=
0;//遇到begin加1，遇到end减1
int
ifCount
=
0;
//遇到if加1
Tabletable
=
new
Table[Max];
//关键字
const
char*
const
KeyWord[MaxKeyWord]
=
{“and“,“array“,“begin“,“case“,“char“,“constant“,“do“,“else“,“end“,“false“,“for“,“if“,“not“,“of“,“or“,“procedure“,“repeat“,“then“,“until“,“var“,“while“};
//
A类运算符
const
char
OptA[]
=
{
+,-,*,/,=,#,};
//B类运算符
const
charOptB[]
=
{“=“,“:=“,““};
//
界符
const
char
End[]
=
{
(,),,,;,.,[,],:,{,},“};
void
error(char
str[20],int
nLine,int
errorType)
{
errorFlag
=
1;
cout
20)
//标识符超过规定长度，报错处理
{
error(str,nLine,1);
}
else
{
int
i;
for(i
=
0;i
=
MaxKeyWord)
//不是关键字
{
table[TableNum].Index
=
WordNum;
strcpy(Word[WordNum++],str);
table[TableNum].type
=
2;
//变量标识符
strcpy(table[TableNum].symbol,str);
table[TableNum].line
=
nLine;
TableNum
++;
}
}
}
/**************************常数**************************/
else
if(isdigit(ch[chIndex]))
//遇到数字
{
int
flag
=
0;
char
str[256];
int
strLen
=
0;
//数字和小数点
while(isdigit(ch[chIndex])
||
ch[chIndex]
==
.
)
{
//flag表记小数点的个数，0时为整数，1时为小数，2时出错
if(ch[chIndex]
==
.
)
flag
++;
str[strLen
++]
=
ch[chIndex];
chIndex
++;
}
str[strLen]
=
0;
if(strlen(str)
>
20)
//常量标识符超过规定长度20，报错处理
{
error(str,nLine,3);
}
if(flag
==
0)
{
table[TableNum].type
=
3;
//整数
}
if(flag
==
1)
{
table[TableNum].type
=
4;
//小数
}
if(flag
>
1)
{
error(str,nLine,2);
}
table[TableNum].Index
=
DigNum;
strcpy(Digit[DigNum
++],str);
strcpy(table[TableNum].symbol,str);
table[TableNum].line
=
nLine;
TableNum
++;
}
/*************************运算符************************/
else
{
//用来区分是不是无法识别的标识符，0为运算符，1为界符
int
errorFlag;
char
str[3];
str[0]
=
ch[chIndex];
str[1]
=
ch[chIndex
+
1];
str[2]
=
/0
;
int
i;
for(
i
=
0;i
=
MaxOptBNum)
{
for(
int
k
=
0;k
=
TableNum)
{
Gerror(14,TableIndex);
//出错信息：该语句缺少分号
return
1;
}
else
{
Gerror(5,TableIndex);
//出错信息：此处应为运算符
TableIndex
++;
}
}
}
/*******************赋值语句判断*************************/
bool
Assign()
//赋值语句的判断
{
TableIndex
++;
if(strcmp(
“:=“,table[TableIndex].symbol)
==
0)
{
TableIndex
++;
}
else
{
Gerror(1,TableIndex);
//出错信息：赋值号应该为“:=“TableIndex
++;
}
if(express())
//“:=“后可以为变量或常量
{
if(strcmp(“;“,table[TableIndex].symbol)
==
0)
{
return
1;
}
else
{
if(TableIndex
>=
TableNum)
{
Gerror(14,TableIndex);
//出错信息：该语句缺少分号
return
1;
}
else
if(table[TableIndex].line
!=
table[TableIndex
+
1].line)
{
Gerror(14,TableIndex);
//出错信息：该语句缺少分号
return
1;
//TableIndex
++;
}
}
}
else
{
Gerror(6,TableIndex);
//出错信息：“:=“后应为变量或常量
TableIndex
++;
}
return
0;
}
/**********************语句判断*************************/
bool
judge()
//条件、循环、初始化语句的判断
{
/**************************begin**********************/
if(strcmp(“begin“,table[TableIndex].symbol)==0)
//匹配begin
{
beginCount
++;
if(table[TableIndex
+
1].type
==
7)
{
TableIndex
++;
cout
<<
“第“<<
table[TableIndex].line
<<
“行,begin
后不能接
“< << endl; return 1; } } /**************************end***********************/ if(strcmp(“end“,table[TableIndex].symbol) == 0) //匹配end { beginCount --; if(TableIndex < TableNum) if(table[TableIndex+1].type==7||table[TableIndex+ 1].type == 8) { TableIndex ++; Gerror(12,TableIndex); return 1; } } /**************************else**********************/ if(strcmp(“else“,table[TableIndex].symbol) == 0) //匹配else { ifCount --; return 1; } /*********