编译原理实验一词法分析

《编译原理》（2014-2015学年第1学期）实验报告学号：2012329620058姓名：胡冰倩班级：12计科3班实验一：词法分析程序一、实验目的1、构造一个《科学计算器》的词法分析程序，程序要求能对输入的字符串流进行词法分析。2、在实验的过程中，学会应用词法分析的方法——构造NFA和DFA。二、实验内容和要求1、科学计算器的功能作为一个科学计算器，最重要的自然是能够计算，以下是罗列的一些可以实现的功能：1）基本四则运算2）三角函数计算3）指幂运算4）表达式求值5）log运算6）提供一些基本常数，如PI、e等7）进制转换8）变量存储2、要实现该科学计算器，本次实验首先需要完成词法分析，下面列举4个输入的表达式，：1.0+2*3=1.0+(2*3+cos3)/3.6-6=tg(1.0+(sin2*3+cos3)/3.6-6)=4.0log(1.0+(sin2*3+cos3)/3.6-6)=期望程序能根据实现的DFA对任给的一个输入串进行词法分析，程序的输出为单词的token序列$(CLASS,VALUE)。CLASS中存放类别，VALUE中存放token的值，如第一个算式，其输出为：$(CLASS，VALUE)$(number,1.0)$(plus,+)$(number,2)$(mul,*)$(number,3)关于TOKEN的分类（CLASS），可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。对于变量标识符和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数在其符号表中登记项的序号。3、程序应通过DFA来完成词法分析。可参考的DFA如下图：图中每一个箭头表明一个字符的输入，由于这个输入，自动机从一个状态变为另一个状态。同学们可以根据自己的理解自行设计DFA。该DFA需能够识别本实验中要实现的科学计算器的所有TOKEN。采用有限自动机（DFA）进行分析，对于特定符号如+、-、*、/、%、(、)、!、^、=，为每一个符号提供一个状态、而其他的一些由字母组成的符号，如ans、pi、sto、clr等，则作为是一个词，之后再对词进行分类处理。（提示：可以参考教材中lex部分的章节，DFA的实现同学们可以使用lex实现（自行搜索下载），也可以自已编码实现。）三、分析过程及源代码1.token的分类将一些由字母组成的函数及常数，如：PI、e、sin、cos、tan、log等归为一类，+、-、*、/、%、（、）、=、^等采用一次一类、把数字归为一类。类别CLASStokenwordPI、e、sin、cos、tg、lognumner0及所有正数plus+minus-mul*div/mod%pow^equ=2.有限状态机状态图3.词法分析器的数据结构与算法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#includecstdio#includestring#includeiostreamusingnamespacestd;charprog[80],token[8];charch;stringCLASS;intp,m=0,n;char*word[6]={PI,e,log,sin,cos,tg};voidscaner(){for(n=0;n8;n++)token[n]=NULL;//把token数组初始化ch=prog[p++];while(ch==''){ch=prog[p];p++;}if((ch='a'&&ch='z')||(ch='A'&&ch='Z'))//如果是字母，则这个token是词{m=0;while((ch='a'&&ch='z')||(ch='A'&&ch='Z')){token[m++]=ch;ch=prog[p++];}p--;CLASS=word;}elseif((ch='0'&&ch='9'))//数字{{m=0;while((ch='0'&&ch='9')||(ch=='.')){token[m++]=ch;ch=prog[p++];}}//把数字由字符类型转化为整数类型CLASS=number;p--;}elseswitch(ch)//其他字符{case'*':CLASS=mul;token[0]=ch;break;case'/':CLASS=div;token[0]=ch;break;case'+':CLASS=plus;token[0]=ch;break;case'-':CLASS=minus;token[0]=ch;break;case'=':CLASS=equ;token[0]=ch;break;case'(':CLASS=lf;token[0]=ch;break;case')':CLASS=rg;token[0]=ch;break;case'^':CLASS=pow;token[0]=ch;break;case'%':CLASS=mod;token[0]=ch;break;57585960616263646566676869707172737475767778}}intmain(){p=0;coutPleaseinputstring:endl;do{cin.get(ch);prog[p++]=ch;}while(ch!='\n');p=0;CLASS=CLASS;strcpy(token,VALUE);do{cout(CLASS,token)endl;scaner();}while(ch!='\n');}4.token的输出四、思考题程序设计中哪些环节影响词法分析的效率？如何提高效率？答：这个词法分析程序是由状dowhile循环语句逐词判断token实现的，影响了整个词法分析器的分析效率，可以考虑使用栈来实现词法分析。