1、= 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|YZH|WHW|W|可见，上式方法中，X表示出了语言的标识符，而Y表示出了语言的无符号的十进制，Z表示出了语言中的十六进制。上式G（S）文法中，各式右边只有单个的终结符号显然，以上文法G（S）已是正规文法。（2）正规文法转成正规式：具体步骤如下：|M 可表示为M*|W可表示为W*|Z可表示为Z* 转换成正规表达式为：S=| * |H | *H |*代入可得：
2、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、
3、单词的BNF表示 - |下划线|无符号整数数字串 |加法运算符 +减法运算符 -大于关系运算符 大于等于关系运算符=由此可知，需将单词分为五种：关键字1标识符2常数3运算符4分隔符5printfa+,mainb1_;intc2*（ifstudent3/）thensum4elsek5returnm6.789!（2） 编码实现#include main（int argc,char *argv）int i,j,state,ERROR=-1; /* state控制状态的转移 1表示09数字， 2表示字母，4表示af，6表示H，0为未输入状态* ERROR=-1表示未输入任何字符串 =1表示输入出错*/
4、char c; /* 暂时存放所取得的一个字符 */char *string=,Unsigned IntegerIdentifierHex;/*输出结果时用*/for（i=1;i0&caz）|（cAZ） state=2;else ERROR=1;break; /* ERROR=1,表示当前字符c为非法字符。* 即此时无状态可转向。*/case 1:else if（cfF）state=4;else if （c=Hstate=6;else ERROR=1;case 2:if（ccase 4:else if（c=case 6:ERROR=1;/*end switch*/if（ERROR=1） /*
5、退出内for的循环，完成一个词的分析。/*end inside-for*/if（ERROR=1）printf（%-15s is a un-identify word!n,argvi）;else if（ERROR=0）%-15s is a %sn,argvi,stringstate）;/*end outside-for*/*未输入任何字符串时（除文件名外）*/ if（ERROR=-1） printf（You input nothing!）; exit（0）; /*正常退出程序*/*end main*/#includestdlib.hctype.h/定义关键字char *table7=contin
6、uemainintifthenelsereturn,TOKEN20,ch;bool zimu（char ch）/判断是否为字母if（chchreturn true;elsereturn false;/判断是否为数字bool shuzi（char ch）int lookup（char *TOKEN） /关键字匹配函数,查询所述程序中的关键字 int m,i;for（i=0;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
7、 scanner（FILE *fp） /扫描函数 char TOKEN20=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,TO
8、KEN）;elseout（2,TOKEN）;else if（shuzi（ch）TOKEN0=ch;while（shuzi（ch） /判断该字符是否是字母或数字 fseek（fp,-1,1）;out（3,TOKEN）; /判断运算符并输出else if（ch=+） TOKEN0=ch; out（4,TOKEN）; -*/ /判断分隔符并输出, out（5,TOKEN）;（）main（）FILE *fp;/读取文件内容，并返回文件指针，该指针指向文件的第一个字符if（fp=fopen（E:222.txtr）=NULL） fprintf（stderr,error opening.nexit（1）;d
9、oif（ch=#） /文件以#结尾，作为扫描结束条件 break; ） /如果是空格，自动跳到下个字符scanner（fp）;fseek（fp,-1,1）; /如果不是空格，则回退一个字符并扫描while（ch!（3） 系统调试5.实验总结通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。这次
10、的实验使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常通过自己编写此类的代码来提高自己的能力。附录1Little语言的EBNF文法program:=sentence;input sentenceoutput sentenceevaluate sentencecondition sentencedeterminacy loop sentenceindeterminacy loop sentence=read=write=ifthen elsefi=todoend=whileterm elementstrong operatorconstant | | （char= = | = | 0 theny := 1, z :=1;while zx doz := z+1;= y*zend;write yfi2. 计算x的little程序（测试程序，用于测试你编写的词法分析程序）n=1;while nsum=sum+x;x=x-1;write sum;read n;10
