实验 2 词法分析程序的设计
一、实验目的掌握计算机语言的词法分析程序的开发方法。
二、实验内容
编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。
三、实验要求
1、根据以下的正规式，编制正规文法，画出状态图；
标识符
<字母 >(< 字母 >|<数字字符 >)*
十进制整数
0 | (（1|2|3|4|5|6|7|8|9）（ 0|1|2|3|4|5|6|7|8|9） *)
八进制整数
0（ 1|2|3|4|5|6|7）（ 0|1|2|3|4|5|6|7） *
十六进制整数
0x（ 0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（ 0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f） *
运算符和界符
+
- *
/ >
< =
( ) ；
关键字
if
then
else
while
do
2、根据状态图，设计词法分析函数 int scan( )，完成以下功能：
1） 从文本文件中读入测试源代码，根据状态转换图，分析出一个单词，
2） 以二元式形式输出单词 <单词种类，单词属性 >
其中单词种类用整数表示：
0：标识符
1：十进制整数
2：八进制整数
3：十六进制整数
运算符和界符，关键字采用一字一符，不编码
其中单词属性表示如下：
标识符，整数由于采用一类一符，属性用单词表示
运算符和界符，关键字采用一字一符，属性为空
3、编写测试程序，反复调用函数 scan( )，输出单词种别和属性。
四、实验环境
PC 微机
DOS 操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
1、 根据正规式，画出状态转换图；
空白
字母或数字
字母
非字母与数字
*
0
1
2
0~9
1~9
非数字
*
3
4
0
非 1~7 与 x
0~7
*
1~7
非 0~7
5
6
7
x
0~9 或 a~f
*
0~9 或 a~f
非 0~9 与 a~f
8
9
10
+ 或—或*
或/ 或< 或>
或=或(或)
或 ;
11
ifthen
else while
do
12
2、 根据状态图，设计词法分析算法；
观察状态图，其中状态
2、 4、 7、 10（右上角打了星号）需要回调一个字符。
声明一些变量和函数：
ch: 字符变量，存放最新读进的源程序字符。
strToken:
字符串变量，存放构成单词符号的字符串。
GetChar():
子函数，将下一输入字符读到
ch 中，搜索指示器前移一字符位置。
GetBC():
子函数，检查
ch 中的字符是否为空白。若是，则调用
GetChar() 直至 ch
中进入一个非空白字符。
Concat():
子函数，将 ch 中的字符连接到
strToken 之后。
IsLetter():
布尔函数，判断
ch 中的字符是否为字母。
IsDigit():
布尔函数，判断
ch 中的字符是否为数字。
Reserve():
整型函数， 对 strToken 中的字符串查找保留字表， 若它是一个保留字
则返回它的编码，否则返回
0。
SearchOp():
整型函数，对 ch 查找运算符和界符，若它是一个运算符或界符，则
返回它的编码，否则返回
0。
Retract(): 子函数，将搜索指示器回调一个字符位置，将
ch 置为空白字符。
ProError():
错误处理函数。
关键字保存在字符数组中，定义编码为相对数组首地址的位置
+ 1 。保留子表顺序
如下： { if ,then ,else ,while, do } , 则相应编码为： 1， 2，3， 4， 5。
运算符和界符保存在字符数组中， 编码定义与关键字相同， 顺序如下： { + ,- , * , / , > ,
<,=,(,),
；} ，编码为：
1~10。
二元表
单词
单词种类
属性
标识符
十进制整数
八进制整数
0
1
2
单词自身
单词自身
单词自身
十六进制整数
3
单词自身
运算符和界符
单词自身
-
关键字
单词自身
-
算法如下：
ch=?, ; strToken=””;
GetBC();
if(IsLetter()) {
while(IsLetter() || IsDigit())
{ Concat(); GetChar(); }
Retract();
If(Reserve()) printf( "<%s , ->" , strToken);
else printf( "<,0,%s >" , strToken);
}
else if(,1? < =ch && ch <= ?9?) {
while(IsDigit())
{ Concat(); GetChar(); }
Retract();
printf( "<,1,%s >" , strToken) ;
}
else if(ch== ?0?) {
GetChar();
if(ch >= ,1?&& ch <= ,7?) {
while(ch >= ,0? && ch <= ,7?)
{ Concat(); GetChar(); } Retract();
printf( "<,2,%s >" , strToken) ;
}
else if(ch== ?x?) {
GetChar();
while(IsDigit() || ch>= ,a?&& ch<= ?f ?)
{ Concat(); GetChar(); } Retract();
printf( "<,3,%s >" , strToken);
}
else {
Retract();
printf( “<1,0> “) ;
}
}
else if(SearchOp()) printf( "<%c,- >" , ch);
else ProError();
3、 采用
C 或
C++ 语言，设计函数
scan( )，实现该算法；
char GetChar(FILE * fp) {
char ch;
ch = fgetc(fp);
return ch;
//读取文件中的一个字符
}
char GetBC(FILE* fp) {
//读取文件的字符直至
ch不是空白
char ch;
do {
ch = GetChar(fp);
} while (ch == ' ' || ch == '\t' || ch == '\n'); return ch;
}
void Concat(char ch ,char strToken[]) {
//将ch中的字符连接到
strToken之后
char str[2];
str[0] = ch;
str[1] = '\0';
strcat(strToken,str);
}
int IsLetter(char ch) { //布尔函数，判断 ch中的字符是否为字母 ,是返
1，否则返回 0 int flag = 0;
if (ch >= 'a' && ch <= 'z') flag = 1;
return flag;
}
int IsDigit( char ch) { //布尔函数，判断 ch中的字符是否为数字 ,是返
1，否则返回 0 int flag = 0;
if (ch >= '0' && ch <= '9') flag = 1;
return flag;
}
int Reserve(char strToken[]) {
保留字则返回它的编码，否则返回
//整型函数，对strToken中的字符串查找保留字表， 若它是一个 0
int code = 0,i;
char keyWord[6][6] = { "if" , "then" , "else", "while" , "do" };
for (i = 0; i < 5; i++) {
if (strcmp(strToken, keyWord[i]) == 0) {
code = i + 1;
break;
}
}
return code;
}
int SearchOP(char ch) { //整型函数，对 strToken中的字符串查找运算符和界符，若它是一
个运算符或界符，则返回它的编码，否则返回 0
int code = 0, i;
char OP[11] = { '+', '-', '*', '/', '<', '>', '=', '(', ')', ';' };
for (i = 0; i < 10; i++) {
if (ch == OP[i]) {
code = i + 1;
break;
}
}
return code;
}
char Retract(FILE * fp,char ch) {
//子函数，将搜索指示器回调一个字符位置，将
ch置为
空白字符
ch = ' ';
fseek(fp, -1L, 1);
return ch;
}
void ProError( ) {
//错误处理函数
printf( "输入错误！
\n");
return;
}
FILE * scan(FILE * fp ) {
//输出单个二元式
char ch;
char strToken[10];
strToken[0] = '\0';
//置 strToken为空串
ch = GetBC(fp);
//先读取一个非空白的字符
if (feof( fp))
return fp;
//判断文件尾，是则返回调用程序
if (IsLetter(ch)) {
while (IsLetter(ch) || IsDigit(ch)) {
Concat(ch, strToken);
ch = GetChar(fp);
//判断标识符
}
ch = Retract(fp,ch);
if (Reserve(strToken)) {
printf( "<%s,->\n" , strToken);
//判断关键字
}
else
printf( "<0,%s>\n" , strToken);
}
elseif (ch >= '1' && ch <= '9') {
while (IsDigit(ch)) {
Concat(ch, strToken);
ch = GetChar(fp);
//判断十进制整数
}
ch = Retract(fp, ch);
printf( "<1,%s>\n" , strToken);
}
elseif (ch == '0') {
ch = GetChar(fp);
if (ch >= '1' && ch <= '7') {
while (ch >= '0' && ch <= '7') {
Concat(ch, strToken);
ch = GetChar(fp);
//判断八进制整数
}
ch = Retract(fp, ch);
printf( "<2,%s>\n" , strToken);
}
else if (ch == 'x') {
//判断十六进制整数
ch = GetChar(fp);
while (IsDigit(ch) || ch >= 'a' && ch <=
'f') {
Concat(ch, strToken);
ch = GetChar(fp);
}
ch = Retract(fp, ch);
printf( "<3,%s>\n" , strToken);
}
else {
//判断十进制的
0
ch = Retract(fp, ch);
printf( "<1,0>\n" );
}
}
elseif (SearchOP(ch)) {
printf( "<%c,->\n" , ch);
//判断运算符和界符
}
else {
//出错
ProError();
}
return fp;
}
4、 编制测试程序（主函数 main ）；
#include<iostream>
using namespacestd;
#define NULL 0
int main( ) {
FILE * fp;
if ((fp = fopen( "C:\\Users\\Administrator\\Desktop\\Code.txt" , "r" )) == NULL ) { //以只
读方式打开文件，失败则退出程序
printf( "file can not open!" );
exit(0);
}
printf( "词法分析结果如下：
\n");
while (!feof(fp)) {
fp = scan(fp);
//若不是文件尾则执行循环
//输出单词种类、属性的二元式
}
fclose(fp);
//关闭文件
fp = NULL ;
//避免指向非法内存
}
5、调试程序：读入文本文件，检查输出结果。
六、测试数据
输入数据：
编辑一个文本文件 program.txt ，在文件中输入如下内容：
if data+92>0x3f then
data=data+01;
else
data=data-01;
正确结果：
<if , ->
<0 , data>
<+,->
<1 , 92>
<>,->
<3 , 3f>
<then , ->
<0 , data>
<=,>
<0 , data>
<+,->
<2,1>
<; ,->
<else , ->
<0 , data>
<=,->
<0 , data>
<-,->
<2,->
<;,->
七、实验报告要求
实验报告应包括以下几个部分：
1、词法的正规式描述；
2、变换后的 状态图；
3、词法分析程序的数据结构与算法。
八、思考题
1、 词法分析能否采用空格来区分单词？
答：不能，因为程序的语法里有包括：’；’， ‘ { ’，‘ } ‘ ，‘（‘，‘）‘等界符或连接符号存在，这些符号符与单词的连接无空格，用空格区分单词将无法保证程序语法的正确。
2、 程序设计中哪些环节影响词法分析的效率？如何提高效率？
: 本程序在判断关键字时，是在完成对标志符的识别后，判断该标识符是否是保留字，若是则判断为关键字，这种情况下，导致每次识别完一个标识符，都要查询保留字表，会影响效率，可在识别标识符的程序段中添加对关键字的识别，如首字母的特别判断或遇到数字跳过关键字的判断等。另外，程序的实现是通过在主函数中循环调用 scan（）函数来输出二元式，一次调用就输出一个二元式，可以考虑使用堆栈，先将读来的数据压栈，再进行识别，这样比重复调用函数效率更高，而且也不必使用文件指针来回调字节，用堆栈会更方便更安全准确，省去不少程序段。