实验一词法分析(共10页).doc
精选优质文档-倾情为你奉上编译原理实验一 词法分析1.实验目的通过实验掌握词法分析的理论、原理和方法，为语法分析做准备。2.实验内容: a) 十六进制数识别器：规定是：必须以十六进制数字打头，以H结尾，十六进制数中允许使用的数字为0-9，字母为A，B，C，D，E, F(分别表示015)。试设计一个DFA，使它能识别无符号的十六进制整数，并编制相应的识别程序。输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。输出：标识出规范的符号串与不合规范的符号串。b) 词法分析：设计、编制、调试一个识别一个Little语言单词的词法分析程序（见附录1）。输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。输出：二元组。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) = (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|Z S X|Y|Z X |M M |M | | Y |Y Z H|WH W |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及DFA最小化（造表法）对应以上的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=elsek5>returnm6<.7>=8<=9!=(2) 编码实现a、#include <stdio.h>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<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'&&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;else if (c='H') state=6;else ERROR=1;break;case 2:if(c>='a'&&c<='z')|(c>='A'&&c<='Z')|(c>='0'&&c<='9') state=2;else ERROR=1;break;case 4:if(c>='0'&&c<='9')|(c>='a'&&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);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>/定义关键字char *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;/判断是否为数字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 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) /判断是关键字还是普通的标识符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); 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='>=') 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='') TOKEN0=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);elsefseek(fp,-1,1); /如果不是空格，则回退一个字符并扫描scanner(fp);while(ch!='#');return 0;(3) 系统调试a、b、5.实验总结通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。这次的实验使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常通过自己编写此类的代码来提高自己的能力。附录1Little语言的EBNF文法<program>:=<sequence><sequence>:=<sentence> <sentence><sentence>:=<input sentence>|<output sentence>|<evaluate sentence>|<condition sentence>|<determinacy loop sentence>|<indeterminacy loop sentence><input sentence>:=read<variable> <variable><output sentence>:=write<variable> <variable><evaluate sentence>:=<variable>:=<expression><condition sentence>:=if<compare expression>then<sequence> else<sequence>fi<determinacy loop sentence>:=to<expression>do<sequence>end<indeterminacy loop sentence>:=while<compare expression>do<sequence>end<compare expression>>:=<expression><relation><expression><expression>:=<term> <weak operator><term><term>:=<element> <strong operator><element><element>:=<constant> | <variable> | (<expression>)<constant>:=<digital> <digital><variable>:=<char> <char> | <digital><relation>:= = | =< | >= | < | > | <><weak operator>:= + | -<strong operator>:= * | /<digital>:= 0|1|2|3|4|5|6|7|8|9<char>:= 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 x>0 theny := 1, z :=1;while z<>x doz := z+1;y := y*zend;write yfiend2. 计算åx的little程序（测试程序，用于测试你编写的词法分析程序）n=1;while n<>0 doread x;sum=0;while x>0 dosum=sum+x;x=x-1;end;write sum;read n;end;专心-专注-专业
