词法分析---基于Asp.NET(实验二学习笔记)
一、背景
任务说明
词法分析表
保留字
特殊符号
其他
if
+
十进制的整数与实数
else
-
while
*
read
/
标识符（由数字、字母和下划线组成的串，但必须以字母开头、且不能以下划线结尾的串）
write
=
int
<
real
==
<>
(
)
;
{
}
/*
*/
[
]
这次实验主要是完成词法分析器，目的是从输入的源程序中能够识别出各个具有独立意义的记号，包括保留字、标识符、常数、运算符、分隔符等，并依次输出各个记号序列。如果出错（即不是语言可以识别的记号），则输出error。
二、 功能实现描述
正则表达式
在cmm中，语言记号大致可分为以下几大类。
1. 保留字
在正则表达式中，保留字是最简单的了，因为它们仅是由字符的固定序列表示，如果要将所有的保留字收集到一个定义中，就可以写成：
reserved=int|real|if|else|while|read|write…….
2. 数
数可以是数字（自然数）、十进制数、或者是小数
nat=[0-9]+
signednat=(+|-)nat
float=singednat ”.” nat
3. 标识符
标识符不是固定的字符串。在cmm中，规定标识符必须由一个字母开头并且只包括字母和数字。可以用一下正则表达式：
letter=[a-za-z]
digit=[0-9]
identifier=letter(letter|digit)*
4. 注释
注释在扫描过程中是被忽略的， 扫描程序必须注释并舍弃它们。虽然扫描程序可能没有清晰的常量记号，但是仍需要给注释编写出正则表达式。在cmm中，我给出的单行注释是：//，多行注释有：/* */或{}
5. 二义性、空白格和先行
在使用正则表达式的描述中，有一些串经常可以被不同的正则表达式匹配。例如：if和while的串可以既是标识符又可以是关键字。程序设计语言定义规定了应遵守哪个解释，但是正则表达式本身却无法做到它。相反地，语言定义必须给出无二义性规则，由其回答每一种情况下的含义。
程序设计语言中空白格伪记号的典型定义是：
whitespace=(newline|blank|tab|comment)+
其中，等号右边的标识符代表恰当的字符或串。空白格通常不是作为记号分隔符，而是被忽略掉。
分隔符结束记号串，但他们并不是记号本身的一部分。因此，扫描程序必须处理先行(lookahead)问题：当它遇到一个分隔符时，它必须做出安排分隔符不会从输入的其他部分中国删除，方法是将分隔符返回到输入串或在将字符从输入中删除之前先行。在大多数情况下，只有单个字符才需要这样做（“单个字符先行”）。
有穷自动机
有穷自动机，或称有穷状态的机器，是描述特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程。当然有穷自动机与正则表达式之间有着很密切的关系。
确定性有穷自动机（dfa）定义：一个确定的有穷自动机（dfa）m是一个五元组：m=（k，σ，f，s，z）其中
① k是一个有穷集，它的每个元素称为一个状态；
② σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称σ为输入符号字母表；
③ f是转换函数，是k×σ→k上的映射，即，如 f（ki，a）=kj，（ki∈k，kj∈k）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
④ s ∈ k是唯一的一个初态；
⑤ z⊂k是一个终态集，终态也称可接受状态或结束状态。
dfa的下一个状态有当前状态和当前输入字符唯一给出的自动机。非确定的有穷自动机是由它产生的。
带有出错转换的标识符的有穷自动机
以上给出了带有出错转换标识符的有穷自动机的示例图。nat和小数的dfa非常简单，在这里就不给出示例了。cmm词法分析器的dfa：
从正则表达式到dfa
我们只关心两个算法：一个是将正则表达式翻译成nfa，另一个是将nfa翻译成dfa。再将dfa翻译成程序。
程序
dfa
nfa
正则表达式
利用thompson结构 -转换将正则表达式的机器片段“粘在一起”以构成与整个表达式相对应的机器。因此该结构式归纳的，而且它依照了正则表达式定义的结构：为每个基本正则表达式展示一个nfa，接着再显示如何通过连接子表达式的nfa得到每个正则表达式。
实现dfa的主要代码：
public static tokentypegettoken()
{
inttokenstringindex = 0;/* 当ì¡à前¡ãtoken的ì?索¡â引°y */
/* 当ì¡à前¡ãtoken的ì?类¤¨¤型¨ª*/
tokentypecurrenttoken = tokentype.void; ;
/* 起e始º?状á¡ä态¬? */
statetypestate = statetype.start;
/* 标਺识º?是º?否¤?储ä¡é存ä?当ì¡à前¡ã字á?符¤? */
intsave;
int once=1;
while(state != statetype.done)
{
intc = getnextchar();
save = 1;
switch(state)
{
casestatetype.start:
if(char.isnumber((char)c))
state = statetype.innum;
elseif(c=='.')
state = statetype.point;
elseif (char.isletter((char)c))
state = statetype.inid;
// else if (c == ':')
// state = inassign;
elseif (c == '<')
state = statetype.inless;
elseif (c == '>')
state = statetype.ingreat;
elseif (c == '=')
state = statetype.inassign;
elseif (c == '!')
state = statetype.innequal;
elseif(c== '/')
{
save=0;
state = statetype.incomment2;
}
elseif ((c == ' ')|| (c == '\t') || (c == '\n'))
save = 0;
// else if (c == '{')
// { save = false;
// state = incomment;
// }
else
{
state = statetype.done;
switch (c)
{
case -1://文?件t结¨¢束º?
save = 0;
currenttoken = tokentype.endfile;
break;
case'{':
currenttoken = tokentype.lbegin;
break;
case '}':
currenttoken = tokentype.rend;
break;
case '+':
currenttoken = tokentype.plus;
break;
case '-':
currenttoken = tokentype.minus;
break;
case '*':
currenttoken = tokentype.times;
break;
// case '/':
// currenttoken = over;
// break;
case '(':
currenttoken = tokentype.lparen;
break;
case ')':
currenttoken = tokentype.rparen;
break;
case'[':
currenttoken = tokentype.larray;
break;
case ']':
currenttoken = tokentype.rarray;
break;
case ';':
currenttoken = tokentype.semi;
break;
case',':
currenttoken = tokentype.comma;
break;
case'%':
currenttoken = tokentype.mod;
break;
default:
currenttoken = tokentype.error;
break;
}
}
break;
casestatetype.incomment:
save = 0;
if(c == -1)
{
state = statetype.done;
currenttoken = tokentype.endfile;
}
elseif (c == '}')state = statetype.start;
break;
casestatetype.inless:
state = statetype.done;
if(c == '=')
currenttoken = tokentype.le;
elseif (c == '>')
currenttoken = tokentype.neq;
else
{ /*取¨?备à?份¤y的ì?前¡ã一°?个?字á?符¤? */
ungetnextchar();
save = 0;
currenttoken = tokentype.lt;
}
break;
casestatetype.ingreat:
state = statetype.done;
if(c == '=')
currenttoken = tokentype.ge;
else
{ /*backup in the input */
ungetnextchar();
save = 0;
currenttoken = tokentype.gt;
}
break;//innoequal
casestatetype.inassign:
state = statetype.done;
if(c == '=')
currenttoken = tokentype.eq;
else
{
ungetnextchar();
save = 0;
currenttoken = tokentype.assign;
}
break;
casestatetype.innequal:
state = statetype.done;
if(c == '=')
currenttoken = tokentype.neq;
else
{
ungetnextchar();
save = 0;
currenttoken = tokentype.error;
}
break;
casestatetype.incomment2:
save = 0;
if(c == -1)
{
state = statetype.done;
currenttoken = tokentype.endfile;
}
elseif (c == '/')
{
state = statetype.incomment_single;
}
else if(c=='*')
{
state = statetype.incomment_multi_1;
}
else
{
ungetnextchar();
save = 1;
c='/';
currenttoken = tokentype.over;
state = statetype.done;
}
break;
casestatetype.incomment_single:
save = 0;
if(c == -1)
{
state = statetype.done;
currenttoken = tokentype.endfile;
}
elseif (c == '\n')
state = statetype.start;
break;
casestatetype.incomment_multi_1:
save = 0;
if(c == -1)
{
state = statetype.done;
currenttoken = tokentype.endfile;
}
elseif (c == '*')
state = statetype.incomment_multi_2;
break;
casestatetype.incomment_multi_2:
save = 0;
if(c == -1)
{
state = statetype.done;
currenttoken = tokentype.endfile;
}
elseif (c == '/')
state = statetype.start;
else
state = statetype.incomment_multi_1;
break;
casestatetype.point:
if(!char.isletter((char)c))
{
ungetnextchar();
save = 0;
state = statetype.done;
currenttoken = tokentype.num;
}
break;
casestatetype.innum:
if(c=='.'&&once!=0)
{
--once;
break;
}
if(!char.isletter((char)c))
{
ungetnextchar();
save = 0;
state = statetype.done;
if(once!=0)
currenttoken = tokentype.num;
}
break;
casestatetype.inid:
if(!char.isletter((char)c)&&!char.isdigit((char)c))
{
ungetnextchar();
save = 0;
state = statetype.done;
currenttoken = tokentype.id;
}
break;
casestatetype.done:
default:
state = statetype.done;
currenttoken = tokentype.error;
break;
}
if((save!=0) && (tokenstringindex <= maxtokenlen))
{
tokenstring[tokenstringindex] = (char)c;
tokenstringindex++;
}
if(state == statetype.done)
{
tokenstring[tokenstringindex] = '\0';
if(currenttoken == tokentype.id)
{
currenttoken =reservedlookup(chartostring(tokenstring));
}
}
}
//util.printtoken(currenttoken,tokenstring.tostring());
stringtemps = util.printtoken(currenttoken,chartostring(tokenstring));
objcode += " "+temps;
returncurrenttoken;
}
实现方法
本人采用asp.net,在windows 7平台下，将cmm语法解释器做成网页版的，在某种程度上实现了跨平台性。
三、使用说明
由于我这web项目无法打包成一个可以执行的文件，只可以在下访问，可能需要在vs2010下编译执行。
在左侧方框中输入要分析的源文件，点击分析之后，在右侧方框出现词法分析。
下一篇： 美图秀秀怎么合成逼真的杯中美女的图片?