2 Lexical Analysis

职责

词法分析器(Scanner / Lexer)是编译器的第一个阶段,做三件事:

  1. 切分:把连续的字符流切成有意义的单元
  2. 归类:给每个单元打上类别
  3. 过滤:丢掉空白、换行、注释

输出是一串 Token,每个 Token 形如 <类别, 属性值>:

源码:  if (x <= 10) count++;

Token: [IF, -] [LPAREN, -] [ID, "x"] [LE, -] [NUM, 10]
       [RPAREN, -] [ID, "count"] [INC, -] [SEMI, -]

属性值(lexical value)只对标识符和常量有意义——关键字、运算符的类别本身就足够,值可以为空。

为什么"切分"不是简单的事

直觉上 split() 就够了,但真实语言有几处坑:

最长匹配:<= 必须识别成一个 LE,而不是 < 加 =。同理 ==、>=、!=、++、->、::。

回退:匹配 <= 时要先看到 < 再试探 =。如果后面不是 =,要回退一个字符再重新走。这就是"最长匹配 + 回退"机制。

关键字还是标识符:if 是关键字,iffy 是标识符。必须先按标识符的规则扫完整个单词,再查保留字表判断。

上下文相关:C++ 的 >> 在模板嵌套里要当两个 >;C 的 typedef 会让后续标识符变成类型名。这类问题严格说词法层解决不了,业界做法是词法分析器和语法分析器互相打信号(lexer hack / symbol table feedback)。

正则定义

形式化地描述 Token 的模式。正则比文法弱,但恰好够用——因为词法结构不需要记忆嵌套。

给定字母表Σ\Sigma,正则定义:

符号含义
ϵ\epsilon空串
a∈Σa \in \Sigma单个字符
r∣sr \mid s选择(或)
rsrs连接
r∗r^*闭包(零次或多次)
r+r^+正闭包(一次或多次)
r?r?可选

常见 Token 的正则:

letter   = [A-Za-z_]
digit    = [0-9]
id       = letter (letter | digit)*
int      = digit+
float    = digit+ '.' digit* ( [eE] [+-]? digit+ )?
          | '.' digit+ ( [eE] [+-]? digit+ )?
ws       = (' ' | '\t' | '\n' | '\r')+
comment  = '//' [^\n]*  |  '/*' ([^*] | '*'+ [^*/])* '*'+ '/'

注意 float 的定义里,1.、.5、1e10 都得覆盖,还要防止 1..2 被误吃。写浮点正则时最容易漏的就是指数部分。

有限自动机

正则只是声明,自动机才是执行。

DFA vs NFA

DFA(确定)NFA(不确定)
同一状态同一输入唯一后继可有多个后继
ϵ\epsilon 转移不允许允许
匹配复杂度O(n)O(n)回溯时可能指数级
构造难度难(直接从正则构造)易
状态数可能指数级膨胀与正则规模线性

结论:用 NFA 便于构造,转成 DFA 便于执行。

Thompson 构造:正则 → NFA

递归地把正则翻译成带ϵ\epsilon 转移的 NFA 片段:

ε:      ──►(s)──ε──►(f)

a:      ──►(s)──a──►(f)

r|s:         ┌──ε─►[NFA r]─ε─┐
      ──►(s)─┤               ├─►(f)
             └──ε─►[NFA s]─ε─┘

rs:    ──►[NFA r]──►[NFA s]──►

r*:      ┌────────ε────────┐
         │                 ▼
      ──►(s)──ε──►[NFA r]──ε──►(f)
              └───────ε───────►

每个构造只增加常数个状态,所以总状态数是O(∣r∣)O(|r|)。

子集构造:NFA → DFA

核心思想:DFA 的一个状态 = NFA 的一个状态集合。

算法(省略 ε-closure 细节):
  Dstates = { ε-closure(nfa_start) }   未标记
  while 存在未标记的 DFA 状态 T:
      标记 T
      for 每个输入符号 a:
          U = ε-closure(move(T, a))
          if U 非空 且 U ∉ Dstates:
              Dstates.add(U)  未标记
          Dtrans[T, a] = U

ε-closure(S):从 S 中状态出发,只走ϵ\epsilon 边能到达的所有状态。 move(T, a):T 中状态经符号 a 能直接到达的状态集合。

最坏情况状态数指数爆炸,但实际的词法规则很少触发——因为真实 Token 的模式都很简单。

最小化:Hopcroft 算法

把 DFA 的状态按"行为是否等价"合并。步骤:

  1. 初始划分:接受态 / 非接受态(再按对应 Token 类型细分)
  2. 反复细分:若状态s,ts,t 同组,但δ(s,a)\delta(s,a) 与δ(t,a)\delta(t,a) 不同组,则拆分
  3. 到划分不再变化为止

最小化后的 DFA 是同语言下状态数最少的(唯一,同构意义下)。

从自动机到词法分析器

教科书路线:正则 → NFA → DFA → 最小化 DFA → 表驱动扫描器。

 正则规则集
     │  Thompson 构造
     ▼
    NFA
     │  子集构造
     ▼
    DFA
     │  Hopcroft 最小化
     ▼
最小 DFA ──► 转移表(二维数组)
                 │
                 ▼
            表驱动扫描器

工业界(flex、re2c、Go 的 lexer)确实走这条路,因为转移表可以预先算好,运行时是纯粹的数组查表,快且可预测。

但手写 lexer 通常更直接——用 switch + 手写状态机,因为可读性更好、调试更容易、还能处理上面那些"词法层解决不了"的边界情况。LLVM/Clang、V8、Lua 的 lexer 都是手写的。

最长匹配与优先级

两条规则同时匹配时:

  1. 最长匹配优先:能匹配多长就匹配多长
  2. 同等长度时,先声明的规则优先

第二条决定了关键字必须写在标识符前面(或单独查表):

"if"    { return IF;    }   /* 声明在前,同等长度优先命中 */
[a-z]+  { return ID;    }

如果把 [a-z]+ 写在前面,if 就永远被当标识符了。

手写词法分析器:一个能跑的实现

// 一个够用的 C 子集 lexer
#include <string>
#include <vector>
#include <cctype>

enum class Tok {
    End, If, Else, While, Return, Int,
    Id, Num,
    Assign, Eq, Ne, Le, Lt, Ge, Gt,
    Plus, Minus, Star, Slash,
    LParen, RParen, LBrace, RBrace, Semi, Comma
};

struct Token {
    Tok kind;
    std::string text;   // lexeme
    long long value;    // Num 的字面值
};

class Lexer {
    const std::string& src;
    size_t pos = 0;

    static const std::vector<std::pair<const char*, Tok>>& keywords() {
        static const std::vector<std::pair<const char*, Tok>> kw = {
            {"if", Tok::If}, {"else", Tok::Else}, {"while", Tok::While},
            {"return", Tok::Return}, {"int", Tok::Int},
        };
        return kw;
    }

    char peek(size_t off = 0) const {
        return pos + off < src.size() ? src[pos + off] : '\0';
    }
    void skipSpaceAndComments() {
        for (;;) {
            while (std::isspace((unsigned char)peek())) ++pos;
            if (peek() == '/' && peek(1) == '/') {          // 行注释
                while (peek() && peek() != '\n') ++pos;
            } else if (peek() == '/' && peek(1) == '*') {   // 块注释
                pos += 2;
                while (peek() && !(peek() == '*' && peek(1) == '/')) ++pos;
                pos += 2;
            } else break;
        }
    }

public:
    explicit Lexer(const std::string& s) : src(s) {}

    Token next() {
        skipSpaceAndComments();
        size_t start = pos;
        char c = peek();
        if (!c) return {Tok::End, "", 0};

        // 标识符 / 关键字
        if (std::isalpha((unsigned char)c) || c == '_') {
            while (std::isalnum((unsigned char)peek()) || peek() == '_') ++pos;
            std::string text = src.substr(start, pos - start);
            for (auto& [kw, k] : keywords())
                if (text == kw) return {k, text, 0};
            return {Tok::Id, text, 0};
        }

        // 数字
        if (std::isdigit((unsigned char)c)) {
            long long v = 0;
            while (std::isdigit((unsigned char)peek()))
                v = v * 10 + (peek() - '0'), ++pos;
            return {Tok::Num, src.substr(start, pos - start), v};
        }

        // 运算符:先试探两字符,再回退到单字符
        auto two = [&](char b, Tok t) {
            if (peek(1) == b) { pos += 2; return Token{t, src.substr(start, 2), 0}; }
            return Token{Tok::End, "", 0};
        };
        switch (c) {
            case '=': { auto t = two('=', Tok::Eq);      return t.kind == Tok::End ? (++pos, Token{Tok::Assign, "=", 0}) : t; }
            case '!': { auto t = two('=', Tok::Ne);      return t.kind == Tok::End ? (++pos, Token{Tok::End, "!", 0}) : t; }
            case '<': { auto t = two('=', Tok::Le);      return t.kind == Tok::End ? (++pos, Token{Tok::Lt, "<", 0}) : t; }
            case '>': { auto t = two('=', Tok::Ge);      return t.kind == Tok::End ? (++pos, Token{Tok::Gt, ">", 0}) : t; }
            case '+': ++pos; return {Tok::Plus,  "+", 0};
            case '-': ++pos; return {Tok::Minus, "-", 0};
            case '*': ++pos; return {Tok::Star,  "*", 0};
            case '/': ++pos; return {Tok::Slash, "/", 0};
            case '(': ++pos; return {Tok::LParen,  "(", 0};
            case ')': ++pos; return {Tok::RParen,  ")", 0};
            case '{': ++pos; return {Tok::LBrace,  "{", 0};
            case '}': ++pos; return {Tok::RBrace,  "}", 0};
            case ';': ++pos; return {Tok::Semi,    ";", 0};
            case ',': ++pos; return {Tok::Comma,   ",", 0};
            default:  ++pos; return {Tok::End, std::string(1, c), 0}; // 非法字符
        }
    }
};

要点:

  • peek(off) 做前瞻,配合"试探两字符再回退"实现最长匹配
  • 关键字用查表而非写进状态机,规则集变化时不用改自动机
  • 非法字符不直接终止,而是返回一个特殊 Token 并继续——这样一次能报多个错
  • 常量在词法阶段就把字符串转成数值,后面不用再解析

缓冲:为什么需要双缓冲区

扫描器要频繁前瞻再回退,如果直接读文件会大量 seek。经典解法是双缓冲区(double buffering):

[ 前半 1024B ][ 后半 1024B ]
      ▲             ▲
      lexemeBegin   forward

forward 前瞻时可能跨到后半;当 forward 到达某半末尾,立刻读下一块填进另一半;若整个缓冲区都不够装一个 Token(超长字符串),则扩容。这样绝大部分前瞻都在内存里完成。

现代实现没这么讲究——直接把整个源文件读进内存就行,几 MB 的源码现代机器毫无压力。双缓冲区是内存按 KB 计时代的产物,但思想(批量读 + 指针扫描)还在。

错误处理

词法层能发现的错误有限但必须优雅处理:

错误处理
非法字符(@、$ 在非允许位置)报错,跳过该字符继续
字符串/注释未闭合报错,标记文件结束
数字溢出报错,取截断值或标记

策略是 "绝不终止编译",尽量多报。报错信息要带行列号,所以扫描时需要维护 line 计数(遇到 \n 自增,行首记录 colBase)。

常见坑

  • 忘记最长匹配,把 <= 切成 < 和 =,语法阶段报一堆莫名其妙的错
  • 关键字表顺序,或者干脆忘了关键字也要走最长匹配(ifx 不能切成 if + x)
  • 浮点数正则漏掉指数,1e10 被切成 1 和 e10
  • 注释嵌套:C 的 /* */ 不嵌套,但 /* // */ 里的 // 不是注释开始——必须先处理块注释
  • 预处理在词法之前:C/C++ 里 #define、#include 由预处理器处理,严格来说在词法分析之前(现代编译器把二者融合了)
  • Unicode:标识符允许中文/emoji 时,isalpha 要换成 UTF-8 解码,不能按字节扫

参考

  • flex / re2c:自动生成词法分析器
  • Crafting Interpreters - Scanning
  • re2c 的 DFA 生成思路:NFA → DFA → 最小化 → 直接生成 C goto 代码(比转移表更快)