词法分析程序实现.doc

实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。输入：由无符号数和+，*，/, ( , ) 构成的算术表达式，如1.5E+2100。输出：对识别出的每一单词均单行输出其类别码（无符号数的值暂不要求计算）。三、实现方法与环境1、首先设计识别各类单词的状态转换图。描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0，1，2，6代表非终结符号、及， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。图1 文法G的状态转换图其中编号0，1，2，6代表非终结符号、及， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。四则运算算术符号的识别很简单，直接在状态图的0状态分别引出相应标记的矢线至一个新的终态即可。根据自己的习惯，也可以将其转换为状态矩阵形式。2、词法分析程序编写根据描述语言中各类单词的文法状态转换图或状态矩阵，利用某种语言（C语言或JAVA语言）直接编写词法分析程序。3、词法分析程序测试用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串，对于输入的测试用例的源程序文件，以对照的形式将扫描器的分析结果信息在输出文件中表示出来。四、 源程序#includeusing namespace std; /使用标准命名空间#define M 101 /定义可输入的字符个数#define UNSIGNEDNUMBER 1 /无符号数#define PLUS 2 /加号#define SUBTRACT 3/减号#define MULTIPLY 4/乘号#define DIVIDE 5/除号#define LEFTBRACKET 6/左括号#define RIGHTBRACKET 7/右括号#define INEFFICACIOUSLABEL 8/无效字符串char pause;class AccidenceAnalysis /定义 词法分析 类private:char testStrM,*p;/私有数据public:AccidenceAnalysis();/构造函数AccidenceAnalysis();/析构函数void InputStr();/输入函数void Output(int a,char *p1,char *p2);/输出函数int IsAcceptantCharacter(char *p);/判断输入字符是否属于字符集int IsOperator(char *p);/判断字符是否是字符集+,-,*,/,(,)中的字符int IsUnsignedNum(char *p);/判断字符是否是0-9的整数void AbnormityExamine(char a); /异常检测函数void IdentifyOperator(char *p);/识别字符集+,-,*,/,(,)中的字符void AssortIdentify();/对输入字符分类识别void static StartAccidenceAnalysis();/开始分析函数void static StartSystem();AccidenceAnalysis:AccidenceAnalysis()/构造函数int i;for(i=0;iM;i+)testStri=0;p=&testStr0; /指针P指向字符数组首元素AccidenceAnalysis:AccidenceAnalysis()/析构函数void AccidenceAnalysis:InputStr()/输入函数coutt输入待分析单词M-1字符以内：;char ch;int i=0;while(ch=cin.get()!=n)testStri=ch;i+;void AccidenceAnalysis:Output(int a,char *p1,char *p2)/输出函数coutt类别码：at 单词值：;while(p1=p2)cout*p1;p1+;coutendl;int AccidenceAnalysis:IsOperator(char *p)/判断字符是否是字符集+,-,*,/,(,)中的字char ch=*p;if(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)return 1;elsereturn 0;int AccidenceAnalysis:IsUnsignedNum(char *p)/是否是19的数字char ch=*p;if(0=ch&ch=9)return 1;elsereturn 0;int AccidenceAnalysis:IsAcceptantCharacter(char *p)/判断字符是否是字符集中的字char ch=*p;if(IsOperator(p)|IsUnsignedNum(p)|ch=E|ch=.)return 1;else return 0;void AccidenceAnalysis:IdentifyOperator(char *p)/对字符+,-,*,/,(,)分类识别char ch=*p;switch(ch) case +: Output(PLUS,p,p);break; case -: Output(SUBTRACT,p,p);break; case *: Output(MULTIPLY,p,p);break; case /: Output(DIVIDE,p,p);break; case (: Output(LEFTBRACKET,p,p);break; case ): Output(RIGHTBRACKET,p,p);break; default: break; void AccidenceAnalysis:AssortIdentify()/对字符分类识别coutt单词分析结果显示:nE+T| E-T|TT-T*F| T/F|FF-(E)|i2、语法分析程序编写设置输入缓冲区、状态栈、符号栈，并根据SLR（1）分析表利用某种语言（C语言或JAVA语言）直接编写移进、归约、接受子程序，编写语法分析程序。3、语法分析程序测试用于测试的实例源文件中应有语法正确的，也应有语法错误的符号串，以对照的形式将分析结果信息在输出文件中表示出来。四、实验程序#include #include #include #include using namespace std ;struct code_val char code;const char *p= /产生式 EE,EE+T,EE-T,ET,TT*F,TT/F,TF,F(E),Fi ;const char TNT =+-*/()i#ETF; /LR分析表列的字符const int M 11= 0,0,0,0,5,0,4,0,1,2,3, 7,6,0,0,0,0,0,17, -3,-3,10,12,0,-3,0,-3, -6,-6,-6,-6,0,-6,0,-6, -8,-8,-8,-8,0,-8,0,-8, 0,0,0,0,5,0,4,0,14,2,3, 0,0,0,0,5,0,4,0,0,8,3, 0,0,0,0,5,0,4,0,0,9,3, -2,-2,10,12,0,-2,0,-2, -1,-1,10,12,0,-1,0,-1, 0,0,0,0,0,0,4,0,0,0,11, -4,-4,-4,-4,0,-4,0,-4, 0,0,0,0,0,0,0,4,0,0,13, -5,-5,-5,-5,0,-5,0,-5, 7,6,0,0,0,15,0,0, -7,-7,-7,-7,0,-7,0,-7 ;int col(char); /列定位函数原型void main() int state50=0; /状态栈初值 int top=0; /栈顶指针初值 ifstream cin(E:lex_r.txt); struct code_val t; /结构变量，存放单词。 cint.code; do /读一单词 int action; action=Mstatetopcol(t.code); if(action0 & action!=17) /移进 state+top=action; cint.code; else if(action 0) /归约 top=top-(strlen(p-action)-3); /为汉字,占 2字节故减3 statetop+1=Mstatetopcol(p-action0); /产生式左部符号 top=top+1; else if(action=17) coutAcc;break; elsecouterr;break; while(1);int col(char c) /将字符+* ()i#ETF分别转换为数字012345678 for(int i=0;i(int)strlen(TNT);i+) if(c=TNTi)return i; coutcendl; exit(0); /终止程序运行 四、实验感想 SLR（1）文法有效地消除了规约和移进之间的冲突，在程序中设了两个堆栈，一个状态栈，一个符号栈。根据LR分析表构造了一个ACTION和矩阵，再用循环的方式把堆栈中的内容显示出来。实验三 语义分析程序实现一、实验目的与要求通过设计、编制、调试一个简单的语义处理分析程序，实现对实验一和实验二所得单词和语句的语义信息简单处里，进一步掌握语义处理的内容和简单方法。二、实验内容对实验一进行扩展，对识别的无符号数进行计值，并将输出形式改为（类别码，值）的二元式形式。对实验二进行扩展，在语法分析的基础上，增加语义操作来实现语法制导翻译。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，计算并输出算术表达式的值。将实验一与实验二的程序合并，以能对完整的输入源文件进行词法分析生成中间文件，然后进行语法制导翻译，输出最终翻译结果。输入：由无符号数和+，*，/, ( , ) 构成的算术表达式。输出：如果输入单词串是合法的无符号数的算术四则运算，输出运算结果，并且给出每一步的分析过程；如果不是无符号数的算术四则运算，输出“非法四则运算表达式”。三、基本实验题目对实验一中每个无符号数识别状态插入计值处理，最终获得无符号数的取值。对实验二进行扩展，在归约（分析表中的归约动作已经反应了运算优先级）处理子程序中加入计值处理，接受子程序中加入输出算数表达式值的处理。四、实验程序#include#include#include#includeusing namespace std;#define EndState -1char ACTION168=s,e,e,e,e,s,e,e,e,s,s,e,e,e,e,a,e,r,r,s,s,e,r,r,e,r,r,r,r,e,r,r,s,e,e,e,e,s,e,e,e,r,r,r,r,e,r,r,s,e,e,e,e,s,e,e,s,e,e,e,e,s,e,e,s,e,e,e,e,s,e,e,s,e,e,e,e,s,e,e,e,s,s,e,e,e,s,e,e,r,r,s,s,e,r,r,e,r,r,s,s,e,r,r,e,r,r,r,r,e,r,r,e,r,r,r,r,e,r,r,e,r,r,r,r,e,r,r;int GOTO1611=5,0,0,0,0,4,0,0,1,2,3,0,6,7,0,0,0,0,0,0,0,0,0,2,2,8,9,0,2,2,0,0,0,0,5,5,5,5,0,5,5,0,0,0,5,0,0,0,0,4,0,0,10,2,3,0,8,8,8,8,0,8,8,0,0,0,5,0,0,0,0,4,0,0,0,11,3,5,0,0,0,0,4,0,0,0,12,3,5,0,0,0,0,4,0,0,0,0,13,5,0,0,0,0,4,0,0,0,0,14,0,6,7,0,0,0,15,0,0,0,0,0,1,1,8,9,0,1,1,0,0,0,0,3,3,8,9,0,3,3,0,0,0,0,4,4,4,4,0,4,4,0,0,0,0,6,6,6,6,0,6,6,0,0,0,0,7,7,7,7,0,7,7,0,0,0,;int Stimulation168=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,2,2,0,5,5,5,5,0,5,5,0,0,0,0,0,0,0,0,0,8,8,8,8,0,8,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,3,3,0,0,0,3,3,0,4,4,4,4,0,4,4,0,6,6,6,6,0,6,6,0,7,7,7,7,0,7,7;class AccidenceAnnalysisprivate:char temp20;char *ptr;int Class;int CurrentState;char test20;float FCON;int w;int n;int p;int e;int d;public:int EXCUTE(int,char);void Push_temp(char);void Clear_temp(void);bool Operator(char);void Operator_Get(char);void Output(void);void Center();AccidenceAnnalysis();int result_class20;float result_value20;int *ptr_c;float *ptr_v;AccidenceAnnalysis:AccidenceAnnalysis()ptr=temp;Clear_temp();ptr_c=result_class;ptr_v=result_value;bool AccidenceAnnalysis:Operator(char c)if(c=+) return true;else if(c=-) return true;else if(c=*) return true;else if(c=/) return true;else if(c=() return true;else if(c=) return true;else if(c=0) return true;else return false;void AccidenceAnnalysis:Clear_temp(void)for(int i=0;i20;i+)tempi=0;void AccidenceAnnalysis:Push_temp(char c)*ptr=c;ptr+;int AccidenceAnnalysis:EXCUTE(int state,char c)if(state=0)if(c=0) CurrentState=1;d=c-0;n=0;w=d;p=0;e=1;if(Operator(c) CurrentState=EndState;Operator_Get(c);Push_temp(c);if(c=.) CurrentState=3;w=0;n=0;p=0;e=1;if(state=1)if(c=.) CurrentState=2;if(c=0)CurrentState=1;d=c-0;w=w*10+d;if(Operator(c)CurrentState=EndState;Class=1;FCON=w;if(c=E|c=e)CurrentState=4;if(state=2)if(c=0)CurrentState=2;d=c-0;w=w*10+d;n+;if(c=E|c=e) CurrentState=4;if(Operator(c)CurrentState=EndState;Class=1;FCON=w*pow(10,e*p-n);if(state=3)if(c=0) CurrentState=2;d=c-0;w=w*10+d;n+;if(state=4)if(c=+) CurrentState=5;if(c=-)e=-1;CurrentState=5;if(c=0) CurrentState=6;d=c-0;p=p*10+d;if(state=5)if(c=0) d=c-0;p=p*10+d;CurrentState=6;if(state=6)if(c=0)d=c-0;p=p*10+d;CurrentState=6;if(Operator(c)CurrentState=EndState;FCON=w*pow(10,e*p-n);Class=1;return CurrentState;void AccidenceAnnalysis:Operator_Get(char c)if(CurrentState=EndState)&(Operator(c)if(c=0) Class=0;if(c=+) Class=2;if(c=-) Class=3;if(c=*) Class=4;if(c=/) Class=5;if(c=() Class=6;if(c=) Class=7;void AccidenceAnnalysis:Output(void)switch(Class)case 1:coutFCONtt1n;*ptr_c=Class;*ptr_v=FCON;ptr_v+;ptr_c+;break;case 2:couttemptt2n;*ptr_c=Class;ptr_c+;break;case 3:couttemptt3n;*ptr_c=Class;ptr_c+;break;case 4:couttemptt4n;*ptr_c=Class;ptr_c+;break;case 5:couttemptt5n;*ptr_c=Class;ptr_c+;break;case 6:couttemptt6n;*ptr_c=Class;ptr_c+;break;case 7:couttemptest;CurrentState=0;cout词法分析过程如下:n;coutClassttValuen;for(int i=0;i20;i+)EXCUTE(CurrentState,testi);if(CurrentState!=EndState)Push_temp(testi);elseif(Class!=0) Output();CurrentState=0;Clear_temp();ptr=temp;if(testi!=0&Class=1) i-; class GrammarAnnalyseprivate:int status20;struct Annalyseint sta;float val;annalyse20,*a;int input20;int *s,*i,*i_end;int i_step;float value20,*v;public:GrammarAnnalyse();void Annalyse();string NumToChar(int*,int);char check_action(int*,int*);int check_goto(int*,int*);int check_stimulation(int*,int*);void Initilize(int,float);void Advance();void Stimulate();void Output();void Calculate();GrammarAnnalyse:GrammarAnnalyse()status0=0;annalyse0.sta=8;s=&status0;a=&annalyse0;i=&input0;i_end=&input0;v=&value0;i_step=1;void GrammarAnnalyse:Initilize(int a20,float b20)for(int i=0;i+)inputi=ai;if(inputi=8) break;i_end=&inputi;/8代表#for(i=0;i=0;n-)switch(*(t-n)case 1:temp+=i;i+;break;case 2:temp+=+;i+;break;case 3:temp+=-;i+;break;case 4:temp+=*;i+;break;case 5:temp+=/;i+;break;case 6:temp+=(;i+;break;case 7:temp+=);i+;break;case 8:temp+=#;i+;break;case 9:temp+=E;i+;break;case 10:temp+=T;i+;break;case 11:temp+=F;i+;break;return temp;void GrammarAnnalyse:Output()couti_stept;i_step+;int *s1=&status0;for(;s1=s;s1+)cout*s1;coutt;GrammarAnnalyse temp;temp.a=&annalyse0;int n=0,a_temp20,*a_temp_ptr=a_temp;for(;temp.asta;a_temp_ptr+;n+;string a_str=NumToChar(a_temp_ptr,n);couta_strt;n=0;int *i_temp;i_temp=i;for(;i_tempi_end;i_temp+)n+;string i_str=NumToChar(i_end,n);couti_strt;coutcheck_action(s,i);if(check_action(s,i)=r) coutcheck_stimulation(s,i);if(check_action(s,i)=s) coutcheck_goto(s,i);if(check_action(s,i)=a) coutcc;coutendl;cout_;coutsta=*i;s+;*s=check_goto(s-1,i);i+;Output();void GrammarAnnalyse:Stimulate()int t=check_stimulation(s,i);switch(t)case 1:a-sta=0;(a-1)-sta=0;(a-2)-sta=0;a=a-2;a-sta=9;a-val=a-val+(a+2)-val;*s=0;*(s-1)=0;*(s-2)=0;s=s-2;int *temp=&a-sta;*s=check_goto(s-1,temp);Output();break;case 2:a-sta=9;int *temp=&a-sta;*s=check_goto(s-1,temp);Output();break;case 3:a-sta=0;(a-1)-sta=0;(a-2)-sta=0;a=a-2;a-sta=9;a-val=a-val-(a+2)-val;*s=0;*(s-1)=0;*(s-2)=0;s=s-2;int *temp=&a-sta;*s=check_goto(s-1,temp);Output();break;case 4:a-sta=0;(a-1)-sta=0;(a-2)-sta=0;a=a-2;a-sta=10;a-val=a-val*(a+2)-val;*s=0;*(s-1)=0;*(s-2)=0;s=s-2;int *temp=&a-sta;*s=check_goto(s