词法分析（lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

词法分析器的工作是低级别的分析：将字符或者字符序列转化成记号。在谈论词法分析时，使用术语“词法记号”（简称记号）、“模式”和“词法单元”表示特定的含义。

在分析时，一是把词法分析器当成语法分析的一部分，另一种是把词法分析器当成编译程序的独立部分。在前一种情况下，词法分析器不断地被语法分析器调用，每调用一次词法分析器将从源程序的字符序列拼出一个单词，并将其Token值返回给语法分析器。后一种情况则不同，词法分析器不是被语法分析器不断地调用，而是一次扫描全部单词完成编译器的独立一遍任务。

有限状态自动机是具有离散输入和输出的系统的一种数学模型。

其主要特点有以下几个方面：

– (1)系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。

– (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。

– (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。

– (4)系统中有一个状态，它是系统的开始状态。

– (5)系统中还有一些状态表示它所读入的字符构成的字符串是语言的一个句子。

形式定义

· 定义：有限状态自动机(FA—finite automaton)是一个五元组：

– M=(Q, Σ, δ, q0, F)

· 其中，

– Q——状态的非空有穷集合。∀q∈Q，q称为M的一个状态。

– Σ——输入字母表。

– δ——状态转移函数，有时又叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。

– q0——M的开始状态，也可叫作初始状态或启动状态。q0∈Q。

– F——M的终止状态集合。F被Q包含。任给q∈F，q称为M的终止状态。

语法分析器（Parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。

语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串（输入文本），主要可以通过两种方式完成：

自顶向下分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。

自底向上分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。

Lex读进一个代表词法分析器规则的输入字符串流，然后输出以C语言实做的词法分析器源代码。

虽然传统上是商业软件，但是有些根据原本AT&T代码这些版本的Lex可以以公开源代码的形式获得，并被视为某些系统的一部分，例如说OpenSolaris和贝尔实验室九号项目。另一个有名的Lex公开源代码版本是flex，代表"快速的词法分析器"（fast lexical analyzer）。

输入缓冲区

成对且对半互补的输入缓冲区模式。

n: 取2的整次幂；每个半区的末尾设置标志“ eof ” 表示读入该半区的源程序的结束；

B：单词w开始指针； F：扫描w的指针。

两个缓冲区的输入模式

预处理程序： （作用）

1） 减少内存空间占用；

2） 减轻扫描器实质性处理的负担；

预处理程序主要任务： 1） 滤掉源程序中的非单词成分(如无用空格；换行符等)；2） 其他的预处理工作:滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入。

#include<stdio.h> #include<string.h> #include<iostream.h> char prog,token; char ch; int syn,p,m=0,n,row,sum=0; char *rwtab={"begin","if","then","while","do","end"};   void scaner() {     /*         共分为三大块，分别是标示符、数字、符号，对应下面的 if   else if  和 else                    */      for(n=0;n<8;n++) token=NULL;     ch=prog;     while(ch==' ')     {         ch=prog;         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=ch;             ch=prog;         }         token='\0';         p--;         syn=10;         for(n=0;n<6;n++)  //将识别出来的字符和已定义的标示符作比较，              if(strcmp(token,rwtab)==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--;         syn=11;         if(sum>32767)             syn=-1;     }     else switch(ch)   //其他字符      {         case'<':m=0;token=ch;             ch=prog;             if(ch=='>')             {                 syn=21;                 token=ch;             }             else if(ch=='=')             {                 syn=22;                 token=ch;             }             else             {                 syn=23;                 p--;             }             break;         case'>':m=0;token=ch;             ch=prog;             if(ch=='=')             {                 syn=24;                 token=ch;             }             else             {                 syn=20;                 p--;             }             break;         case':':m=0;token=ch;             ch=prog;             if(ch=='=')             {                 syn=18;                 token=ch;             }             else             {                 syn=17;                 p--;             }             break;         case'*':syn=13;token=ch;break;         case'/':syn=14;token=ch;break;         case'+':syn=15;token=ch;break;         case'-':syn=16;token=ch;break;         case'=':syn=25;token=ch;break;         case';':syn=26;token=ch;break;         case'(':syn=27;token=ch;break;         case')':syn=28;token=ch;break;         case'#':syn=0;token=ch;break;         case'\n':syn=-2;break;         default: syn=-1;break;     } } int main() {     p=0;     row=1;     cout<<"Please input string:"<<endl;     do     {         cin.get(ch);         prog=ch;     }     while(ch!='#');     p=0;     do     {         scaner();         switch(syn)         {         case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break;           case -1: cout<<"Error in row "<<row<<"!"<<endl; break;         case -2: row=row++;break;         default: cout<<"("<<syn<<","<<token<<")"<<endl;break;         }     }     while (syn!=0); }