词法分析器
一、实验目的二、实验内容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版的,对于这方面有一定的了解。
要存储保留字,标示符,还有常数,先建立一个表结构,用于存储保留字和特殊符号表,在查找是否是保留字和特殊符号表时,就遍历查询此表,建立一个标示符表,假如读到一个字符串,那么先查询保留字和特殊符号表,如果可以查到那就是保留字,如果查不到,那么再查询标示符表,如果在标示符表也查不到,那就将这个字符串加入到标识符表,此外还要建立一个常数表,还要建立一个记录行号的计数位,还有一个记录错误的计数位。
下面,才开始按实验给出的函数编程,首先打开读文件,和写文件,初始化操作,再就是循环程序一个一个读取字符串,数字,符号,并且对其进行处理。
在处理小数点的时候,迷糊了好久,问了一次老师,后来把状态转换图绘制出来,才清晰了许多。
再往下就是对注释处理,在这里要把‘/’这个符号的处理和其他符号的处理分开了,读取了第一个字符是‘/’后,还要继续往下读取,看看后面是‘/’还是‘’还是‘=’,还是没有,这里最难处理的就是‘’因为结束的时候你要读取两个字符,需要挨着的两个字符是‘*/’才行,其次就是‘/’这是单行注释,遇到回车换行符结束就行了。
再继续往下走,就是符号的处理,每个字符都要写一个返回,代码耦合度太高了,再次改进状态转换图,这时候就把字符分类处理,那些第二个字符是‘=’的分成一组,第一个字符是‘|’和‘&’的单独处理,剩下其他的,就直接去符号表查找,有就输出,没有就报错,并且记录行号,输出非法字符。
到此,实验结束。通过这次试验,收获很多,也激发了我对编译原理的兴趣,不断地思考,给我带来了成功后的快感。希望在今后的学习中也会如此。畅快淋漓!
如果觉得《【编译原理-实验-1】词法分析器最详细设计报告(c++版)》对你有帮助,请点赞、收藏,并留下你的观点哦!