词法分析器

一、实验目的二、实验内容1．根据状态转换图直接编程2．编写DFA模拟程序（选做） 三、实验要求1．能对任何S语言源程序进行分析（S语言定义见下面）2．能检查并处理某些词法分析错误 四、S语言定义1.保留字和特殊符号表2．S语言表达式和语句说明 五、程序参考结构说明六、实验过程说明程序源码：运行结果：实验总结：

一、实验目的

了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA编写通用的词法分析程序。（选做）

二、实验内容

1．根据状态转换图直接编程

编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。

具体任务有：

（1）组织源程序的输入

（2）识别单词的类别并记录类别编号和值，形成二元式输出，得到单词流文件

（3）删除注释、空格和无用符号

（4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。

（5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。

标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址

注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。

常量表结构：常量名，常量值

2．编写DFA模拟程序（选做）

算法如下：

DFA（S=S0,MOVE[ ][ ],F[ ],ALPHABET[ ]）

/S为状态，初值为DFA的初态，MOVE[ ][ ]为状态转换矩阵，F[ ] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[ ][ ] 中列标题的字母顺序一致。/

{

Char Wordbuffer[10]=“”//单词缓冲区置空

Nextchar=getchar（）；//读

i=0；

while（nextchar！=NULL）//NULL代表此类单词

{ if （nextchar！∈ALPHABET[]） {ERROR（“非法字符”），return（“非法字符”）；}

S=MOVE[S][nextchar] //下一状态

if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误

wordbuffer[i]=nextchar ； //保存单词符号

i++；

nextchar=getchar（）；

}

Wordbuffer[i]=‘\0’;

If（S∈F）return（wordbuffer）； //接受

Else return（“不接受”）；

}

该算法要求：实现DFA算法，给定一个DFA（初态、状态转换矩阵、终态集、字母表），调用DFA（），识别给定源程序中的单词，查看结果是否正确。

三、实验要求

1．能对任何S语言源程序进行分析（S语言定义见下面）

在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。

2．能检查并处理某些词法分析错误

词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。

本实验要求处理以下两种错误（编号分别为1，2）：

1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。

2：源程序文件结束而注释未结束。注释格式为：/* …… */

四、S语言定义

1.保留字和特殊符号表

单词的构词规则：

字母=[A-Z a-z]

数字=[0-9]

标识符=（字母|）（字母|数字|）*

数字=数字(数字)*( .数字+|)

2．S语言表达式和语句说明

1．算术表达式:+、-、、/、%

2．关系运算符：>、>=、<、<=、==、！=

3．赋值运算符：=，+=、-=、=、/=、%=

4．变量说明：类型标识符 变量名表；

5．类型标识符：int char float

6．If语句：if 表达式then 语句 [else 语句]

7．For语句：for（表达式1；表达式2；表达式3） 语句

8．While语句：while 表达式 do 语句

9．S语言程序：由函数构成，函数不能嵌套定义。

函数格式为：返回值 函数名（参数）begin数据说明语句end10．复合语句构成begin语句序列end

五、程序参考结构说明

1．Initscanner函数：程序初始化：输入并打开源程序文件和目标程序文件，初始化保留字表

2．Scanner函数：若文件未结束，反复调用lexscan函数识别单词。

3．Lexscan函数：根据读入的单词的第一个字符确定调用不同的单词识别函数

4．Isalpha函数：识别保留字和标识符

5．Isnumber函数：识别整数，如有精力，可加入识别实数部分工功能

6．Isanotation函数：处理除号/和注释

7．Isother函数识别其他特殊字符

8．Output函数：输出单词的二元式到目标文件，输出格式（单词助记符，单词内码值），如（int，-）（rlop，>）……

9．Error函数：输出错误信息到屏幕

10．除此之外，还可以设置查符号表，填写符号表等函数，学生可自行设计。

六、实验过程说明

测试源程序示例：

//aa.cvoid aa( )beginfloat rate,circle; rate=3;circle=3.14*rate*rate;end

输出结果：

（1）输出结果文件：

（void,-）(id, 0) ((,-) (),-) (begin,- ) ( float,-) (id,1)……

（2）标识符的符号表：

Name type address0aa1rate2circle345

（3）常数表：

Name value0313.1423

程序源码：

#include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<string.h> #define MAX 10// 保留字符号长度 #define MAXSIZE 45// 保留字和特殊符号表长度 #define NUM 30// 标识符和常数的个数FILE *in,*out;// 指向文件的指针 char infile[MAX];// 文件名字 char token[MAX];//字符组，存放构成单词符号的字符串 char Word[NUM][MAX];// 标识符 char consts[NUM][MAX];// 常数 char lownum[NUM][MAX]={"0","1","2","3","4","5","6","7","8","9", "10","11","12","13","14","15","16","17","18","19" "20","21","22","23","24","25","26","27","28","29"}; //自定义表int n=1;// 行号 int num=0; // 错误统计数typedef struct Key_word// 保留字和特殊符号表结构 {//int keyNum; //种别编码 char keyWord[MAX]; // 单词符号 char keySign[MAX]; //助记符 char keyValue[MAX]; //内码值 }Key_word; //初始化保留字表Key_word Key[MAXSIZE]=//保留字和特殊符号数组 {{"int","int","-"},//保留字 1 {"char","char","-"},//2 {"float","float","-"}, //3 {"void","void","-"},//4 {"const","const","-"},//5 {"for","for","-"}, //6 {"if","if","-"},//7 {"else","else","-"},//8 {"then","then","-"}, //9 {"while","while","-"},//10 {"switch","switch","-"},//11 {"break","break","-"}, //12 {"begin","begin","-"},//13 {"end","end","-"},//14 {"","",""}, //15空余出来，以便扩充 {"","",""},//16 {"","id",""},//17标示符 {"","num",""}, //18数字（常数和实数） {"+","+","-"},//19 {"-","-","-"},//20 {"*","*","-"},//21 {"/","/","-"},//22 {"%","%","-"},//23 {"(","(","-"},//24 {")",")","-"},//25 {"[","[","-"},//26 {"]","]","-"},//27 {"","",""},//28 {"<","rlop","<"},//29 {">","rlop",">"},//30 {"<=","rlop","<="},//31 {">=","rlop",">="},//32 {"=","rlop","="}, //33 {"!=","rlop","!="},//34 {",",",","-"},//35 {";",";","-"},//36 {"/=","/=","-"},//37 {"+=","+=","-"},//38 {"-=","-=","-"}, //39 {"*=","*=","-"},//40 {"%=","%=","-"},//41 {"||","or","-"}, //42 {"&&","and","-"},//43 {"!","not","-"},//44 {"=","=","-"}//45 }; //打开关闭文件int Initscanner() {printf(" 请输入要输入的文件 :\n"); scanf("%s",infile); //读取指定文件 if((in=fopen(infile,"r"))==NULL) {printf("cannot open infile!\n"); return 0; }//将文件输出 if((out=fopen("word.txt","a+"))==NULL) {printf("cannot open outfile!\n"); return 0; } return 0; } //写入文件 void Output(int n,int m) {//在文件中写入二元组（Key[n].keySign，fputs("(",out); fputs(Key[n].keySign,out); fputs(",",out); //如果是关键字或特殊字符，//在文件中写入（Key[n].keySign，Key[n].keyValue //Key[n].keyValue都是 — if(m==-1) fputs(Key[n].keyValue,out); //如果是表示符，写入标识符在自定义表中对应的下标的值（Key[n].keySign，lownum[m]else fputs(lownum[m],out);// 下标//在文件中写入（Key[n].keySign，Key[n].keyValue） fputs(")",out); }//扫描指针回退一个字符 void remove() {//int fseek( FILE *stream, long offset, int origin );stream为文件指针 offset为偏移量，正数表示正向偏移，负数表示负向偏移//SEEK_SET： 文件开头 SEEK_CUR： 当前位置 SEEK_END： 文件结尾fseek(in,-1,SEEK_CUR); } //Isalpha 函数：识别保留字和标识符int Isalpha() {int i; // 关键字，16个关键字，循环匹配 for(i=0;i<16;i++){//判断token是否等于Key[i].keyWordif(strcmp(token,Key[i].keyWord)==0) {Output(i,-1); //匹配到对应的关键字，传回关键字在数组中的位置，-1表示是关键字 return 0; } } //标识符 Word[NUM][MAX] //i=表示符id for(i=0;i<NUM;i++) {//如果标示符表【i】位置不为空，并且标示符表【i】中存在该标示符 if((Word[i][0]!=NULL)&&strcmp(token,Word[i])==0) {Output(16,i); return 0; }//如果标示符表【i】位置为空 if(Word[i][0]==NULL) {//将token中的值复制到标示符表Word[i]中 strcpy(Word[i],token); Output(16,i); return 0; } } return 0; } //Isnumber 函数 :consts[NUM][MAX] 识别整数，如有精力，可加入识别实数部分工功能 int Isnumber(){int i;for(i=0;i<NUM;i++) {//如果数字表(consts[i]位置不为空，并且数字表中存在该数字 if((consts[i][0]!=NULL)&&strcmp(token,consts[i])==0) {Output(17,i); return 0; } // 如果数字表(consts[i]位置为空if(consts[i][0]==NULL) {//将token中的值复制到数字表consts[i]中 strcpy(consts[i],token); Output(17,i); return 0; } } return 0; } //Isanotation 函数：处理除号 /和注释 void Isanotation() //提示第一个字符已经存为 /了 {char ch,pre; ch=getc(in); if(ch=='=')// "/=" Output(36,-1); else if(ch=='*')// "/*" {ch=getc(in); do{//如果文件结束，则返回非0值，否则返回0 if(feof(in)) {num++; //记录错误数量 printf("\n 第(%d) 行 : 注释错误 : /*后面的字符全部当做注释，缺少结束注释*/\n",n); break; } pre=ch; ch=getc(in); }while(pre!='*'||ch!='/'); } else if(ch=='/')// "//" {ch=getc(in); while (ch != '\n'){ch=getc(in); }n++; } else// "/" {remove(); //多读入一个字符，指针回退一个字符Output(21,-1); } } //Isother 函数识别其他特殊字符void Isother() {int i=1;int j=0; char ch;//()，[] //, ;//< > ! %<= >= != %= //+ - * =if(token[0]=='<'||token[0]=='>'||token[0]=='!'||token[0]=='%'||token[0]=='+'||token[0]=='-'||token[0]=='*'||token[0]=='=') {ch=getc(in); if(ch=='=') token[i++]=ch; else remove(); }//| || else if(token[0]=='|') {ch=getc(in); if(ch=='|') token[i++]=ch; else remove(); }//& && else if(token[0]=='&') {ch=getc(in); if(ch=='&') token[i++]=ch; else remove(); } //字符串数组结尾就是'\0',表示这串字符到结尾了 token[i]='\0'; //匹配字符表是否存在该字符 for(i=18;i<45;i++) {if(strcmp(token,Key[i].keyWord)==0) {Output(i,-1); //-1表示特殊字符 break; } } //如果不存在，输出非法字符 if(i==45) {num++; printf("\n 第(%d)行 : 字符错误 : %s 字符非法 \n",n,token); } } //Scanner函数：若文件未结束，反复调用lexscan函数识别单词。 void Scanner() {char ch; int i; ch=getc(in); while(!feof(in)) {while(ch==' '||ch=='\t'||ch=='\n') // 先统计行数{if(ch=='\n') ++n; ch=getc(in); } // 标识符 isalpha(ch)单词if(((ch>='a')&&(ch<='z'))||(ch=='_')){i=1; token[0]=ch; ch=getc(in);//当ch为非字母或数字时，终止循环 while(((ch>='a')&&(ch<='z'))||((ch>='0')&&(ch<='9')))//word number {token[i++]=ch; ch=getc(in); } token[i]='\0'; //识别保留字和标识符 Isalpha(); }// 整数 else if((ch>='0')&&(ch<='9')){i=1; token[0]=ch; ch=getc(in); //当ch不是数字时终止循环 while(isdigit(ch)) {token[i++]=ch; ch=getc(in); }//如果下一位为. if(ch=='.'){token[i++]=ch; ch=getc(in); while(isdigit(ch)){token[i++]=ch; ch=getc(in); }}token[i]='\0'; Isnumber();} else if(ch=='/')// 区分 "/" , "/=" , "/*" {token[0]=ch; Isanotation(); ch=getc(in); } else //特殊字符{token[0]=ch; Isother(); ch=getc(in); } } } void show() {int i; char ch; printf("分析程序：\n");rewind(in);while(!feof(in)) {printf("%c",getc(in)); }printf("\n 二元式 :\n"); rewind(out); while(!feof(out)) {printf("%c",getc(out)); } printf("\n 标志符表 \n"); for(i=0;i<NUM;i++) {if(Word[i][0]!=NULL) printf("%d,%s\n",i,Word[i]); } printf("\n 常数表 \n"); for(i=0;i<NUM;i++) {if(consts[i][0]!=NULL) printf("%d,%s\n",i,consts[i]); } } int main() {//初始化 Initscanner(); Scanner(); printf("\n 共有 %d 个错误 \n",num); show(); fclose(in); fclose(out); return 0;}

在文件夹下新建chengxu.txt文件，用于程序分析

//aa.cvoid $ aa( )begin $/*hsahdkjashdjg*/float rate,circle; rate=3; $circle=3.14*rate*rate;end $@

在文件夹下新建word.txt文件，用于输出分析的二元组结果

运行结果：

输入文件chengxu.txt

实验总结：

将近两年没有用c语言编程，在实验刚开始做时，甚至连怎么用dev运行一个项目这么基础的东西都不会了，后来通过自己查找，想起来要先编译，再运行。当看到词法分析器，这么多的实验报告后，我很蒙，不知道从什么地方下手，于是我一遍一遍的看老师发的视频，参考书上的案例，由于书上的代码不全，有些函数不存在，可以说，书上的就是伪代码。

我只能自己去问百度了，首先我再百度上查找了一份用java编写的词法分析器，一看，直接拷贝到编辑器运行一边，运行成功，并且可以分析出字符的不合法，还能找出错误，这使我找到了方向，于是我准备研究这个代码，因为我对java比较熟悉，语法读起来还是比较方便的，从头到尾的仔细读了一遍，每一个不懂得就打上注释。

后来读着读着，我开始慢慢理解什么叫标示符，什么叫保留字，还有数字需要读出来存到常数表，标示符需要判断结束存储到标识符表，大概了解了词法分析器的作用和功能，我开始发现如果要想写好，并且这么多字符，要写的井而有序，思路清晰，一定要画好状态转换图。

首先打一遍草稿，然后再在专业画图工具Visio上绘制，这个图花费了我很长时间，我参考书上的，起初绘制的状态转换图，每个符号都返回一个二元组，图画了一大长溜，画完图后，开始编程c语言版的，为什么我对java那么熟悉，不编java版的呢，其实自己也是想顺便练习一下c编程，实验中明确给出了要用到的函数，一个初始化，一个用来循环字符，最后一个关闭文件流。

函数都知道了，开始准备需要什么样的数组，由于之前看过一个java版的，对于这方面有一定的了解。

要存储保留字，标示符，还有常数，先建立一个表结构，用于存储保留字和特殊符号表，在查找是否是保留字和特殊符号表时，就遍历查询此表，建立一个标示符表，假如读到一个字符串，那么先查询保留字和特殊符号表，如果可以查到那就是保留字，如果查不到，那么再查询标示符表，如果在标示符表也查不到，那就将这个字符串加入到标识符表，此外还要建立一个常数表，还要建立一个记录行号的计数位，还有一个记录错误的计数位。

下面，才开始按实验给出的函数编程，首先打开读文件，和写文件，初始化操作，再就是循环程序一个一个读取字符串，数字，符号，并且对其进行处理。

在处理小数点的时候，迷糊了好久，问了一次老师，后来把状态转换图绘制出来，才清晰了许多。

再往下就是对注释处理，在这里要把‘/’这个符号的处理和其他符号的处理分开了，读取了第一个字符是‘/’后，还要继续往下读取，看看后面是‘/’还是‘’还是‘=’，还是没有，这里最难处理的就是‘’因为结束的时候你要读取两个字符，需要挨着的两个字符是‘*/’才行，其次就是‘/’这是单行注释，遇到回车换行符结束就行了。

再继续往下走，就是符号的处理，每个字符都要写一个返回，代码耦合度太高了，再次改进状态转换图，这时候就把字符分类处理，那些第二个字符是‘=’的分成一组，第一个字符是‘|’和‘&’的单独处理，剩下其他的，就直接去符号表查找，有就输出，没有就报错，并且记录行号，输出非法字符。

到此，实验结束。通过这次试验，收获很多，也激发了我对编译原理的兴趣，不断地思考，给我带来了成功后的快感。希望在今后的学习中也会如此。畅快淋漓！