词法分析

简介

词法分析是编译原理中的一个重要步骤，它是将源代码中的字符序列（如程序、脚本等）分解成一系列的单词或词素（ Token ）的过程。 Token 是编程语言中的最小单元，它可以是关键字、标识符、运算符、常量或分隔符等。

词法分析器（ Lexer ）会读入源代码字符序列，扫描每个字符，并根据语法规则将字符序列分割成 Token 序列，然后将这些 Token 保存下来，交给下一步的语法分析器（ Parser ）进行分析和处理。

在词法分析的过程中，词法分析器通常会忽略空格、换行符等无关字符，只识别有效的 Token ，并为每个 Token 打上相应的类型标记。例如，对于C语言中的表达式 x\=y+3 ，词法分析器会识别出标识符 x 、 y 、 + 、 \= 和数字 3 ，并将它们分别打上相应的类型标记，以便后续的语法分析和代码生成。

词法分析算法

本节参考了"编译器设计 第二版"

主要包含从正则表达式构造 NFA ，从 NFA 到 DFA 的子集构造算法， NFA 模拟算法，最小化 DFA 的算法。

TODO

flex 使用的词法分析算法

flex 使用的词法分析算法是基于有限状态自动机 （Finite State Automaton，FSA） 的算法。它将用户定义的正则表达式转换成一个 DFA（Deterministic Finite Automaton，确定性有限状态自动机） ，然后通过扫描输入的字符序列，并根据 DFA 的状态转移规则逐个读入字符，最终得到 Token 序列。

flex 生成的词法分析器中包含一个状态转移表，该表包含了所有的状态和状态转移规则。每个状态对应一个状态号，每个字符对应一个字符类，状态转移表中的每个条目记录了当前状态、字符类和下一个状态。在扫描输入字符序列时，词法分析器会根据当前状态和读入的字符，查找状态转移表，找到下一个状态，并执行相应的动作，例如记录 Token 类型、值等。

flex 使用 FSA 算法的优点是速度快，生成的词法分析器代码比较紧凑，并且可以自动生成状态转移表，无需手动设计状态转移规则。缺点是在处理一些上下文相关的语言时，可能会出现识别错误的情况。

One More Thing

词法分析算法的演变

  1. 手写的有限状态自动机：早期的词法分析器都是手写的有限状态自动机，需要程序员自己设计状态转移表和状态转移规则，实现比较困难，而且容易出错。

  2. 正则表达式和自动生成器：正则表达式和自动生成器的出现简化了词法分析器的设计和实现。程序员可以使用正则表达式描述 Token 的识别规则，并使用自动生成器生成词法分析器。

  3. 基于递归下降分析器的词法分析：递归下降分析器可以将语法规则转化为递归函数，然后通过递归调用的方式来识别 Token 。这种算法实现起来比较简单，容易维护和调试。

  4. 基于 LL(k) 分析器的词法分析： LL(k) 分析器是一种自顶向下的语法分析器，可以自动生成词法分析器。 LL(k) 分析器不需要事先设计状态转移表，可以自动识别上下文相关的语法规则，提高了语法分析的效率和准确性。

  5. 基于神经网络的词法分析：近年来，随着深度学习的发展，一些研究者开始探索使用神经网络来进行词法分析。使用神经网络的词法分析算法不需要事先设计状态转移表或编写正则表达式等规则，而是通过训练神经网络来自动学习 Token 的识别规则，提高了词法分析的效率和准确性。

各种词法分析算法的优缺点

在处理的文法类型、实现复杂度和运行效率等方面，这些词法分析算法各有其优缺点：

  1. 手写的有限状态自动机

    优点：可读性好，实现简单，可以直接用状态机理解语言特性，能够处理各种文法类型。

    缺点：不易维护和修改，需要手动编写状态转移表和状态转移规则。

  2. 正则表达式和自动生成器

    优点：使用正则表达式描述 Token 的识别规则，简化了词法分析器的设计和实现，自动生成器可以生成词法分析器。

    缺点：有时无法处理上下文相关的语法规则，如括号匹配等。

  3. 基于递归下降分析器的词法分析

    优点：可以将语法规则转化为递归函数，实现简单，容易维护和调试。

    缺点：在处理左递归文法时容易陷入无限递归。

  4. 基于 LL(k) 分析器的词法分析

    优点：自顶向下的语法分析器，可以自动生成词法分析器，不需要事先设计状态转移表，可以自动识别上下文相关的语法规则。

    缺点：需要进行回溯处理，导致效率较低。

  5. 基于 LR(k) 分析器的词法分析

    优点：自底向上的语法分析器，效率高，可以处理大部分语言文法类型。

    缺点：需要预处理所有可能的推导路径，表格较大，容易引起内存溢出。

  6. 基于神经网络的词法分析

    优点：可以自动学习 Token 的识别规则，准确率高，不需要手动编写规则。

    缺点：训练模型需要大量的数据和计算资源，模型复杂度高，实现难度大。

正则表达式、 NFA 与 DFA

关于 NFA 与 DFA 的精确定义可以在龙书的 3.6 节找到。

正则表达式、 NFA 、 DFA 三者的关系可以描述为：在实现词法分析器时，开发者可以使用正则表达式来描述词法规则，接着可以使用算法将正则表达式转换为 NFA ，最后可以使用算法将 NFA 转换为 DFA 或者使用算法直接模拟 NFA 。

由 NFA 构造 DFA 的算法称为子集构造法，具体的细节请参考龙书的 3.7 节。