编译原理报告(9) 本文关键词：编译，原理，报告
编译原理报告(9) 本文简介：课程设计报告课程名称：编译原理专业班级：信息安全1302班学号：姓名：指导教师：报告日期：2015年11月8日计算机科学与技术学院目录1实验一词法分析11.1实验目的11.2实验要求11.3实验原理11.4算法实现11.5测试结果12实验二语法分析12.1实验目的12.2实验要求12.3实验原理12
编译原理报告(9) 本文内容：
课
程
设
计
报
告
课程名称：
编译原理
专业班级：
信息安全
1302
班
学
号：
姓
名：
指导教师：
报告日期：
2015年11月8日
计算机科学与技术学院
目录
1实验一
词法分析1
1.1实验目的1
1.2实验要求1
1.3实验原理1
1.4算法实现1
1.5测试结果1
2实验二
语法分析1
2.1实验目的1
2.2实验要求1
2.3实验原理1
2.4算法实现1
I
1
实验一
词法分析
1.1
实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
1.2
实验要求
1.
待分析的简单语言的词法
(1)
关键字
begin
if
then
while
do
end
所有的关键字都是小写。
(2)
运算符和界符：
:=
+
-
/
>
>=
=
；
(
)
#
(3)
其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义：
ID
=
letter(letter
|
digit)*
NUM
=
digit
digit*
(4)
空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。
2.
各种单词符号对应的种别码。
单词符号
种别码
单词符号
种别码
begin
1
:
17
if
2
:=
18
then
3
21
do
5
23
letter
(letter
|
digit)*
10
>=
24
digit
digit*
11
=
25
+
13
;
26
-
14
(
27
15
)
28
/
16
#
0
3.
词法分析程序的功能
输入：所给文法的源程序字符串。
输出：二元组（syn,token
或
sum）构成的序列
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整形常数。
例如：对源程序
begin
x:=9;
if
x>0
then
x:=
2
x
+
1
/
3
;
end
#
的源文件，经词法分析后输出如下序列：
(1,begin)(10,’x’)(18,:=)(11,9)(26,;)(2,if)…
1.3
实验原理
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
1.
主程序示意图
主程序示意图如图
1 1所示。其中初值包括如下两个方面：
（1）
关键字表的初值。
关键字作为特殊标识符处理，把他们预先安排在一张表格中（成为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下。
char
rwtab[6]
=
{“begin”,”if”,”then”,”while”,”do”,”end”};
（2）
程序中需要用到的主变量为syn,token和sum。
2.
扫描子程序的算法思想
首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整形单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图
1 2所示。
图
1 1
此法分析主程序示意图
图
1 2
词法分析程序流程
1.4
算法实现
在我的程序使用C++语言编制，在其中我使用了类这个工具来封装整个词法分析代码，并且把所有的全局变量都封装到类或者类的功能函数中，这样可以使得程序代码更加有序，简化后续的调试和改进工作。
同时，我的词法分析程序将处理的结果放在一个链表中，并且在程序结束后返回链条头。这样设计可以减少后续语法分析程序的编写难度。
同时，我的程序还可以检测数字输入错误。如果输入了非法的数字，程序就会提示错误。
我的源程序如下：
complie_common.h:
#ifndef
COMPILE_COMMON_H_INCLUDED
#define
COMPILE_COMMON_H_INCLUDED
//词法分析返回的结果链表节点结构
typedef
struct
WORD_ANALY_RESULT_
{
int
syn;
char
word;
int
sum;
struct
WORD_ANALY_RESULT_
next,*
prev;
}
WORD_ANALY_RESULT;
#endif
//
COMPILE_COMMON_H_INCLUDED
word_analy.h:
#ifndef
WORD_ANALY_H_INCLUDED
#define
WORD_ANALY_H_INCLUDED
#include“compile_common.h“//输入一个以
/0
结尾的源程序字符缓冲区
//输出它的词法分析结果，就是一个二元组链表
class
WordAnaly
{
public:
WordAnaly()=default;
~WordAnaly();
//词法分析功能函数
WORD_ANALY_RESULT
scanner(
char
source_buffer
);
private:
char
key_word_map[6]
=
{“begin“,“if“,“then“,“while“,“do“,“end“};
//可以直接接在数字之后的符号
char
after_num[15]
=
{
;,-,+,=,/,,/n,/r,/t,!,,:,*,’)’
};
//关键字的个数
int
key_word_num
=
sizeof(this->key_word_map)/sizeof(char);
//为链表节点分配空间
WORD_ANALY_RESULT
AllocMem();
//检查字符是否是字母
inline
int
is_letter(
char
ch
);
//检查字符是否是数字
inline
int
is_number(
char
ch
);
//检查字符是否是空白字符
inline
int
is_blank(
char
ch
);
//检查字符串是否是空格
inline
int
is_space(
char
ch
);
};
#endif
//
WORD_ANALY_H_INCLUDED
word_analy.cpp:
#include
#include
#include
#include“word_analy.h“WORD_ANALY_RESULT
WordAnaly::scanner(
char
source_buffer)
{
//字符
char
token[33];
//当前处理的源程序的位置
int
source_buffer_pointer
=
0;
//当前token字符串的位置
int
token_pointer
=
0;
char
temp_ch;
//返回的结果链表头及其临时指针
WORD_ANALY_RESULT
pWAR_head,*
pWAR_p,*
pWAR_q,*
pWAR_r;
pWAR_head
=
this->AllocMem();
pWAR_p
=
pWAR_head;
while(
1
)
{
token_pointer
=
0;
temp_ch
=
source_buffer[source_buffer_pointer++];
while(
this->is_blank(temp_ch))
temp_ch
=
source_buffer[source_buffer_pointer++];
if(
this->is_letter(temp_ch)
)
{
while(
this->is_letter(temp_ch)
||
this->is_number(temp_ch))
{
token[token_pointer++]
=
temp_ch;
if(
token_pointer
>
32
)
{
printf(“Identifer
overflow!/n“);
return
NULL;
}
temp_ch
=
source_buffer[source_buffer_pointer++];
}
token[token_pointer++]
=
/0
;
source_buffer_pointer--;
pWAR_p->syn
=
10;
for(
int
i
=
0;i
key_word_num
-
1;
i
++)
if(
strcmp(key_word_map[i],token)
==
0)
{
pWAR_p->syn
=
i
+
1;
break;
}
}
else
if(
this->is_number(temp_ch)
)
{
while(
this->is_number(temp_ch)
)
{
pWAR_p->sum
=
pWAR_p->sum*10
+
temp_ch
-
0
;
temp_ch
=
source_buffer[source_buffer_pointer++];
}
pWAR_p->syn
=
-22;
for(
int
i
=
0;i
after_num[i])
{
pWAR_p->syn
=
11;
break;
}
}
//如果数字后面跟了非法字符，就报错
if(pWAR_p->syn
==
-22
)
{
printf(“Identifier
error!/n“);
return
NULL;
}
source_buffer_pointer
--;
}
else
switch(temp_ch)
{
case
)
{
pWAR_p->syn
=
21;
token[token_pointer++]
=
temp_ch;
token[token_pointer++]
=
/0
;
}
else
if(
temp_ch
==
=
)
{
pWAR_p->syn
=
22;
token[token_pointer++]
=
temp_ch;
token[token_pointer++]
=
/0
;
}
else
{
pWAR_p->syn
=
20;
source_buffer_pointer--;
}
break;
case
>
:
token[token_pointer++]
=
temp_ch;
temp_ch
=
source_buffer[source_buffer_pointer++];
if(
temp_ch==
=
)
{
pWAR_p->syn
=
24;
token[token_pointer++]
=
temp_ch;
token[token_pointer++]
=
/0
;
}
else
{
pWAR_p->syn
=
23;
source_buffer_pointer--;
}
break;
case
:
:
token[token_pointer++]
=
temp_ch;
temp_ch
=
source_buffer[source_buffer_pointer++];
if(
temp_ch
==
=
)
{
pWAR_p->syn
=
18;
token[token_pointer++]
=
temp_ch;
token[token_pointer++]
=
/0
;
}
else
{
pWAR_p->syn
=
17;
source_buffer_pointer--;
}
break;
case
+
:
pWAR_p->syn
=
13;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
-
:
pWAR_p->syn
=
14;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
:
pWAR_p->syn
=
15;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
/
:
pWAR_p->syn
=
16;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
;
:
pWAR_p->syn
=
26;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
(
:
pWAR_p->syn
=
27;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
)
:
pWAR_p->syn
=
28;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
case
#
:
pWAR_p->syn
=
0;
token[0]
=
temp_ch;
token[1]
=
/0
;
break;
default:
pWAR_p->syn
=
-1;
}
pWAR_p->word
=
(char*)calloc(sizeof(char),token_pointer
+
4);
strcpy(pWAR_p->word,token);
pWAR_q
=
this->AllocMem();
pWAR_p->next
=
pWAR_q;
pWAR_q->prev
=
pWAR_p;
pWAR_p
=
pWAR_q;
//遇到结束符#就退出
if
(
pWAR_p->prev->syn
==
0)
break;
}
pWAR_p->prev->next
=
NULL;
free(pWAR_p);
return
pWAR_head;
}
WORD_ANALY_RESULT
WordAnaly::AllocMem()
{
return
(WORD_ANALY_RESULT)calloc(sizeof(WORD_ANALY_RESULT),1);
}
int
WordAnaly::is_letter(
char
ch
)
{
return
((ch
>=
a
int
p
=
0;
char
ch;
WORD_ANALY_RESULT
result;
WordAnaly
pWordAnaly
=
new
WordAnaly();
printf(“/n
please
input
string
:
/n“);
//读入源程序
do
{
buffer[p++]
=
ch
=
getchar();
}while(
ch
!=
#
);
//获取结果链表
result
=
pWordAnaly->scanner(buffer);
//输出结果
while(
result
)
{
if(
result->syn
==
11)
printf(“(%d,%d)/n“,result->syn,result->sum);
else
if(
result->syn
==
-1)
printf(“Error/n“);
else
if
(result->syn
==
-2)
{
printf(“Identifier
error/n“);
result
=
result->next;
}
else
printf(“(%d,%s)/n“,result->syn,result->word);
result
=
result->next;
}
return
0;
}
1.5
测试结果
首先我输入书上的测试用例，其结果如图所示：
图
1 3
书上的测试用例运行结果
接着我故意将数字后面直接与字母相连，测试一下程序的错误处理能力。
图
1 4
输错数字后程序的操作
可见程序可以正确处理标识符错误的情况。此时，我再输入一些非法字符，看一看程序的处理能力。
图
1 5
输入非法字符后程序的操作
由上述示例可以看到，程序实现了预定的功能，也可以对一些特定的错误进行处理，可以说这个程序的编制是成功的。
2
实验二
语法分析
2.1
实验目的
编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。
2.2
实验要求
利用C语言编制递归下降分析程序，并对简单语言进行语法分析。
1.
待分析的简单语言的语法
用扩充的BNF表示如下：
（1）
::=
begin
end
（2）
::=
{;
}
（3）
::=
（4）
::=
ID
:=
（5）
::=
{+
|
-}
（6）
::=
{*
|
/}
（7）
::=
ID
|
NUM
|
()
2.
实验要求说明
输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。
例如：
输入
begin
a:=9;
x:=2*3;
b:=a+x
end
#
输出
success
输入
x:=a+b*c
end
#
输出
error
2.3
实验原理
(1)
主程序示意图如图
2 1所示。
(2)
递归下降分析程序示意图如所示。
(3)
语句串分析过程示意图如所示。
(4)
表达式语句分析函数流程如所示。
图
2 1语法分析主程序示意图
图
2 2
递归下降分析程序示意图
图
2 3
语句串分析示意图
图
2 4
statement语句分析函数示意图
图
2 5
expression表达式分析函数示意图
图
2 6
term分析函数示意图
图
2 7
factor分析过程示意图
2.4
算法实现
同词法分析程序一样，本程序也是使用C++语言，并借助了类这个工具来编写的。并且，它的输入就是我的词法分析程序输出的链表。
同时，我在实际的编程工作中，对于出错的判断并没有使用变量kk，而是直接通过各个函数的返回值来进行判断。一旦某个函数返回0，就说明语法分析过程出错，则工作停止并输出错误。
并且，由于本次实验所用的词法分析函数就是在前面介绍的，而且前面也已经展示了代码，因此，下面我将仅展示我的语法分析函数的代码。
grammar_analy.h:
#include“word_analy.h“#include“compile_common.h“class
GrammerAnaly
{
public:
GrammerAnaly()
=
default;
int
grammer_analy(WORD_ANALY_RESULT
head)
{
this->pWordAnalyResult
=
head;
return
lrparser();
}
private:
WORD_ANALY_RESULT
pWordAnalyResult;
int
scanner();
int
lrparser();
//语句串分析
int
word_string();
//赋值语句分析
int
statement();
//表达式分析
int
expression();
//项分析
int
term();
//因子分析
int
factor();
};
#endif
grammar_analy.cpp:
#include
#include“grammer_analy.h“int
GrammerAnaly::scanner()
{
this->pWordAnalyResult
=
this->pWordAnalyResult->next;
if
(this->pWordAnalyResult
==
NULL)
return
0;
return
1;
}
int
GrammerAnaly::lrparser()
{
if
(this->pWordAnalyResult
==
NULL)
return
0;
//当前符号是否为begin
if
(this->pWordAnalyResult->syn
==
1)
{
if
(!this->scanner())
return
0;
if
(this->word_string()
==
0)
return
0;
//当前符号是否为end
if
(this->pWordAnalyResult->syn
==
6)
{
if
(!this->scanner())
return
0;
//当前符号是否为#
if
(this->pWordAnalyResult->syn
==
0)
return
1;
}
else
{
printf(“缺少
end
/n“);
}
}
else
{
printf(“缺少begin/n“);
}
return
0;
}
int
GrammerAnaly::word_string()
{
if
(this->statement()
==
0)
return
0;
//当前符号是否为；
while
(this->pWordAnalyResult->syn
==
26)
{
if
(!this->scanner())
return
0;
if
(this->statement()
==
0)
return
0;
}
return
1;
}
int
GrammerAnaly::statement()
{
//当前符号是否为变量名
if
(this->pWordAnalyResult->syn
==
10)
{
if
(!this->scanner())
return
0;
//当前符号是否为赋值号
if
(this->pWordAnalyResult->syn
==
18)
{
if
(!this->scanner())
return
0;
if
(this->expression()
==
0)
return
0;
}
else
{
printf(“语句错误/n“);
return
0;
}
}
return
1;
}
int
GrammerAnaly::expression()
{
if
(this->term()
==
0)
return
0;
//当前符号是否为加号或减号
while
(this->pWordAnalyResult->syn
==
13
||
this->pWordAnalyResult->syn
==
14)
{
if
(!this->scanner())
return
0;
if
(this->term()
==
0)
return
0;
}
return
1;
}
int
GrammerAnaly::term()
{
if
(this->factor()
==
0)
return
0;
//当前符号是否为乘号或除号
while
(this->pWordAnalyResult->syn
==
15
||
this->pWordAnalyResult->syn
==
16)
{
if
(!this->scanner())
return
0;
if
(this->factor()
==
0)
return
0;
}
return
1;
}
int
GrammerAnaly::factor()
{
//当前符号是否为变量名或整形数字
if
(this->pWordAnalyResult->syn
==
10
||
this->pWordAnalyResult->syn
==
11)
{
if
(!this->scanner())
return
0;
}
//当前符号是否为左括号
else
if
(this->pWordAnalyResult->syn
==
27)
{
if
(!this->scanner())
return
0;
if
(this->expression()
==
0)
return
0;
//当前符号是否为右括号
if
(this->pWordAnalyResult->syn
==
28)
{
if
(!this->scanner())
return
0;
}
else
{
printf(“缺少
)
错误/n“);
return
0;
}
}
else
{
printf(“表达式错误/n“);
return
0;
}
return
1;
}main.cpp:
#include
#include“word_analy.h“#include“grammer_analy.h“int
main()
{
char
buffer[300];
int
p
=
0;
char
ch;
WORD_ANALY_RESULT
result;
WordAnaly
pWordAnaly
=
new
WordAnaly();
GrammerAnaly
pGrammerAnaly
=
new
GrammerAnaly();
printf(“/n
please
input
string
:
/n“);
do
{
buffer[p++]
=
ch
=
getchar();
}while(
ch
!=
#
);
//获取此法分析结果
result
=
pWordAnaly->scanner(buffer);
if
(pGrammerAnaly->grammer_analy(result)
==
1)
printf(“Success!/n“);
else
printf(“Error!/n“);
return
0;
}
2.5
测试结果
我先用书上的两个例子源程序进行了测试，结果如下：
图
2 8
书上测试用例1运行结果
图
2 9
书上测试用例2运行结果
由书上的两个例子的运行结果可以看出来，程序目前可以对正确的源程序判定成功，也可以对错误的源程序指出错误原因。接下来我将再测试几个例子。
1.
测试一个不加’end’的源程序代码。
图
2 10
自编用例1运行结果
2.
测试一段带有括号的正确的代码。
图
2 11
自编用例2运行结果
3.
此时一段缺少右括号’)’的代码
图
2 12
自编用例3运行结果
4.
测试一段输入了错误的标识符的代码
图
2 13
自编用例5运行结果
由上面的运行结果可以看出，对一部分程序源代码，我的语法分析程序可以识别正确的表达式，并且找出错误的表达式中出错的地方。虽然并没有测试更多的例子，不过现在可以说，我的语法分析程序的编制是成功的。
3
总结与体会
通过这次编译原理上机，我学到了很多的东西。
首先，我认识到了，编译原理这门课的只是并不仅仅局限在理论上。在上机之前，我们所接触的编译原理都是存在于课堂上、书本中的，都是书上一条条的理论与规则。虽然我们都知道我们平时所做的编程工作都离不开这门课程，但是还是觉得这门课程的知识很高深，也距离我们很遥远。直到上机的时候，我才发现，原来在书本上深奥的知识，实践起来居然会那么简单。上机的过程也打消了编译原理这门课程在我心中的神秘性。并且，在实现词法分析与语法分析程序的过程中，我深切感受到了规格化的重要性。正因为规格化理论上的复杂与严谨，我们在动手去实现它的时候才会这么轻松和简单。
在上机实验的过程中，我也看到有一些同学使用了Yacc和Lex等工具来生成产生自己的代码。我在之前仅仅是听老师提过一次，并没有尝试去了解和使用它，没想到这些同学就已经开始积极动手实践了。看到这些同学，我也很惭愧，感觉自己在学习的主动性上还是差了很多。之后我就去了解了一些Yacc和Lex的有关知识，发现它们的使用也并不是太困难。因此我打算等这段时间考试课设都忙完了以后去深入学习一下这两个工具的。
同时，在编写程序的时候，我也遇到了一些问题。比如全局变量太乱不好管理、词法分析程序与语法分析程序直接不好做衔接、如何检测程序中的错误等等。通过不断的调试与改进，我最终解决了这些问题，完成了上机实验的任务。不过话说回来，我的解决方式也并不完美。因为中间的数据是靠链表进行传递的，所以语法分析程序和词法分析程序不能实时通信，这样的话在出现错误的时候程序不能及时响应，会浪费一定的时间。这一点还是需要再进行改进。
总地来说，这次上机实验加深了我对编译原理这门课程的认识，提高了我编写程序和查错改错能力，也让我认识到了自己在学习上面的不足，让我知道我自身需要提高的地方。在接下来的学习生活中，我一定会改正这些错误，让自己的学习更上一层楼。
23