Edgar Hoo Blog

假设一个语言允许使用十六进制数，其规定是：必须以数字打头，必须以H结尾，数中允许使用的字母为A，B，C，D，E, F(分别表示10~15)。该语言的标识符为字母开头的字母数字串。试设计一个DFA，使它能识别标识符、无符号的十进制和十六进制整数(假定各单词之间用界限符或空格分开)，并编制相应的识别程序。

输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。

输出：标识出规范的符号串与不合规范的符号串。

（来源：海南大学儋州校区计算机系）

要求如下：

A、根据给定的语言求出其文法；

B、将该文法转换成正规式；

C、由正规式构造NFA；

D、将NFA转换成DFA,并将其最小化；

E、根据最小化的DFA编写词法分析程序。

按说这个实验该用C语言编程，但最近学习JavaScript、PHP，正好借此题目练习。

根据题意，笔者认为十六进制整数不含小写字母（包括H），十六进制整数首字符为0的情况下第二字符不能为数字，无符号的十进制整数除0外首字符不能为0。

笔者编JS代码如下：

• /*
• Item Name: Recognizer of Realize
• Description: Compilation Principle Experiment 1st
• Version: 1.0
• Author: Edgar Hoo
• Author URI: http://EdgarHoo.com
• Last Updated: Nov. 23, 2008 @ SCUTA
• CopyRight 2008 BY-NC-SA
• */
• function recog(){
• var test = document.myform.mytest.value;// 取得待测字符串
• var tl = test.length;// 定义字符串长度
• var s=0;// state
• for (i=0;i<tl;i++){
•  ti = test.charAt(i);// 字符串第i个字符
•  if (ti==' ' || ti=='　') s=6;// 去除半角及全角空格
•  else {
•   switch(s){
•     case 0: if (ti==0) s=1;
•       else if (ti>=1 && ti<=9) s=2;
•       else if ((ti>='A' && ti<='Z') || (ti>='a' && ti<='z')) s=3;
•       else s=6;
•       break;
•     case 1: if (ti>='A' && ti<='F') s=4;
•       else if (ti=='H') s=5;
•       else s=6;
•       break;
•     case 2: if (ti>=0 && ti<=9) s=2;
•       else if (ti>='A' && ti<='F') s=4;
•       else if (ti=='H') s=5;
•       else s=6;
•       break;
•     case 3: if ((ti>=0 && ti<=9) || (ti>='A' && ti<='Z') || (ti>='a' && ti<='z')) s=3;
•       else s=6;
•       break;
•     case 4: if ((ti>=0 && ti<=9) || (ti>='A' && ti<='F')) s=4;
•     else if (ti=='H') s=5;
•     else s=6;
•     break;
•   }
•  }
• if (s==6) break;
• }
• if (s==0) alert("请输入待测字符串！");
• else if (s==1 || s==2) alert(test+"是十进制数。");
• else if (s==3) alert(test+"是标识符。");
• else if (s==5) alert(test+"是十六进制数。");
• else if (s==4 || s==6) alert(test+"是不合规范字符串。");
• }

因为采用提交HTML表单的形式输入待测字符串，而JS将表单中的空格转换成“+”，但在实际测试中，程序却将空格判断为数字，所以，在循环中首先判断去除空格。本以为如果采用在JS代码中添加待测字符串，则不需要添加去除空格的代码，而事实再次证明JS同样认为空格是数字。

用PHP编码，只要稍作改动即可，PHP没有空格问题，减少几行代码，完整代码如下：

• $test = $_GET['mytest'];
• $tl = strlen($test);
• $s = 0;
• $i = 0;
• for ($i=0;$i<$tl;$i++){
•  $ti = substr($test,$i,1);
•   switch ($s){
•     case 0: if ($ti=='0') $s=1;
•       else if ($ti>='1' && $ti<='9') $s=2;
•       else if (($ti>='A' && $ti<='Z') || ($ti>='a' && $ti<='z')) $s=3;
•       else $s=6;
•       break;
•     case 1: if ($ti>='A' && $ti<='F') $s=4;
•       else if ($ti=='H') $s=5;
•       else $s=6;
•       break;
•     case 2: if ($ti>='0' && $ti<='9') $s=2;
•       else if ($ti>='A' && $ti<='F') $s=4;
•       else if ($ti=='H') $s=5;
•       else $s=6;
•       break;
•     case 3: if (($ti>='0' && $ti<='9') || ($ti>='A' && $ti<='Z') || ($ti>='a' && $ti<='z')) $s=3;
•       else $s=6;
•       break;
•     case 4: if (($ti>='0' && $ti<='9') || ($ti>='A' && $ti<='F')) $s=4;
•       else if ($ti=='H') $s=5;
•       else $s=6;
•       break;
•   }
•  if ($s==6) break;
• }
   
• if ($s==0) $out = '请输入待测字符串！';
• else if ($s==1 || $s==2) $out = $test.'：是十进制数。';
• else if ($s==3) $out = $test.'：是标识符。';
• else if ($s==5) $out = $test.'：是十六进制数。';
• else if ($s==4 || $s==6) $out = $test.'：是不合规范字符串。';

因为本站空间默认启用get_magic_quotes_gpc()函数，所以在输出字符串之前要使用stripslashes()：

• $out = stripslashes($out); echo $out;

测试地址：JS、JS-sp、PHP

附：

(1)．文法：按题意，十六进制整数如0AH、11H、1AH、1A0BH等由以数字打头，并以H结尾的字符串，不含a、b等小写字母；标识符如a0、ab、A1a等由A至Z、a至z、0至9并以字母开头的字母数字串；无符号的十进制整数如0、11、123等由0至9之间数字组合组成，而00、001等则不属于无符号的十进制整数。

由以上可得出文法，表示如下：G(S) = (V_N, V_T, P, S)

其中，V_N = { S, X', Y', Z', M', N’,W’, a’, b’, c’, d’, e’, f’, g’,h’}

V_T = { 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}

a’= 0

b’=1|2|3|4|5|6|7|8|9

c’ = A|B|C|D|E|F

d’ =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’ → a’ H | b’ H | a’ c’ M’ H | b’ M’ H

M’ →e’ | e’ M’

e’ → a’ | b’ | c’

Y’ →f’ |f’ N’

f’ →c’| d’

N’ → g’ | g’ N’

g’ →a’ | b’ | c’ | d’

Z’ →a’ | b’ | b’ W’

W’ → h’ | h’ W’

h’ → a’ | b’

上述表示中，X’为十六进制整数，Y’为标识符，Z’为无符号十进制整数。

(2)．正规式：由于上文文法已为正规文法，所以根据转换规则，步骤如下：

M’ → e’| e’ M’     =>   M’ →e’ * e’

N’ → g’ | g’ N’    =>   N’ →g’ * g’

W’ → h’ |h’ W’   =>  W’ → h’*h’

所以，转换成正规式为：S=a’ H |b’ H | a’ c’ e’ * e’ H| b’ e’ * e’ H| f’ |f’ g’ * g’| a’ |b’ |b’ h’ *h’

代入可得：

S=a’ H| b’ H| a’ c’ (a’ |b’ |c’)*(a’ |b’ |c’)H |b’ (a’ |b’ |c’)*(a’ |b’ |c’)H| (c’ |d’)| (c’ |d’)(a’ |b’ |c’ |d’)*(a’ |b’ |c’ |d’)| a’ |b’ | b’ (a’ |b’)*(a’ |b’)

(3)．NFA：

初始NFA图：

最终NFA图：

(4)．DFA：对应以上NFA图，用造表法表示如下：

由上表得出DFA图：

其中，状态2和状态6等价，状态3和状态8等价，状态4、状态9和状态7等价，化简后得最小DFA图：

Updated @ Nov. 30,2008 SCUTA

－－－－－这是分割线－－－－－

Flickr 1/2/3/4/5