<--, _> <;, _>
词法分析分析器作为一个子程序 词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析器设计
输入、预处理
词法分析器工作的第一步是输入源程序文本。在许多情况下，为了更好地对单词符号识别，把输入串预处理一下。预处理主要滤掉空格，跳过注释、换行符等。 超前搜索
词法分析过程中，有时为了确定词性，需超前扫描若干个字符。
对于FORTRAN 语言，关键字不作为保留字，可作为标识符使用， 空格符号没有任何意义。为了确定词性，需超前扫描若干个字符。 在FORTRAN中
1 DO99K=1,10 2 IF(5.EQ.M) I=10 3 DO99K=1.10 4 IF(5)=55
这四个语句都是正确的语句。语句1和2 分别是DO和IF语句，语句3和4是赋值语句。为了正确区别1和3，2和4语句，需超前扫描若干个字符。
1 DO99K=1,10 2 IF(5.EQ.M) I=10 3 DO99K=1.10 4 IF(5)=55
语句1和3的区别在于符号之后的第一个界符：一个为逗号，另一个为句末符。语句2和4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。为了识别1、2中的关键字，必须超前扫描多个字符。超前到能够肯定词性的地方为止。为了区别1和3，必须超前扫描到等号后的第一个界符处。对于语句2、4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。 状态转换图
词法分析器使用状态转换图来识别单词符号。状态转换图是一张有限方向图。在状态转换图中，有一个初态，至少一个终态。
其中0为初态，2为终态。这个转换图识别（接受）标识符的过程是：从初态0开始，若在状态0之下输入字符是一个字母，则读进它，并转入状态1。在状态1之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到状态1发现输入字符不再是字母或数字时（这个字符也已被读进）就进入状态2。状态2是终态，它意味着到此已识别出一个标识符，识别过程宣告终止。终态结上打个星号意味着多读进了一个不属于标识符部分的字符，应把它退还给输入口中 。如果在状态0时输入字符不为“字母”，则意味着识别不出标识符，或者说，这个转换图工作不成功。 正规表达式与正规集
正规表达式是说明单词的一种重要的表示法(记号)，是定义正规集的工具。在词法分析中，正规表达式用来描述标示符可能具有的形式。 定义(正规式和它所表示的正规集)： 设字母表为S，
1. e和Ø都是S上的正规式，它们所表示的正规集分别为{e}和{ }； 2. 任何aÎ S，a是S上的一个正规式，它所表示的正规集为{a}；
3. 假定U和V都是S上的正规式，它们所表示的正规集分别为L(U)和L(V)，那么，(U), U|V, U·V, U*也都是正规式,它们所表示的正规集分别为L(U), L(U)ÈL(V), L(U)L(V)和(L(U))*；
4. 仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式所表示的字集才是S上的正规集。
正规式的运算符的“½”读为“或” ,“· ”读为“连接”；“*”读为“闭包”(即，任意有限次的自重复连接)。
在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“· ”、“½” 。连接符“· ”一般可省略不写。
“*”、“· ”和“½” 都是左结合的。
例 令S={a,b}， S上的正规式和相应的正规集的例子有： 正规式 正规集
a {a} a½b {a,b} ab {ab}
(a½b)(a {aa,ab,ba,bb}
a * {e ,a,a, ……任意个a的串}
ba* {b, ba, baa, baaa, …}
(a½b)* {e ,a,b,aa,ab ……所有由a和b 组成的串}
(a½b)*(aa½bb)(a½b)* {S*上所有含有两个相继的a 或两个相继的b组成 的串}
定理：若两个正规式U和V所表示的正规集相同,则说U和V等价,写作U=V。 证明b(ab)*=( ba)*b
证明：因为L(b(ab)*)={b}{e, ab, abab, ababab, …} ={b, bab, babab, bababab, …} L((ba)*b) ={e, ba, baba, bababa, …}{b} ={b, bab, babab, bababab, …} = L(b(ab)*) 所以, b(ab)*=( ba)*b
设U，V，W为正规式，正规式服从的代数规律有： (1) U½V=V½U (交换律)
(2) U½(V½W)=(U½V)½W (结合律) (3) U(VW)=(UV)W (结合律)
(4) U(V½W)=UV½UW (V½W)U=VU½WU (分配律) (5) eU=U e=U
分析器的简单实现
上文主要介绍了词法分析的一些相关的知识，而对词法分析器的具体实现还没有具体提到，为了能更好的理解词法分析，我写了一个简单的词法分析器。
虽然说是语法分析器，但实现的功能很简单，只是对输入的程序把注释去掉，其中用到了上面关于状态转换图部分的知识。 分析：
一般的程序设计语言， 注释部分的形式为； /* 注释部分、、、、*/
我们的程序总是顺序的一个一个字符读取输入文件的。我们的目的是把注释部分去掉，那么对于输入的字符流，我们只要识别出“/*”就知道后面的部分是注释部分，直到识别输入流中出现\"*/\"为止。
对字符流的处理是一个一个进行的，每读入一个字符，就判断，如果字符是“/”,就说明后面 的部分可能是注释，再看下一个输入字符，如果是“*”, 就是上面所说的情况：“ /*”那么后面的部分就是注释部分，然后再用相同的方法找出\"*/\"就可以了。 这个识别的过程就可以用状态转换图来清晰的表示:
对于读入的每个符号都要进行判断，如果是“/”说明后面的部分有可能是注释，进入状态1。如果后面的输入是“*”那么就可以确定以后的内容为注释内容，如果后面的输入不是\"*\"，说明后面的内容不是注释，前面出现的\"/\"可能是做除号使用，如“5/3”
其实上面的流程图也就对应了程序实现的逻辑，可以用switch-case 来实现，对于每个输入，判断后跳转到相应的状态，然后继续判断。 下面是程序伪代码：
while((ch=getchar())!=EOF) switch(state)
case 1 :if ch==\"/\ case 2: if ch==\"*\ else state=1;break; case 3:.......... case 4:..........
词法分析器
这个程序比较简单，就不给出源代码了。接下来是一个简单的词法分析器的代码，可以实现对关键字（如 while end if 等），对数字的识别，去掉空格符等。 下面是这个分析器的功能： 1、 待分析的简单语言的词法 （1） 关键字：
begin if then while do end 所有关键字都是小写。 （2） 运算符和界符：
:= + – * / < <= <> > >= = ; ( ) #
（3） 其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义： ID=letter（letter| digit）* NUM=digit digit *
（4） 空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、 各种单词符号对应的种别码
词法分析程序的功能
输入：所给文法的源程序字符串。
输出：二元组（syn，token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。
运行结果：
源代码：
#include #include #include char prog[80],token[8]; char ch;int syn,p,m=0,n,row,sum=0;
char *rwtab[6]={\"begin\
void scaner() {
/*
共分为三大块，分别是标示符、数字、符号，对应下面的 if else if 和 else */
for(n=0;n<8;n++) token[n]=NULL; ch=prog[p++];
while(ch==' ') {
ch=prog[p]; p++; }
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) //可能是标示符或者变量名 {
m=0;
while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
{
token[m++]=ch; ch=prog[p++]; }
token[m++]='\\0'; p--;
syn=10;
for(n=0;n<6;n++) //将识别出来的字符和已定义的标示符作比较，
if(strcmp(token,rwtab[n])==0) {
syn=n+1; break; } }
else if((ch>='0'&&ch<='9')) //数字 {
{
sum=0;
while((ch>='0'&&ch<='9')) {
sum=sum*10+ch-'0'; ch=prog[p++]; } } p--;
syn=11;
if(sum>32767) syn=-1; }
else switch(ch) //其他字符 {
case'<':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='>') {
syn=21;
token[m++]=ch; }
else if(ch=='=') {
syn=22;
token[m++]=ch; } else {
syn=23; p--; }
break;
case'>':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') {
syn=24;
token[m++]=ch; } else {
syn=20; p--; }
break;
case':':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') {
syn=18;
token[m++]=ch; } else {
syn=17; p--; }
break;
case'*':syn=13;token[0]=ch;break; case'/':syn=14;token[0]=ch;break; case'+':syn=15;token[0]=ch;break; case'-':syn=16;token[0]=ch;break; case'=':syn=25;token[0]=ch;break; case';':syn=26;token[0]=ch;break; case'(':syn=27;token[0]=ch;break; case')':syn=28;token[0]=ch;break; case'#':syn=0;token[0]=ch;break; case'\\n':syn=-2;break; default: syn=-1;break; } }
int main() {
p=0; row=1;
cout<<\"Please input string:\"<cin.get(ch); prog[p++]=ch; }while(ch!='#'); p=0; do {
scaner(); switch(syn) {
case 11: cout<<\"(\"<cout<<\"(\"<while (syn!=0); }