编译原理词法分析与语法分析实验报告

1、实 验 三 词法分析与语法分析程序设计实验日期: 2011 年 11 月 11日 评分 批阅教师签字 一、实验目的基本掌握计算机语言的词法分析程序和语法分析程序的设计方法二、实验内容实验要求：1根据以下的正规式，画出状态图；标识符：(|)*关键字：if then else while do十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）* 运算符和分隔符：+ - * / = ( ) ；2根据状态图，设计词法分析函数int scan( )，从键盘读入数据，分析出一个单词。3对于只含有+、*运算的算术表达式的如下文法，编写相应的语法分析程序，要求

2、用LL(1)分析表实现，并以id+id*id为例进行测试：E TE E +TE| T FTT *FT|F （E）| id实验步骤1根据状态图，设计词法分析算法2采用C+语言，实现该算法3调试程序：输入一组单词，检查输出结果。4 编制给定文法的非递归的预测分析程序，并加以测试。三、实验环境计算机、Windows 操作系统、Visual C+ 程序集成环境。四、实验原理（或程序框图）及步骤LL(1)中的第一个L表示从左到右扫描输入，第二个L表示产生最右推导，而1则表示在每一步中只需要向前看一个输入符号来决定语法分析动作。构造一个预测分析表如下：输入：文法G输出：预测分析表 M方法：对于文法G的每个

3、产生式A，进行如下处理：1）：对于FIRST（）中的每个终结符a，将A加入到MA, 中。2）：如果在FIRST（）中，那么对于FOLLOW（A）中的每个终结符b，将A加入到MA, 中。如果在FIRST（）中，且$在FOLLOW（A）中，也将A加入到MA, $中。完成上面操作之后，如果MA, 中没有产生式，那么将MA, 设置为error。五、程序源代码词法分析函数：struct key_kord char *word;int id;key_word keyword=if,1,then,2,else,3,while,4,do,5,integer,16;void scan (FILE *ftp)ch

4、ar temp_char;int i,c;while(!feof(ftp)temp_char=fgetc(ftp);if(isalpha(temp_char) TOKEN0=temp_char;temp_char=fgetc(ftp);i=1;while(isalnum(temp_char) TOKENi=temp_char;i+;temp_char=fgetc(ftp);TOKENi=0;fseek(ftp,-1,1);c=lookup(TOKEN);if(c=0) out (ID,TOKEN);elseout (c, );else if(isdigit(temp_char)TOKEN0=t

5、emp_char;temp_char=fgetc(ftp);i=1;while(isdigit(temp_char)TOKENi=temp_char;i+;temp_char=fgetc(ftp);TOKENi=0;fseek(ftp,-1,1);out(INT,TOKEN);elseswitch(temp_char)case ) out(NE, );elsefseek(ftp,-1,1);out(LT, );break;case =: out(EQ, ); break;case : temp_char=fgetc(ftp);if(temp_char=)out(GE, );elsefseek(

6、ftp,-1,1);(GT, );break;case : temp_char=fgetc(ftp);if(temp_char=) out(FZ, );elsefseek(ftp,-1,1);report_error(temp_char);break;case /: temp_char=fgetc(ftp); if(temp_char=/)dotemp_char=fgetc(ftp);while(temp_char!=n);graphnum+;elsefseek(ftp,-1,1);out(DEV, );break;case : break; case n: graphnum+; break;

7、 case : break; case -1 : break; default : report_error(temp_char);break;return;LL（1）算法实现：#define MAXSYMBOL 30temp_charar NT=E,A,T,B,F;temp_charar TE=i,+,*,(,(,);temp_charar *analysisTableMAXSYMBOL3= E,i,TG,E,+,E,*,E,(,TG,E,),E,#, A,i,A,+,+TA,A,*,A,(,A,),$,A,#,$, T,i,FB,T,+,T,*,T,(,FB,T,),T,#, B,i,B,

8、+,$,B,*,*FB,B,(,B,),$,B,#,$, F,i,i,F,+,F,*,F,(,(E),F,),F,#,;int Stack_Count(HEADSTACK *head) int count=0; if(head-stackHead=NULL) return 0; TEMP_CHARARSTACK *currentNode=head-stackHead; while(currentNode!=NULL) currentNode=currentNode-nextNode; count+; return count;HEADSTACK *Stack_Init() HEADSTACK

9、*headNode=(HEADSTACK *)malloc(sizeof(HEADSTACK); headNode-stackHead=NULL; return headNode;void Stack_Push(HEADSTACK *head,temp_charar temp_char) TEMP_CHARARSTACK *currentNode,*tail; tail=(TEMP_CHARARSTACK *)malloc(sizeof(TEMP_CHARARSTACK); tail-temp_char=temp_char; tail-nextNode=NULL; if(head-stackH

10、ead=NULL) head-stackHead=tail; return; currentNode=head-stackHead; while(currentNode-nextNode!=NULL) currentNode=currentNode-nextNode; currentNode-nextNode=tail; currentNode=tail; currentNode-nextNode=NULL;TEMP_CHARARSTACK Stack_Pop(HEADSTACK *head) TEMP_CHARARSTACK *currentNode,*tail,popNode; if(he

11、ad-stackHead=NULL) printf(Error:The Stack does not has noden); return popNode; currentNode=tail=head-stackHead; if(tail-nextNode=NULL) popNode.temp_char=tail-temp_char; popNode.nextNode=NULL; head-stackHead=NULL; return popNode; while (tail-nextNode!=NULL) tail=tail-nextNode; if(tail-nextNode=NULL)

12、currentNode-nextNode=NULL; popNode.temp_char=tail-temp_char; popNode.nextNode=tail-nextNode; return popNode; currentNode=currentNode-nextNode; bool IsNT(temp_charar temp_char) for(int i=0;isizeof(NT)/sizeof(temp_charar);i+) if(temp_char=NTi) return true; return false;bool IsTE(temp_charar temp_char) for(int i=0;isizeof(TE)/sizeof(temp_charar);i+) if(temp_char=TEi) return true; return false; temp_charar* GetMatrixValue(temp_charar NT,temp_charar TE) temp_charar nt2,te2; nt0=NT; nt1=0; te0=TE; te1=0; for(int i=0;i-1;j-) Stack_Push(head,concludej); e