实验一词法分析

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) = (V

3、N，VT，P，S)其中 VN = S，X' Y' Z'，M' W' a，3，Y，卩，u，coVT = 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 ,Za = 0|1| 2|3|4|5|6|7|8|93= a|b|c|d|e|f|A|B|C|D|E|FY =g| h|i|j|k|l|m| n|o|p|q|r|s|t|u|v|w|x|y|z|G|H|l|G

4、|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|ZS T X' |Y' |Z'X ' t u |u M 'M ' To |o M 'u T 3 | Yo t a | 3 | YY' T a |a Y'Z ' t a H| a W' HW'1 la W'i fa | 3可见，上式方法中，X '表示出了语言的标识符，而Y '表示出了语言的无符号的十进制，Z '表示出了语言中的十六进制。-上式G(S)文法中，各式右边只有单个的终结符号显然，以上文法 G(S)已

5、是正规文法。(2) 正规文法转成正规式：具体步骤如下：T M ' f 3 | w M '可表示为 M ' f w * 3W' f i 11 W' 可表示为 W' f i * iZ' f a | a Z'可表示为 Z' f a * a 转换成正规表达式为： S= u | u w * w | a H | a i * i H | a * a代入可得：S= ( 3 Iy ) | ( 3 |Y ) ( a |3 | Y )*( a | 3 Y ) | a H | a ( a |3 )* ( a |3 )H | a * a(3) 正规

6、式转成NFA (分裂法)初始的NFA图下所示：(3|V)|(3|¥)(o|p|vf(a|P|Y)| aH | a (a | p)* (a |0 >H | a经过替换规则替换后得到的最终图1初始NFA图NFA图如下所示:图2最终的NFA图(4)NFA转成DFA及 DFA最小化(造表法)对应以上的NFA图，我们可用造表法来表示如下:I1InSA54"卫&训©KL23 © FJf23J ©04.E 6,7.8.5.9 Q4.F.340J.9) Q(8.10.9) (71 0F©F.U32网02网卩邛©04;E840d

7、5d9071丽疋;0色刚8.10.9 Q 0F©审0IF.3021,3© 2J3b 1显然，由图可看出，状态 2与状态5等价，而状态1与状态3等价，这里省去状态3和状态5，并将所以指向状态 3的状态都指向状态1，指向状态5的都指向状态2。由 此可画出最小化的 DFA图如下：c屮可见，终结状态1表示出了无符号的十进制，终结状态2表示出了标识符， 状态6表示出了十六进制的整数。b、单词的BNF表示<标识符 >-> < 字母 ><字母数字串><字母数字串 >->< 字母 ><字母数字串>|<

8、数字 ><字母数字串>|<下划线 ><字母数字串>| £<无符号整数 >-> < 数字 >< 数字串><数字串 >-> < 数字 ><数字串> | £<加法运算符>-> +<减法运算符>-> -<大于关系运算符>-> ><大于等于关系运算符>-> > =由此可知，需将单词分为五种：关键字i标识符2常数3运算符4分隔符5printfa0+5mai nb1intc2*(i

9、fstude nt3/)the nsum4=elsek5>returnm6<7>=8<=9!=(2)编码实现a、#in elude <stdio.h>main (i nt argc,char *argv)int i,j,state,ERR0R=-1;/* state控制状态的转移1表示09数字，2表示字母，4表示af, 6表示H ,0为未输入状态* ERROR=-1表示未输入任何字符串=1表示输入出错*/char c; /*暂时存放所取得的一个字符*/char *string="","Unsigned Integer"

10、,"Identifier","","","","Hex"/*输出结果时用 */for(i=1;i<argc;i+)state=0;/* 初始态为 0 */ERROR=0;/*控制是否为可识别词or非法字符*/for(j=0;(c=argvij)!='0'j+)switch(state)case 0:if(c>='0'&&c<='9')state=1;else if(c>='a'&&am

11、p;c<='z')|(c>='A'&&c<='Z') state=2;else ERROR=1;break;/* ERROR=1,表示当前字符c为非法字符。*即此时无状态可转向。*/case 1:if(c>='0'&&c<='9')state=1;else if(c>='a'&&c<='f)|(c>='A'&&c<='F')state=4;el

12、se if (c='H')state=6;elseERROR=1;break;case 2: if(c>='a'&&c<='z')|(c>='A'&&c<='Z')|(c>='0'&&c<='9') state=2;elseERROR=1;break;case 4: if(c>='0'&&c<='9')|(c>='a'&

13、amp;&c<='f')|(c>='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);

14、else if(ERROR=0)printf("%-15s is a %sn",argvi,stringstate);/*end outside-for*/* 未输入任何字符串时 (除文件名外 )*/ if(ERROR=-1) printf("You input nothing!n");exit(0); /* 正常退出程序 */*end main*/b、#include<string.h>#include<stdio.h>#include<stdlib.h>#include<ctype.h>/定义关键字ch

15、ar *table7="continue","main","int","if","then","else","return",TOKEN20,ch;bool zimu(char ch)/ 判断是否为字母if(ch>='a'&&ch<='z'|ch>='A'&&ch<='Z')return true;elsereturn false;/判断

16、是否为数字bool shuzi(char ch)if(ch>='0'&&ch<='9')return true;elsereturn false;int lookup(char *TOKEN) / 关键字匹配函数 , 查询所述程序中的关键字int m,i;for(i=0;i<6;i+) if(m=strcmp(TOKEN,tablei)=0) return 1;return 0;void out(int c,char *TOKEN)/ 输出函数 printf("(%d,%s)n",c,TOKEN);void

17、scanner(FILE *fp)/扫描函数char TOKEN20='0'char ch;int i;ch=fgetc(fp); /获取字符，指针 fp 并自动指向下一个字符if(zimu(ch) /判断该字符是否是字母，若 ch 指的是字母，返回非 0，否则返回 0 TOKEN0=ch;ch=fgetc(fp); /fgetc(fp) 从数据流中区下一个字符i=1;while(shuzi(ch)| zimu(ch) / 判断该字符是否是字母或数字TOKENi=ch;ch=fgetc(fp);i+;fseek(fp,-1,1);if(lookup(TOKEN) / 判断是关键

18、字还是普通的标识符 out(1,TOKEN);elseout(2,TOKEN);else if(shuzi(ch)TOKEN0=ch;ch=fgetc(fp); /fgetc(fp) 从数据流中区下一个字符 i=1;while(shuzi(ch) / 判断该字符是否是字母或数字TOKENi=ch; ch=fgetc(fp); i+;fseek(fp,-1,1); out(3,TOKEN);/判断运算符并输出else if(ch='+')TOKEN0=ch;out(4,TOKEN);else if(ch='-')TOKEN0=ch;out(4,TOKEN);els

19、e 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(4,TOKEN);else if(ch='<')TOKEN0=ch;out(4,TOKEN);else if(ch='>=')TOKEN0=ch;out(4,TOKEN);else if(ch='&

20、lt;=')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='')TOKEN0=ch;out(5,TOKEN);else if(ch='(')TOKEN0=

21、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='')如果是空格，自动跳到下个字符

22、sca nn er(fp);elsefseek(fp,-1,1);/如果不是空格，则回退一个字符并扫描sca nn er(fp);while(ch!='#');return 0;(3)系统调试a、tiello123 7AH 803Hhelloz 匚:WINDOWS5ystem3Zci123 7AH 0阴H n3 7chI dentif iei* Unsigned Integer HexHexIdentif ier un-identif y wordtb、5.实验总结通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以 此来确定该实验要我们实现的是什么，怎么实

23、现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何设计、编制并调试词法分析程序，加深 对词法分析原理的理解；实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。这次的实验使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点 再加上自己的努力都一一克服了， 今后我也会经常通过自己编写此类的代码来提高自己的能 力。附录1Littlevprogram>:=<seque nce> vseque nce>

24、:=<se nten ce> <se nten ce> <se nten ce>:=<in put senten ce>|<output senten ce>|<evaluate senten ce>|<c on diti on senten ce>|<determ inacy loop senten ce>| <in determ inacy loop senten ce><in put senten ce>:=read<variable> <variab

25、le> voutput senten ce>:=write <variable> <variable> vevaluate senten ce>:=<variable>=<expressi on><con diti on senten ce>:=f vcompare expressi on ihenvseque nce> pls呱seque nce>i vdeterm inacy loop senten ce>:=o<expressi on >dovseque nce：end<in determ inacy loop senten ce>:=while<compare expressi on:dovseque nce>md vcompare expressi on> >:=<exp