|
十六进制数的词法识别器 2006-12-17 15:26:10
分类： 作者:余洪周 nickhome@163.com 版权所有，转载时请注明出自: nick19842000.cublog.cn
本文将通过一个识别标识符、无符号的十进制和十六进制整数的词法分析器实例，来帮助您如何掌握简单识别程序的分析、设计与实现的基本技术与一般方法。
题目： 假设一个语言允许使用十六进制数，其规定是：必须以数字打头，必须以H结尾，数中允许使用的字母为A，B，C，D，E, F(分别表示10~15)。该语言的标识符为字母开头的字母数字串。试设计一个DFA，使它能识别标识符、无符号的十进制和十六进制整数(假定各单词之间用界限符或空格分开)，并编制相应的识别程序。 输入：键盘输入输入符号串。 输出：标识出规范的符号串和不合规范的符号串。
一、 分析 (1) 文法：该语言的十六进制，如：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|αW’H 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表示出了十六进制的整数。
二、 编程
这里将用C语言实现以上最小化的DFA，并借用C语言中main函数的形参，即指针数组来存放输入的词语，通过指数数组来读取词语并进行分析，从而实现用键盘输入来分析词语。以下是其简单的程序流程图（图4），由于DFA的详细状态转移在图中表示出来比较复杂，所以这里不细画出来，具体思想将在代码中表现出来。
图4 程序流程图 程序代码如下： /* * ana.c * Written by Yu Hongzhou <nickhome@163.com> * * A simple DFA programe */ #include <stdio.h> main(int argc,char *argv[]){ int i,j,state,ERROR=-1; /* state控制状态的转移 * ERROR=-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=argv[i][j])!='\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",argv[i]); else if(ERROR==0) printf("%-15s is a %s\n",argv[i],string[state]); }/*end outside-for*/ /*未输入任何字符串时(除文件名外)*/ if(ERROR==-1) printf("You input nothing!\n"); exit(0); /*正常退出程序*/ }/*?end main*/
三、系统调试 将以上程序代码通过编译器（推荐用Turbo C 2.0）调试连接后，将生成ANA.EXE的可执行文件。打开MSDOS界面，进入ANA.EXE所在的路径。（如：以下的测试我们将把ANA.EXE放在C盘根目录下。）
执行命令输入的标准格式如下： 命令名 字符串1 字符串2 字符串3 ……字符串n 命令名和各字符串间用空格分隔。多余的空格符将被当作字符来处理。命令名，即程序名，可以是ana或ana.exe。如可输入：ana hello 123 7AH 003H n3 ~yl 7ch （注意：如题目所要求的，如果是16进制，则后面的应跟大写的“H”。所以这里小写h被列入a到z的普通标识符中）
图5 命令运行结果
编译的一些方法 |
|
|
