本文源自笔者的课程《编译原理》的实验一，原题如下：
假设一个语言允许使用十六进制数，其规定是：必须以数字打头，必须以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) = (VN, VT, P, S)
其中，VN = { S, X', Y', Z', M', N’,W’, a’, b’, c’, d’, e’, f’, g’,h’}
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}
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
