词法分析-算符优先分析-课程设计

1、南华大学 计算机科学与技术学院课程设计 课程名称：编译原理 题 目：词法分析和算符优先分析 班 级：01班 学 号：20104030113 姓 名：段检妹 2012年5月24日 设计一：词法分析器1. 课程设计目的和要求11.1实验目的11.2实验要求12.设计描述23.函数模块35.测试样例与测试结果66. 结论7 设计二： 算符优先语法分析1.课程设计的目的和要求81.1 课程设计的目的81.2 课程设计的要求82.设计描述82.1 自底向上分析方法的描述：82.2算符优先文法的描述：93. 概要设计和详细设计104.1功能结构104.2模块的划分105.源代码115.测试样例与测试结果2

2、16. 结论22 设计一：词法分析器1. 课程设计目的和要求1.1实验目的通过完成词法分析程序，了解词法分析的过程。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。1.2实验要求通过词法分析器能够实现以下五种类型如单词等的识别。(1)关键字"begin","end","if","then","else","while","write",&qu

3、ot;read"等,"do", "call","const","char","until","procedure","repeat"等(2)运算符："+","-","*","/","="等(3)界符："","","","","",",&qu

4、ot;,".","(",")",":"等(4)标识符 (5)常量2.设计描述词法分析：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。表1 各种单词符号对应类型表单词符号类型编码助记符标识符1$SYMNOL常量2$CNSTANTint3$INTif4$IFelse5$ELSEwhile6

5、$WHILEfor7$FORread8$READwrite9$WRITE+10$ADD -11$SUB*12$MUL /13$DIV<14$L<=15$LE>16$G>=17$GE!=18$NE =19$E = 20$ASSIGN(21$LPAR)22$RPAR,23$COM;24$SEM3.函数模块1. LexAnalyz()函数实现整个分析的过程2.main主函数：主要实验将输入的字符串存进token中，和组织其他函数已完成功能。3. print()函数将识别的结果打印出来。4.设计源码#include<stdio.h>#include<strin

6、g.h>#include<ctype.h>#include<cstdlib>using namespace std;const char*reserchar7="int", "if", "else", "while", "for", "read", "write" ; /关键字 const char*rememchar25="","$SYMBOL", "$CNSTANT&quo

7、t;, "$INT", "$IF", "$ELSE", "$WHILE", "$FOR", "$READ", "$WRITE", "$ADD", "$SUB", "$MUL", "$DIV", "$L", "$LE", "$G", "$GE", "$NE", "$E&q

8、uot;, "$ASSIGN", "$LPAR", "$RPAR", "$COM", "$SEM" ; /助记符 void LexAnalyz();void Print();char prog100;char token10;int syn,p;char ch;int main() char sym; Print(); p=0; do ch=getchar(); progp+=ch; while( ch!='#' ); p=0; do LexAnalyz(); if( syn=-

9、1 ) printf("errorn"); else if( syn!=0 ) printf("%s %d %sn", token, syn, rememcharsyn); / system("pause") ; while( syn!=0 ); system("pause"); return 0;void LexAnalyz() int j=0,i=0; syn=0; for( i=0; i<10; i+) tokeni='0' ch=progp+; while( ch =' 

10、9; ) ch= progp+; if(isalpha( ch ) while(isalpha( ch ) | isdigit( ch ) tokenj+ = ch; ch= progp+ ; ch=progp-; syn=1; for( i=0; i<7; i+ ) if( strcmp( token, reserchari)=0 ) syn=i+3; break; else if( isdigit( ch ) ) while( isdigit( ch ) ) tokenj+ = ch; ch = progp+; ch= progp-; syn=2; else switch( ch )

11、 case '<': tokenj+ = ch; ch = progp+; if( ch = '=' ) tokenj+ = ch; syn=15; else syn=14; ch= progp-; break; case '>': tokenj+ = ch; ch = progp+; if( ch = '=' ) tokenj+ = ch; syn=17; else syn=16; ch= progp-; break; case '!': tokenj+ = ch; ch = progp+; if(c

12、h = '=') tokenj+ = ch; syn=18; else ch= progp-; break; case '=': tokenj+ = ch; ch = progp+; if( ch = '=' ) tokenj+ = ch; syn=19; else ch= progp-; syn=20; break; case '+': tokenj+=ch; syn=10; break; case '-': tokenj+=ch; syn=11; break; case '*': tokenj+

13、=ch; syn=12; break; case '/': tokenj+=ch; syn=13; break; case '(': tokenj+=ch; syn=21; break; case ')': tokenj+=ch; syn=22; break; case ',': tokenj+=ch; syn=23; break; case '': tokenj+=ch; syn=24; break; case '#': syn=0; break; default: syn=-1; void Pr

14、int() for(int i=0; i<=25; i+ ) printf("*"); printf("n"); for(int i=0; i<=8; i+ ) printf(" "); printf("词法分析器n"); for(int i=0; i<=25; i+ ) printf("*"); printf("n"); printf("输入一串句子以#+enter键结束：n");5.测试样例与测试结果输入的是字符串；识别出的是单词，且

15、输出单词的类别编码和助记符。6. 结论 通过本次课程设计的练习，熟悉了用C+语言编写词法分析器的过程，掌握了词法分析器的原理以及功能。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序的主要任务：读源程序，产生单词符号。 词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，等等等等。词法分析工作从语法分析工作独立出来的原因：简化设计，改进编译效率，增加编译系统的可移植性 。而且从划分关键字，运算符，界符，标识符和常量，才发现数字，字母及符号组合有很多很

16、多，无法全部枚举，所以在新建的文本文档中只象征性的列出几种符号，但这并不影响此法分析结果的完成。总之，通过本次实验，一点点分析词法分析器的功能，并努力实现它，掌握了课程设计内容的同时也锻炼了自己分析解决问题的能力以及编程能力，收获颇丰！ 设计二： 算符优先语法分析1.课程设计的目的和要求1.1 课程设计的目的 本次设计的时间为一个月，目的是件通过使用高级语言实现部分加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应蕴含本课程内容和世纪应用相关的主要技术。1.2 课程设计的要求1. 文法使用产生式来定义；2. 用大写字母和小写字母分别表示非终结符和终结符；产生式使用->；3. 文

17、法中的空字符串统一使用表示；4. 分别给出每一个终结符的FIRSTVT 集和LASTVT集；5. 版定给定的文法是否是算符优先文法；6. 画出算符优先关系表；、7. 给定富豪穿是否是文法中的句子，分析过程用分析表格的方式打印出来。2.设计描述本次实验使用windows vista操作系统下visiual c+6.0平台，使用c语言，利用读文件方式将待分析的文法读入到程序中，通过定义数组和结构体作为具有一定意义或关系的表或栈，存放FIRSTVT 、LASTVT、算符有限关系表的元素。系统能够对由文件读入的文法进行分析，构造出FIRSTVT LASTVT表以及算符优先关系表。可以根据构造的有限关系

18、表对输入的任意字符串进行分析，判断是否为本文法的句子，若是则打印归约过程。结果显示到DOS界面上。2.1 自底向上分析方法的描述：对输入的字符串自左向右进行扫描，并将输入字符逐个移入栈中，边移入边分析，一旦栈顶富豪穿形成摸个矩形的句柄时（该句柄对应某个产生式的右部），就用该产生式的非终结符代替邮编的文法字符串，这一过程成为归约。重复这一过程，知道栈中只剩下文法的开始负责分析成功。2.2算符优先文法的描述：之规定酸腐之间的优先关系，也就是说只考虑终结符之间的有限关系。由于算符优先分析不考虑终结符之间的优先关系，在归约过程中只要找到最左素短语就可以规约了。如给定一个文法GS：S->#E#E-

19、>E+TE->TT->T*FT->FF->(E)F->i利用算符优先文法分析过程处理如下：1. 计算给定文法中任意两个终结符对（a,b）之间的优先关系，首先计算两个几何FIRSTVT(B)=b|B->b.或B->Cb.LASTVT(B)=a|B->.a或B->.aC2.构造firstvt和lastvt集下表是FIRSTVT集和LASTVT集根据firstvt 和lastvt集构造算符优先关系表下表是算符优先关系表3.进行移进和归约3. 概要设计和详细设计4.1功能结构4.2模块的划分1. 文件的导入：int ReadFile(char

20、 expcol); 文法以文件的形式输入而且保存在二维数组中。2. Firstvt和Lastvt集的构造：void FirstVT(char expcol,char firstvtcol,const int&exp_len,const int&first_len); /构造firstvt集void LastVT(char expcol,char lastvtcol,const int&exp_len,const int&first_len); /构造lastvt集3. 算符优先关系表的构造：bool OperPriTable(char expcol,char o

21、pertablecol,char firstvtcol,char lastvtcol,int exp_len,int first_len,int&oper_len);/构造算符优先表如果不是算符优先文法则返回false。4. 归约的过程：bool GuiYue(char input,char opertablecol,char expcol,int oper_len,int exp_len); /在其他的小函数的帮助下归约 5. 主函数Main函数,将模块组合，完成整个设计的功能。5.源代码#include<iostream>#include<fstream>#

22、include<stack>#define col 50#define row 50 using namespace std; struct Element char nont; /非终结符 char ternal; /终结符 ;void Init(char expcol,char firstvtcol,char lastvtcol,int&exp_len,int&first_len); /first和lastvt的非终结符bool FindRecord(Element record,Element &a, int &r); /在构造first集时，

23、判断是否已经添加了A->a bool TerminalJug(char ch); /判断是否是终结符 void FirstVT(char expcol,char firstvtcol,const int&exp_len,const int&first_len); /构造firstvt集void LastVT(char expcol,char lastvtcol,const int&exp_len,const int&first_len); /构造lastvt集int ReadFile(char expcol); /文法以文件的形式输入bool Insert

24、Table(char opertablecol,int&i,int&j,char oper); int FindItem( char firstvtcol,int first_len,char ch); /判断此终结符是否在firsrvt集 0列中int FindPosition(char term,const char&c1,const int&term_len) ;bool OperPriTable(char expcol,char opertablecol,char firstvtcol,char lastvtcol,int exp_len,int fir

25、st_len,int&oper_len); /构造算符优先表void Print(char arraycol,int r); /输出查看 bool GuiYue(char input,char opertablecol,char expcol,int oper_len,int exp_len); /归约函数 char Match(char sk,int s,int e,char expcol,int&exp_len); /在产生式中查找匹配式子并返回规约后的非终结符 int main() char firstvtrowcol='0',lastvtrowcol=&

26、#39;0' char exprowcol='0',opertablerowcol='0' int first_len,exp_len,oper_len; exp_len=ReadFile(exp); Init(exp,firstvt,lastvt,exp_len,first_len); FirstVT(exp,firstvt,exp_len,first_len); cout<<"nt文法中非终结符的firstvt集： "<<endl; cout<<"*"<<endl

27、; Print(firstvt,first_len); LastVT(exp,lastvt,exp_len,first_len); cout<<"nt文法中非终结符的lastvt集： "<<endl; cout<<"*"<<endl; Print(lastvt,first_len); if( OperPriTable(exp,opertable,firstvt,lastvt,exp_len,first_len,oper_len) ) cout<<"nt算符优先分析表： "&l

28、t;<endl; cout<<"*"<<endl; Print(opertable,oper_len); cout<<endl; char inputcol='0' cout<<"输入要分析的串 （以#+enter键结束）："<<endl; cin>>input; cout<<"tt分析过程描述 "<<endl; if( GuiYue(input,opertable,exp,oper_len,exp_len) ) co

29、ut<<"该句型符合算符优先文法"<<endl; else cout<<"该句型不符合算符优先文法,是个错误的句子"<<endl; /C:UserspeanutDesktop编译原理文法.txt return 0;void FirstVT(char expcol,char firstvtcol,const int&exp_len,const int&first_len) /构造firstvt集 int i,recor_len; stack<Element> expstack; E

30、lement temp; Element recordcol; recor_len=0; for( i=0; i<exp_len; i+) /第一次扫描得出的A->a入栈 for( int j=3; expij!='0' j+) if( TerminalJug( expij ) ) /判断是否是终结符 temp.nont=expi0; temp.ternal=expij; if( recor_len=0 | !FindRecord(record,temp, recor_len) ) /没记录就添加到记录 expstack.push(temp); recordreco

31、r_len.nont=temp.nont; recordrecor_len.ternal=temp.ternal; recor_len+; break; Element DL,DE; int locationcol; /用来记录firstvt集中每行的长度 for( i=0; i<first_len; i+) locationi=1; while( !expstack.empty() ) DE=expstack.top(); / cout<<DE.nont<<"->"<<DE.ternal<<endl; expst

32、ack.pop(); for( i=0; i<first_len; i+) /将终结符加到相应firstvt集中 if( firstvti0 = DE.nont ) int len=locationi; firstvtilen=DE.ternal; locationi+; break; for( i=0; i<exp_len; i+) /找出能推出相应非终结符的产生式 规律二: A->B if( expi3=DE.nont ) DL.nont=expi0; DL.ternal=DE.ternal; if( !FindRecord(record, DL, recor_len)

33、)/没记录就添加到记录 expstack.push(DL); recordrecor_len.nont=DL.nont; recordrecor_len.ternal=DL.ternal; recor_len+; void LastVT(char expcol,char lastvtcol,const int&exp_len,const int&first_len) /构造lastvt集 int i,j,k; char ch; char temprowcol='0' for( i=0; i<exp_len; i+) for( j=0; expij!=

34、9;0' j+) tempij=expij; j-; for( k=3; k<j; k+,j-) ch=tempik; tempik=tempij; tempij=ch; FirstVT(temp,lastvt,exp_len,first_len); void Init(char expcol,char firstvtcol,char lastvtcol,int&exp_len,int&first_len)/first和lastvt的非终结符 first_len=0; for( int i=0; i<exp_len; i+) if( TerminalJug(

35、expi0) = false && FindItem(firstvt,first_len,expi0) = -1 ) firstvtfirst_len0=expi0; lastvtfirst_len0=expi0; first_len+; int ReadFile(char expcol) /文法以文件的形式输入 ifstream fin; int i; char address30; cout<<"输入文件的路径："<<endl; cin>>address; cout<<endl; fin.open(addr

36、ess,ios:in); if(!fin) cout<<"file can not be opened!"<<endl; else cout<<"t文法的中表达式:"<<endl; cout<<"*"<<endl; for( i=0; !fin.eof(); i+) /表达式的输入 fin>>expi; cout<<expi<<endl; fin.close(); return i; /返回表达式的行数 int FindItem

37、(char firstvtcol,int first_len,char ch) /判断此终结符是否在firsrvt集 0列中 for(int i=0; i<first_len; i+) if( firstvti0=ch ) return i; return -1; bool FindRecord(Element record,Element &a, int &recor_len) /判断是否有记录 for( int k=0; k<recor_len; k+) if( recordk.nont=a.nont && recordk.ternal=a.te

38、rnal ) return true; return false; bool TerminalJug(char ch) if( ch>='A' && ch<='Z') return false; return true;bool OperPriTable(char expcol,char opertablecol,char firstvtcol,char lastvtcol,int exp_len,int first_len,int&oper_len) /构造算符优先表 char termcol='0' int

39、 term_len=0,i,j,k; int r,c,p; for( i=0; i<exp_len; i+) /得到所有终结符 for( j=3; expij!='0' j+) if( TerminalJug(expij) && !FindPosition(term,expij,term_len) ) termterm_len+=expij; oper_len=term_len+1; for( i=0; i<term_len+1; i+) for( j=0; j<term_len+1; j+) opertableij=' ' f

40、or( i=1; i<term_len+1; i+) /初始化表头 opertablei0=termi-1; opertable0i=termi-1; for( i=0; i<exp_len; i+) for( j=5; expij!='0' j+) / 等于关系 if(TerminalJug(expij-2)&&!TerminalJug(expij-1)&& TerminalJug(expij) ) / cout<<expij-2<<' '<<expij-1<<'

41、; '<<expij<<endl; r=FindPosition(term,expij-2,term_len); c=FindPosition(term,expij,term_len); if( !InsertTable(opertable, r, c, '=') ) cout<<"不是算符优先文法！"<<endl; return false; for( i=0; i<exp_len; i+) for( j=4; expij!='0' j+) if( TerminalJug(exp

42、ij-1) && TerminalJug(expij) ) /相邻两个终结符的等于关系 r=FindPosition(term,expij-1,term_len); c=FindPosition(term,expij,term_len); if( !InsertTable(opertable, r, c, '=') ) cout<<"不是算符优先文法！"<<endl; return false; / Print(opertable,term_len+1); if( TerminalJug(expij-1) && !TerminalJug(expij) ) /小于