Paradoxical 札记

最近把 neorg 作为笔记和规划系统有点上头，但苦于没一个好用的 Language Server，自己又对编译器前端方面略有了解于是决定写下这篇大概会持续更新的札记

我们的最终目的是实现一个不错的 Language Server 并且可以在 neovim/helix 上跑起来

为什么是 neovim/helix 呢？因为我暂时不会继续用 VSCode 了

流水线设计

考虑到我希望 paradoxical 有如下两个功能

  • 重新格式化 neorg 文档
  • 良好的补全

因此我决定采用如下流水线设计：

1
2
Text  →  Lexer (RawTokenKind)  →  CST  →  Typed AST/HIR  →  Semantic Analysis  →  LSP Server  →  Editor
| src |     Lazy Lexer         |  CST  |                 AST                   |

需要着重说明的是，我们使用 rope 来保存和编辑源文件，这样我们所有的操作的时间复杂度都是 \(O(logN)\)

目标

阶段 0

该阶段起始于 2025-05-16

在阶段 0 需要实现最基本的功能：解析

但由于 neorg 的格式内容较多所以在这个阶段只考虑实现一个子集

  • 标题
  • 有序/无序列表
  • 文本段
    • 文本类型 Paragraph：这种类型允许使用 neorg 的修饰符例如 {} // $||$ 等，这些修饰符可以正常执行其对应的功能
    • 逐字类型 VerbatimParagrah: 这种类型的文本段不会处理 neorg 的修饰符，所有输入的修饰符都应该原样输出
  • 标签 Tag

请注意，由于 neorg设计上要求的非歧义解析，所有解析失败的内容都应该回归为文本类型 Paragraph

Token 设计

基于 Token 的功能和现在的目标，我设计出如下的 RawTokenKind

1
2
3
4
5
6
7
8
9
10
11
12
13
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum RawTokenKind {
    Punct(char),
    NormalChar(char),
    Tag,
    Linending(LinendingKind),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum LinendingKind {
    LF,
    CRLF,
}

以上的代码省略了对于 Display trait 的实现

Token 解析规则

我们使用 nom 这个库来实现解析，因为 neorg 的文档风格非常适合使用组合子解析器的方式进行解析。

不自己编写递归下降解析器是因为 neorg 的规范实际上比较简单，而且 neorg 的二义性情况很容易被判断，因此我们直接使用组合子解析器来实现解析就好

由于我们需要保留 Token 在文档里的位置信息，因此基于 RawTokenKind 派生出 RawToken，添加 span 字段保留当前 Token 的在文档里的位置信息（以偏移表示）

1
2
3
4
5
#[derive(Debug, Clone)]
pub struct RawToken {
    pub kind: RawTokenKind,
    pub span: Range<usize>,
}

接下来我们开始编写对于几个类型 Token 的组合子

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
pub const AVAILIABLE_PUNCT: &[char] = &['(', ')', '-', '~', '*', '/', '{', '}', '[', ']'];

fn parse_punct(input: Span) -> IResult<Span, RawToken> {
    let (input, pos) = position(input)?;
    let (input, matched) = nom::character::complete::one_of(AVAILIABLE_PUNCT)(input)?;

    let token = RawToken {
        kind: RawTokenKind::Punct(matched),
        span: pos.location_offset()..(pos.location_offset() + matched.len_utf8()),
    };

    Ok((input, token))
}

fn parse_normal_char(input: Span) -> IResult<Span, RawToken> {
    let (input, pos) = position(input)?;
    let (input, matched) = nom::character::complete::satisfy(|c| {
        !AVAILIABLE_PUNCT.contains(&c) && c != '@' && c != '\n' && c != '\r'
    })(input)?;

    let token = RawToken {
        kind: RawTokenKind::NormalChar(matched),
        span: pos.location_offset()..(pos.location_offset() + matched.len_utf8()),
    };

    Ok((input, token))
}

fn parse_tag(input: Span) -> IResult<Span, RawToken> {
    let (input, pos) = position(input)?;
    let (input, matched) = nom::character::complete::char('@')(input)?;

    let token = RawToken {
        kind: RawTokenKind::Tag,
        span: pos.location_offset()..(pos.location_offset() + matched.len_utf8()),
    };

    Ok((input, token))
}

fn parse_linending(input: Span) -> IResult<Span, RawToken> {
    let (input, pos) = position(input)?;
    let (input, ending) = nom::branch::alt((
        nom::combinator::map(nom::bytes::complete::tag("\n"), |_| LinendingKind::LF),
        nom::combinator::map(nom::bytes::complete::tag("\r\n"), |_| LinendingKind::CRLF),
    ))
    .parse(input)?;

    let token = RawToken {
        kind: RawTokenKind::Linending(ending),
        span: pos.location_offset()..(pos.location_offset() + ending.to_string().len()),
    };

    Ok((input, token))
}
  • 对于 RawTokenKind::Tag 我们直接提取 @ 字符就好
  • 对于 RawTokenKind::Linending 我们需要判断并且保留文档里的换行符类型
    • \n：UNIX 平台所使用的换行符
    • \r\n：Windows 平台所使用的换行符
  • 对于其他的标点符号，我们引入一个常量 AVAILIABLE_PUNCT 表示可以出现在 RawTokenKind::Punct 内的字符（相当于白名单）
  • 如果在以上情况之外，则归类为 RawTokenKind::NormalChar

因此，我们可以总结出如下的 lexer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let rope = Rope::from_str(source);
let mut tokens = Vec::new();
let mut input = Span::new(source);

let mut parsers = nom::branch::alt((
    Self::parse_tag,
    Self::parse_linending,
    Self::parse_punct,
    Self::parse_normal_char,
));

while !input.fragment().is_empty() {
    let Ok((rest, token)) = parsers.parse(input) else {
        return Err(error::Error::Lexer);
    };

    tokens.push(token);
    input = rest;
}

Ok(Self { text: rope, tokens })

单元测试也是不可少的一部分，因为包括对于中文的解析是略微麻烦也需要验证的

编译器/解析器 > 笔记
#技术 #捣鼓 #设计
Paradoxical 札记
https://blog.krysztal.dev/2025/05/12/Paradoxical-札记/
作者
Krysztal
发布于
2025年5月12日
许可协议