词法分析程序实现

1、实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。输入：由无符号数和+，*，/, ( , ) 构成的算术表达式，如1.5E+2100。输出：对识别出的每一单词均单行输出其类别码（无符号数的值暂不要求计算）。三、实现方法与环境1、首先设计识别各类单词的状态转换图。描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0，1，2，6代表非终结符号<无符号数>

2、;、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。图1 文法G<无符号数>的状态转换图其中编号0，1，2，6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。在一个程序设计语言中，一般都含有若干类

3、单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。四则运算算术符号的识别很简单，直接在状态图的0状态分别引出相应标记的矢线至一个新的终态即可。根据自己的习惯，也可以将其转换为状态矩阵形式。2、词法分析程序编写根据描述语言中各类单词的文法状态转换图或状态矩阵，利用某种语言（C语言或JAVA语言）直接编写词法分析程序。3、词法分析程序测试用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串，对于输入的测试用例的源程序文件，以对照的形式将扫描器的分析结果信息在

4、输出文件中表示出来。四、 源程序#include<iostream>using 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;

5、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(

6、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;i<M;i+)testStri='0'

7、;p=&testStr0; /指针P指向字符数组首元素AccidenceAnalysis:AccidenceAnalysis()/析构函数void AccidenceAnalysis:InputStr()/输入函数cout<<"t输入待分析单词"<<M-1<<"字符以内："char ch;int i=0;while(ch=cin.get()!='n')testStri=ch;i+;void AccidenceAnalysis:Output(int a,char *p1,char *p2)/输出函

8、数cout<<"t类别码："<<a<<"t 单词值："while(p1<=p2)cout<<*p1;p1+;cout<<endl;int AccidenceAnalysis:IsOperator(char *p)/判断字符是否是字符集+,-,*,/,(,)中的字char ch=*p;if(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')')return 1;els

9、ereturn 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

10、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

11、(LEFTBRACKET,p,p);break; case ')': Output(RIGHTBRACKET,p,p);break; default: break; void AccidenceAnalysis:AssortIdentify()/对字符分类识别cout<<"t单词分析结果显示:n"<<endl; while(*p!='0') if(IsOperator(p) IdentifyOperator(p+); continue; else if(IsUnsignedNum(p)|*p='.')

12、char *p1=p;if(IsUnsignedNum(p)while(IsUnsignedNum(p)p+;if(*p='0')Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else if(*p='E')p+;if(IsUnsignedNum(p)while(IsUnsignedNum(p)p+;Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else if(*p='+'|*p='-')p+;while(IsUnsignedNum(p)p+;Output(UN

13、SIGNEDNUMBER,p1,-p);p+;continue;elseOutput(INEFFICACIOUSLABEL,p1,-p);p+;continue;else if(*p='.')p+;while(IsUnsignedNum(p)p+;if(*p='0')Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else if(*p='E')p+;if(IsUnsignedNum(p)while(IsUnsignedNum(p)p+;Output(UNSIGNEDNUMBER,p1,-p);p+;continu

14、e;else if(*p='+'|*p='-')p+;if(IsUnsignedNum(p)while(IsUnsignedNum(p)p+;Output(UNSIGNEDNUMBER,p1,-p);p+;continue;elseOutput(INEFFICACIOUSLABEL,p1,-p);p+;continue;elseOutput(INEFFICACIOUSLABEL,p1,-p);p+;continue;elseOutput(UNSIGNEDNUMBER,p1,-p);p+;continue;else Output(UNSIGNEDNUMBER,p1

15、,-p);p+;continue;if(*p='.')p+;if(IsUnsignedNum(p)p+;while(IsUnsignedNum(p)p+;if(*p='0')Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else if(*p='E')p+;if(IsUnsignedNum(p)while(IsUnsignedNum(p)p+;Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else if(*p='+'|*p='-')p+;whil

16、e(IsUnsignedNum(p)p+;Output(UNSIGNEDNUMBER,p1,-p);p+;continue;else Output(UNSIGNEDNUMBER,p1,-p);p+;continue;elseOutput(INEFFICACIOUSLABEL,p1,-p);p+;continue; else if(*p='E') Output(INEFFICACIOUSLABEL,p,p); p+; continue; void AccidenceAnalysis:StartAccidenceAnalysis()/开始分析函数AccidenceAnalysis

17、accidenceanalysis;accidenceanalysis.InputStr();accidenceanalysis.AssortIdentify();int main()AccidenceAnalysis:StartAccidenceAnalysis();return 0; 五、实验感想通过此次实验，加深对词法分析原理的理解；熟悉了构造词法分析程序的手工方式的相关原理，根据识别语言单词的状态转换图，使用某种高级语言直接编写此法分析程序。另外，也让我重新熟悉了C+语言的相关内容，加深了对C+语言的用途的理解。实验二 语法分析程序实现一、实验目的与要求通过设计、编制、调试典型的SLR

18、（1）语法分析程序，实现对实验一所得词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。二、实验内容选择对各种常见高级程序设计语言都较为通用的语法结构无符号数的算术四则运算作为分析对象，给出其文法描述（注意应与所采用的语法分析方法比较贴近），设计并实现一个完整的语法分析程序。输入：由实验一输出的单词类别串，如1，3，1。输出：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，则输出“RIGHT”，并且给出每一步归约的过程；如果不是句子，即输入串有错误，则输出“ERROR”，并且显示已经归约出的各个文法符号，以及必要的出错说明信息。三、实现方法与环境1、

19、首先根据算术四则运算的语法定义，构造SLR（1）分析表。无符号数的算术四则运算的语法可表示为：E->E+T| E-T|TT->T*F| T/F|FF->(E)|i2、语法分析程序编写设置输入缓冲区、状态栈、符号栈，并根据SLR（1）分析表利用某种语言（C语言或JAVA语言）直接编写移进、归约、接受子程序，编写语法分析程序。3、语法分析程序测试用于测试的实例源文件中应有语法正确的，也应有语法错误的符号串，以对照的形式将分析结果信息在输出文件中表示出来。四、实验程序#include <fstream>#include <iostream>#include

20、<stdlib.h>#include <string>using namespace std ;struct code_val char code;const char *p= /产生式 "E'E","EE+T","EE-T","ET","TT*F","TT/F","TF","F(E)","Fi" ;const char TNT ="+-*/()i#ETF" /LR

21、分析表列的字符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,

22、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; /结构变量，存放单词。 cin>>t.code; do /读一单词 int action; action=Mstatetopcol(t.code); i

23、f(action>0 && action!=17) /移进 state+top=action; cin>>t.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) cout<<"Acc"break; elsecout<<"err"

24、;break; while(1);int col(char c) /将字符+* ()i#ETF分别转换为数字012345678 for(int i=0;i<(int)strlen(TNT);i+) if(c=TNTi)return i; cout<<"Err in col char>"<<c<<endl; exit(0); /终止程序运行 四、实验感想 SLR（1）文法有效地消除了规约和移进之间的冲突，在程序中设了两个堆栈，一个状态栈，一个符号栈。根据LR分析表构造了一个ACTION和矩阵，再用循环的方式把堆栈中的内容显示出来

25、。实验三 语义分析程序实现一、实验目的与要求通过设计、编制、调试一个简单的语义处理分析程序，实现对实验一和实验二所得单词和语句的语义信息简单处里，进一步掌握语义处理的内容和简单方法。二、实验内容对实验一进行扩展，对识别的无符号数进行计值，并将输出形式改为（类别码，值）的二元式形式。对实验二进行扩展，在语法分析的基础上，增加语义操作来实现语法制导翻译。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，计算并输出算术表达式的值。将实验一与实验二的程序合并，以能对完整的输入源文件进行

26、词法分析生成中间文件，然后进行语法制导翻译，输出最终翻译结果。输入：由无符号数和+，*，/, ( , ) 构成的算术表达式。输出：如果输入单词串是合法的无符号数的算术四则运算，输出运算结果，并且给出每一步的分析过程；如果不是无符号数的算术四则运算，输出“非法四则运算表达式”。三、基本实验题目对实验一中每个无符号数识别状态插入计值处理，最终获得无符号数的取值。对实验二进行扩展，在归约（分析表中的归约动作已经反应了运算优先级）处理子程序中加入计值处理，接受子程序中加入输出算数表达式值的处理。四、实验程序#include<iostream>#include<stdlib.h>

27、#include<cmath>#include<string>using namespace std;#define EndState -1char ACTION168='s','e','e','e','e','s','e','e','e','s','s','e','e','e','e','a','e'

28、,'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'

29、,'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'

30、,'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'

31、,'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'

32、,'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

33、,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

34、,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

35、;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_t

36、emp();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=&

37、#39;0') return true;else return false;void AccidenceAnnalysis:Clear_temp(void)for(int i=0;i<20;i+)tempi='0'void AccidenceAnnalysis:Push_temp(char c)*ptr=c;ptr+;int AccidenceAnnalysis:EXCUTE(int state,char c)if(state=0)if(c<='9'&&c>='0') CurrentState=1;d=c

38、-'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<='9'&&c>='0')CurrentState=1;d=c-'0'w=w*10+d;if(Operator(c)CurrentState

39、=EndState;Class=1;FCON=w;if(c='E'|c='e')CurrentState=4;if(state=2)if(c<='9'&&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&

40、lt;='9'&&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<='9'&&c>='0') CurrentState=6;d=c-'0'p=p*10+d;if(state=5)if(c<='9'&&c>

41、;='0') d=c-'0'p=p*10+d;CurrentState=6;if(state=6)if(c<='9'&&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=End

42、State)&&(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:cout<<FCON<<"tt1n

43、"*ptr_c=Class;*ptr_v=FCON;ptr_v+;ptr_c+;break;case 2:cout<<temp<<"tt2n"*ptr_c=Class;ptr_c+;break;case 3:cout<<temp<<"tt3n"*ptr_c=Class;ptr_c+;break;case 4:cout<<temp<<"tt4n"*ptr_c=Class;ptr_c+;break;case 5:cout<<temp<<

44、;"tt5n"*ptr_c=Class;ptr_c+;break;case 6:cout<<temp<<"tt6n"*ptr_c=Class;ptr_c+;break;case 7:cout<<temp<<"tt7n"*ptr_c=Class;ptr_c+;break;void AccidenceAnnalysis:Center()Clear_temp();cin>>test;CurrentState=0;cout<<"词法分析过程如下:n"c

45、out<<"ClassttValuen"for(int i=0;i<20;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

46、;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

47、 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代表'#'f

48、or(i=0;i<20;i+)valuei=bi;char GrammarAnnalyse:check_action(int *s,int *t)return ACTION*s*t-1;int GrammarAnnalyse:check_goto(int *s,int *t)return GOTO*s*t-1;int GrammarAnnalyse:check_stimulation(int *s,int *t)return Stimulation*s*t-1;string GrammarAnnalyse:NumToChar(int *t,int n)string temp;int i=

49、0;for(;n>=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+="#&quo

50、t;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()cout<<i_step<<'t'i_step+;int *s1=&status0;for(;s1<=s;s1+)cout<<*s1;cout<<'t'GrammarAnnalyse te

51、mp;temp.a=&annalyse0;int n=0,a_temp20,*a_temp_ptr=a_temp;for(;temp.a<=a;temp.a+)a_tempn=temp.a->sta;a_temp_ptr+;n+;string a_str=NumToChar(a_temp_ptr,n);cout<<a_str<<'t'n=0;int *i_temp;i_temp=i;for(;i_temp<i_end;i_temp+)n+;string i_str=NumToChar(i_end,n);cout<<i

52、_str<<'t'cout<<check_action(s,i);if(check_action(s,i)='r') cout<<check_stimulation(s,i);if(check_action(s,i)='s') cout<<check_goto(s,i);if(check_action(s,i)='a') cout<<"cc"cout<<endl;cout<<"_"cout<<en

53、dl;void GrammarAnnalyse:Advance()a+;a->sta=*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=&am

54、p;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,t