词法分析总体概念
1、词法分析的任务

词法分析是编译的第一个阶段，其任务是：从左至右逐个字符地对源程序（用高级语言编写的）进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。

2、词法分析器（也叫扫描器）

执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。

词法分析器的功能是输入源程序，输出单词符号。

3、词法分析的两种处理结构

（1）把词法分析程序作为主程序。即，把词法分析与语法分析明显分开，由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序，以这个中间程序作为语法分析程序的输入。在这种处理结构中，词法分析和语法分析实际上是分别实现的。

（2）把词法分析程序作为语法分析程序调用的子程序。在进行语法分析时，每当语法分析程序需要一个单词时，便调用词法分析程序，词法分析程序每一次调用便从字符串源程序中识别出一个单词交给语法分析程序。在这种处理结构中，词法分析和语法分析实际上是交替进行的。

$\color{green}{词法分析程序，通常采用第2种处理结构→享用更有效的方法来处理单词}$
词法分析器的设计方法
2.1 单词符号

由语法分析程序的任务可以知道：单词符号是程序语言的基本语法单位具有确定的语法意义。

1、程序语言的单词符号通常可以分为以下5种：




保留字
标识符
常数
运算符
界符




也称为基本字，例如C语言中的if、else、while、do等，保留了语言所规定的含义，是编译程序识别各类语言语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符
用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义
包括各种类型的常数，如整型常数、实型常数、布尔型常数等
如“ + ”、“ - ”、“ * ”、“ / ”、“ > ” 等。
在语言中是作为语法上的分界符号使用的，如“ ， ”、“  ；  ”、“ ； ”、“  （ ”、“  ） ”等。


2、词法分析程序输出的单词符号，通常表示为：

（单词种别，单词自身的值）

一词一码的单词符号，二元式中不必写出值（用null代替即可）；一类一码的单词符号，二元式中要写出值。

（1）单词种别

单词种别表示单词的种类，它是语法分析所需要的信息。通常让每种单词对应一个整数码，这样可以最大限度地把各个单词区分开来。

（2）单词自身的值

单词自身的值，是编译中其它阶段所需要的信息。




若一个种别只含有一个单词符号
若一个种别含有多个单词符号




对于这个单词符号，其种别编码就完全代表了它自身的值
对于他的每个单词符号，除了给出种别编码之外，还应给出单词符号自身的值，以便把同一种类的不同单词区别开来








保留字
标识符
常数
运算符
界符




可将其全体视为一种，也可以一词一种
一般统一归为一种
可以统一归为一种，也可按整型、实型、布尔型等分为几种
可采用一符一种的分法，也可以统一归为一种
可采用一符一种的分法，也可以统一归为一种


采用一词一种比较方便






如果一词一类，那么种别编码就代表自身的值
标识符自身的值就是标识符自身的字符串
常数自身的值是常数本身的二进制数值




注：此外，我们也可以用指向某类表格中一个特定项目的指针来区分同类中的不同单词。

eg: 对于标识符，可以用它在符号表的入口指针作为它自身的值；

常数可以用它在常数表的入口指针作为它自身的值

2.2 状态转换图

举例：无符号数的状态转换图：



当到达一类单词符号的终止状态时即可给出相应的单词编码。由于某些终止状态是在读入一个其它不属于该单词的符号后，才得到相应的单词编码，这表明在识别单词的过程中多读入了一个符号，所以识别处单词后应将最后多读入的这个符号予以回退。




a. 对于不含回路的分支状态来说，可以让它对应一个 switch（）语句或者一组if-else语句：


b. 对于含回路的状态来说，可以让它对应一个 while语句。：



终态一般对应一个return（）语句。return 意味着从词法分析器返回到调用段，一般指返回到语法分析器。
一个简单的词法分析器
一个重要的事实是：大多数程序语言的单词符号都可以用状态转换图予以识别。
举例：

1、C语言子集的单词符号及内码表示：

（由于直接使用整数编码不利于记忆，故用一些特殊符号来表示种别编码）



备注：表格中的保留字，采用一词一码的方式处理→种别编码就完全代表了自身的值；

标识符、常数，采用的是一类一码→分别用指向符号表、常数表的一个特定项目的指针来区分同类中的单词；

运算符、界符，采用一词一码的方式处理。

2、在设计的状态转换图中，首先对输入的串做预处理，剔除多余的空白符 → 将保留字作为一类特殊的标识符来处理，即对保留字不单独设置状态转换图，当转换图识别出一个标识符时，先去查对应的表的前5项，确定它是否为一个保留字。（也可以专设一个保留字表来进行处理）

对应的状态转换图为：



注意：

在图中的状态2时，先确定是否为保留字，否则就是标识符。如果是标识符，应该先查符号表，如果表中无此标识符，则将它加入到符号表中，返回它在符号表中的入口指针（地址）作为该标识符的内码值；如果表中已经有此标识符，则给出重名错误信息。

在状态4时，应将识别的常数转换成二进制常数，并将其加入到常数表中，然后返回其在常数表中的入口指针作为该常数的内码值。

3、状态转换图的实现（C语言代码）

最简单的实现状态转换图的方法：让每个状态对应一小段程序。

对于这个例子的状态转换图，引进一组变量和函数：

(1) character: 字符变量，存放新读入的源程序字符

(2)token: 字符数组，存放构成单词符号的字符串

(3) getbe()： 若character中的字符为空白，则调用getchar()， 直至character为非空白字符为止

(4) concatenation():  将token中的字符串与character中的字符连接并作为token 中新的字符串

(5) letter()和 digit():  判断character中的字符是否为字母和数字的布尔函数，是则返回true(即1)，否则返回false(即0)。

(6) reserve（）: 按token数组中的字符串查表中的前五项(即判别其是否为保留字)，若是保留字则返回它的编码，否则返回0值

(7)retract():  扫描指针回退一个字符，同时将character置为空白。

(8) buildlist(): 将标识符登灵到符号表中或将赏数登录到常数表中

(9) error(): 出现非法字符，显示出错信息。

词法分析概述















词法分析器的设计

在编译原理介绍中，我们已经对前端的工作有了大致的了解。
在其中，词法分析器的任务就是读入源程序，对其进行一定的切分，得到记号流。
对于字符流和记号流之间的区别，下面给出一个例子来说明。
if (x > 5)
    y = "hello";
else
    z = 1;
对面上面这段程序，在词法分析器的眼中，是这样表示的：
i, f, " ", (, x, " ",>, " ", 5, ), n, " "," ", y, " ", =, .........
可见词法分析器看到的字符流和我们眼中的字符流是不一样的。 而词法分析器的任务就是对字符进行 切分。将 i 和 f 并在一起做为一个 if 关键字，去除掉没有意义的空格等等。
对于像 IF， LPAREN， IDENT 等的单词，我们都称为记号。
在记号中，有一些记号是没有属性的，类似于 IF 之类的关键字， IDENT(x) 之类的标识符需要表明其中的元素具体是什么。
记号的数据结构定义如下：
enum kind {IF, LPAREN, ID, INTLIT, ...};
struct token{
    enum kind k;
    char *lexname;
}
因此，对于语句 if (x > 5) 可以转变为
token {
    k = IF;
    lexname = 0; //0 表示没有赋任何的值
}
token {
    k = LPAREN;
    laxname = 0;
}
token {
    k = ID;
    laxname = "x";
}
....
通过上面的学习，我们可以知道词法分析器的任务是将字符流转化为记号流。
字符流：和被编译的语言密切相关（ASCII（C）， Unicode（Java,  Swift）， or ...）
记号流：编译器内部定义的数据结构，编码所识别出的词法单元。
原文链接：
编译原理 - 网易云课堂

在词法分析器中使用怎么样的算法和数据结构是我们的主要研究内容。
词法分析器的实现方法
手工编码实现法
相对复杂，且容易出错
当能够对各个部分进行相当好的控制，效率高
是目前非常流行的实现方法
GCC， LLVM，...
词法分析器的生成器
可快速原型、代码量少
但较难控制细节
如下是手工编码分析常用的转移图：
其中双圆圈表示接收/识别状态，一个单词的识别已经结束。
下面给出一个转移图算法的例子：
token nextToken(){
    c = getChar();
    switch(c){
        case '<': c = getChar();
                  switch(c) {
                      case '=': return LE;
                      case '>': return NE;
                      default: rollback(); return;
                  }
        case '=': return EQ;
        case '>': c = nextChar();
                  switch(c): //similar
    }
}
token nextToken(){
    c = getChar();
    switch(c){
        // continued from abobe cases...
        case 'a', ..., 'z', 'A', ..., 'Z', '_':
            c = getChar();
            while(c == 'a' ||  c == 'b' || ... || c == '_')
                c = getChar(); 
    }
}
识别关键字
（以 if 为例），有如下两种方法：
对于 标识符 和 关键字 其实是有很大的交集的：
从语法分析的角度看，关键字是标识符的一部分
以C语言为例：
标识符：以字母或下划线开头，后面跟零个或者多个字母、下划线、或数字。
关键字：if, while, else, ....
关键字表算法
对给定语言中所有的关键字，构架关键字构成的哈希表H
对所有的标识符和关键字，先统一按标识符的转移图进行识别
识别完成后，进一步查表H看是否是关键字
通过合理的构造哈希表H（完美哈希），可以O(1)时间完成
原文链接：
编译原理 - 网易云课堂