词法分析器负责输入源码字符串，输出一串词法单元序列。它的接口是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// 表示直接供给语法分析器的 Token 类型。这种 token 经过序列化和整理,
/// 合并了表示相同的不同语法, 方便给 parser 使用
pub enum FinalToken { ... }

pub struct IRLexer<'src> { ... }

/// IRLexer 是个迭代器.
/// 之所以不直接输出一个 vec 之类的序列是因为这么做省内存
impl<'src> Iterator for IRLexer<'src> {
    type Item = (Result<FinalToken, String>, logos::Span);

    fn next(&mut self) -> Option<Self::Item> { ... }
}
impl<'src> IRLexer<'src> {
    pub fn new(source: &'src str) -> Self { ... }
}

PrimToken 和 FinalToken

最初我直接让 FinalToken 实现 logos::Logos 的注解, 但这么做在面对浮点常量之类的语法规则时很容易写得非常丑陋. 例如, 浮点常量一共有这么几条规则:

  1. 十进制浮点, 小数模式: [+-]?[0-9]*\.[0-9]+
  2. 十进制浮点, 整数模式: [+-]?[0-9]+\.
  3. 十进制浮点, 指数模式1: [+-]?[0-9]*\.[0-9]+[eE][+-]?[0-9]+
  4. 十进制浮点, 指数模式2: [+-]?[0-9]+(\.)?[eE][+-]?[0-9]+
  5. 十六进制浮点, 模式1: [+-]?0[xX][0-9A-Fa-f]*\.[0-9A-Fa-f]+[pP][+-]?[0-9]+
  6. 十六进制浮点, 模式2: [+-]?0[xX][0-9A-Fa-f]+(\.)?[pP][+-]?[0-9]+

这几个要混在一起写的话, 且不说这些变体的反序列化能否一起做, 就正则表达式的可维护性都够烂了。因此我得这么做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[derive(Logos)]
pub enum ???Token {
    ...

    #[regex(r"[+-]?[0-9]*\.[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec0Std(f64),

    #[regex(r"[+-]?[0-9]+\.", PrimToken::parse_dec_fp)]
    LitFPDec1Std(f64),

    #[regex(r"[+-]?[0-9]*\.[0-9]+[eE][+-]?[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec0Exp(f64),

    #[regex(r"[+-]?[0-9]+(\.)?[eE][+-]?[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec1Exp(f64),

    #[regex(r"[+-]?0[xX][0-9A-Fa-f]*\.[0-9A-Fa-f]+[pP][+-]?[0-9]+")]
    LitFPHex0(&'lex str),

    #[regex(r"[+-]?0[xX][0-9A-Fa-f]+(\.)?[pP][+-]?[0-9]+")]
    LitFPHex1(&'lex str),

    ...
}

不过 parser 要是看到一个浮点数有这么多变体的话, 匹配都匹配不过来了. 因此我选择把“负责做词法分析的那个 token 类型”和“负责给 parser 看的那个 token 类型”拆分开来, 搞了私有的 PrimToken 和开放的 FinalToken.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#[derive(Logos)]
enum PrimToken<'src> {
    /// 词法规则集合; 具体源码参见下面的附录
    ...
}

impl<'src> PrimToken<'src> {
    fn into_final(self) -> Result<FinalToken, String> {
        // 1. 合并语义相同的变体
        // 2. 解析一些 PrimToken 那边不容易解析的东西, 比如把 LitFPHex* 解析成浮点数
    }
}

// 因此, IRLexer 实际上只是个 logos::Lexer 的包装器
pub struct IRLexer<'src> {
    spanned: logos::SpannedIter<'lex, PrimToken<'lex>>,
}
impl<'src> Iterator for IRLexer<'src> {
    type Item = (Result<FinalToken, String>, logos::Span);

    fn next(&mut self) -> Option<Self::Item> {
        let (res, span) = self.spanned.next()?;
        let res = res
            .map_err(|()| String::from("Internal lexer error"))
            .and_then(|token| token.into_final());
        Some((res, span))
    }
}

关键字解析

Remusys-IR 中充斥着大量的上下文关键字；甚至, 由于基本块标签语法的存在, 任意的 Word 都可以不是关键字。比如这样的:

1
2
3
4
5
6
7
8
9
10
11
12
define dso_local i32 @main(i32 %argc, ptr %argv) {
define:
    %ptr = load ptr, ptr %argv, align 8
    %cond = icmp eq ptr %ptr, null
    br i1 %cond, label %add, label %sub
add:
    %res = add nuw i32 %argc, 1
    ret i32 %res
sub:
    %res2 = sub nuw i32 %argc, 1
    ret i32 %res2
}

注意看, 所有看上去像关键字的都可以放在标签上. 所以我选择在词法分析阶段只解析出 word 来，不做任何关键字判断. 到了哪个上下文要用关键字的时候再具体比较 word 内字符的内容。

写文章的时候突然想到可以把 [_A-Za-z][0-9_A-Za-z]*\: 当成一个独立的 token 来着… 不过写都写完了就这样吧.

附录

1. 所有词法规则

这些词法规则不是一开始就设计好的, 而是有什么需求就加什么.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#[derive(Debug, Clone, Logos)]
enum PrimToken<'lex> {
    #[regex(r"[+-]?[0-9]+", |lex| PrimToken::parse_dec_int(lex.slice()))]
    LitDecInt(i128),

    #[regex(r"[+-]?(0X|0x)[0-9A-Fa-f]+", |lex| PrimToken::parse_hex_int(lex.slice()))]
    LitHexInt(i128),

    #[regex(r#"c\"([^\\\"]|(\\[0-9A-Fa-f][0-9A-Fa-f]))*\""#)]
    LitBytes(&'lex str),

    #[regex(r"[+-]?[0-9]*\.[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec0Std(f64),

    #[regex(r"[+-]?[0-9]+\.", PrimToken::parse_dec_fp)]
    LitFPDec1Std(f64),

    #[regex(r"[+-]?[0-9]*\.[0-9]+[eE][+-]?[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec0Exp(f64),

    #[regex(r"[+-]?[0-9]+(\.)?[eE][+-]?[0-9]+", PrimToken::parse_dec_fp)]
    LitFPDec1Exp(f64),

    #[regex(r"[+-]?0[xX][0-9A-Fa-f]*\.[0-9A-Fa-f]+[pP][+-]?[0-9]+")]
    LitFPHex0(&'lex str),

    #[regex(r"[+-]?0[xX][0-9A-Fa-f]+(\.)?[pP][+-]?[0-9]+")]
    LitFPHex1(&'lex str),

    #[regex(r"%[a-z0-9A-Z_]+", |lex| &lex.slice()[1..])]
    PIdent(&'lex str),

    #[regex(r"@[a-z0-9A-Z_]+", |lex| &lex.slice()[1..])]
    AIdent(&'lex str),

    #[regex(r"[a-zA-Z_][a-z0-9A-Z_]*")]
    Word(&'lex str),

    #[regex(r":")]
    Colon,
    #[regex(r",")]
    Comma,
    #[regex(r"!")]
    Exclaim,
    #[regex(r"\.\.=")]
    DotDotEq,
    #[regex(r"\.\.\.")]
    Ellipsis,
    #[regex(r"=")]
    Eq,

    #[regex(r"\(")]
    LParen,
    #[regex(r"\)")]
    RParen,

    #[regex(r"\[")]
    LBracket,
    #[regex(r"\]")]
    RBracket,

    #[regex(r"\{")]
    LBrace,
    #[regex(r"\}")]
    RBrace,

    #[regex(r"<")]
    LAngle,
    #[regex(r">")]
    RAngle,

    /// 你没看错. 很反常的一点是, Remusys-IR Text (或者说, LLVM-IR Text)
    /// 也可以不依赖换行符的.
    #[regex(r"[ \n\r\t\f]+", logos::skip)]
    Space,

    #[regex(r";[^\n\r]*", logos::skip, allow_greedy = true)]
    LineComment,
}