实验一词法分析(共10页).doc

《实验一词法分析(共10页).doc》由会员分享，可在线阅读，更多相关《实验一词法分析(共10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上编译原理实验一 词法分析1.实验目的通过实验掌握词法分析的理论、原理和方法，为语法分析做准备。2.实验内容: a) 十六进制数识别器：规定是：必须以十六进制数字打头，以H结尾，十六进制数中允许使用的数字为0-9，字母为A，B，C，D，E, F(分别表示015)。试设计一个DFA，使它能识别无符号的十六进制整数，并编制相应的识别程序。输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。输出：标识出规范的符号串与不合规范的符号串。b) 词法分析：设计、编制、调试一个识别一个Little语言单词的词法分析程序（见附录1）。输入：学生自行确定符号串的输入形式

2、，如键盘输入、文本文件、字符数组等。输出：二元组。3.实验要求：(1) 上机前编写完整的实验报告，报告中要体现分析设计实现等几个过程；如无实验报告，则取消本次上机资格，实验成绩以0分记。(2) 严禁相互抄袭，否则实验成绩以0分记；(3) 有完整的源代码，源码有规范的注释，无明显的语法错误；4.实验步骤(1) 分析与设计a、文法：该语言的十六进制，如：0aH，77H，7BH等由以数字打头及以H结尾；该语言的标识符，如：Num，a3，go等由A到Z(or a到z)和0至9所组成；该语言的无符号的十进制，如：8，90，123等由0到9之间的任意数字组成。由以上可得出该语言的文法可表示如下：G(S)

3、= (VN，VT，P，S)其中VN=S，X，Y，Z，M，W，VT= 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,G,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z= 0|1| 2|3|4|5|6|7|8|9= a|b|c|d|e|f|A|B|C|D|E|F=g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|G|H|I|G|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|ZSX|Y|ZX|MM|M|Y|Y

4、ZH|WHW|W|可见，上式方法中，X表示出了语言的标识符，而Y表示出了语言的无符号的十进制，Z表示出了语言中的十六进制。上式G(S)文法中，各式右边只有单个的终结符号显然，以上文法G(S)已是正规文法。(2)正规文法转成正规式：具体步骤如下：M|M 可表示为M*W|W可表示为W*Z|Z可表示为Z* 转换成正规表达式为：S=| * |H | *H |*代入可得：S= (|) | (|) (|)*(|) |H | (|)*(|)H |*(3)正规式转成NFA（分裂法）初始的NFA图下所示：图1初始NFA图经过替换规则替换后得到的最终NFA图如下所示：图2最终的NFA图(4)NFA转成DFA及DF

5、A最小化（造表法）对应以上的NFA图，我们可用造表法来表示如下：显然，由图可看出，状态2与状态5等价，而状态1与状态3等价，这里省去状态3和状态5，并将所以指向状态3的状态都指向状态1，指向状态5的都指向状态2。由此可画出最小化的DFA图如下：图3最小化的DFA图可见，终结状态1表示出了无符号的十进制，终结状态2表示出了标识符，状态6表示出了十六进制的整数。b、单词的BNF表示 - -| | - - | - + - - - - =由此可知，需将单词分为五种：关键字1标识符2常数3运算符4分隔符5printfa0+,mainb1_;intc2*(ifstudent3/)thensum4=else

6、k5returnm6=8=9!=(2) 编码实现a、#include main(int argc,char *argv)int i,j,state,ERROR=-1; /* state控制状态的转移 1表示09数字， 2表示字母，4表示af，6表示H，0为未输入状态* ERROR=-1表示未输入任何字符串 =1表示输入出错*/char c; /* 暂时存放所取得的一个字符 */char *string=,Unsigned Integer,Identifier,Hex;/*输出结果时用*/for(i=1;i=0&c=a&c=A&c=0&c=a&c=A&c=a&c=A&c=0&c=0&c=a&c=

7、A&c=F) state=4;else if(c=H) state=6;else ERROR=1;break;case 6:ERROR=1;break;/*end switch*/if(ERROR=1)break; /* 退出内for的循环，完成一个词的分析。*/*end inside-for*/if(ERROR=1)printf(%-15s is a un-identify word!n,argvi);else if(ERROR=0)printf(%-15s is a %sn,argvi,stringstate);/*end outside-for*/*未输入任何字符串时(除文件名外)*/

8、if(ERROR=-1) printf(You input nothing!n); exit(0); /*正常退出程序*/*end main*/b、#include#include#include#include/定义关键字char *table7=continue,main,int,if,then,else,return,TOKEN20,ch; bool zimu(char ch)/判断是否为字母if(ch=a&ch=A&ch=0&ch=9)return true;elsereturn false;int lookup(char *TOKEN) /关键字匹配函数,查询所述程序中的关键字 in

9、t m,i;for(i=0;i) TOKEN0=ch; out(4,TOKEN); else if(ch=) TOKEN0=ch; out(4,TOKEN); else if(ch=) TOKEN0=ch; out(4,TOKEN); else if(ch=!=) TOKEN0=ch; out(4,TOKEN); /判断分隔符并输出else if(ch=,) TOKEN0=ch; out(5,TOKEN); else if(ch=;) TOKEN0=ch; out(5,TOKEN); else if(ch=) TOKEN0=ch; out(5,TOKEN); else if(ch=) TOKE

10、N0=ch; out(5,TOKEN); else if(ch=() TOKEN0=ch; out(5,TOKEN); else if(ch=) TOKEN0=ch; out(5,TOKEN); main()FILE *fp;/读取文件内容，并返回文件指针，该指针指向文件的第一个字符if(fp=fopen(E:222.txt,r)=NULL) fprintf(stderr,error opening.n);exit(1);doch=fgetc(fp);if(ch=#) /文件以#结尾，作为扫描结束条件 break;if(ch= ) /如果是空格，自动跳到下个字符scanner(fp);else

11、fseek(fp,-1,1); /如果不是空格，则回退一个字符并扫描scanner(fp);while(ch!=#);return 0;(3) 系统调试a、b、5.实验总结通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。这次的实验使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编

12、写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常通过自己编写此类的代码来提高自己的能力。附录1Little语言的EBNF文法:=:=; :=|:=read; :=write; :=:=:=ifthen elsefi:=todoend:=whiledoend:=:= := := | | ():= := | := = | = | | := + | -:= * | /:= 0|1|2|3|4|5|6|7|8|9:= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z附录21. 计算x!的little程序（测试程序，用于测试你编写的词法分析程序）Read n； to n doread x;if x0 theny := 1, z :=1;while zx doz := z+1;y := y*zend;write yfiend2. 计算x的little程序（测试程序，用于测试你编写的词法分析程序）n=1;while n0 doread x;sum=0;while x0 dosum=sum+x;x=x-1;end;write sum;read n;end;专心-专注-专业