用 Rust 实现编译器 (一): Lexer & Parser

之前暑假的时候就已经有用 Rust 写编译器的打算了, 一方面是想实现一个内存安全且性能不差的编译器, 另一方面也想复健一下 Rust 水平；但是后来因为老师要求暑假要写完 optimize 就不了了之了. 寒假心血来潮, 就决定继续把这个坑填完.

编译原理基础

之前暑假的时候郑老板花一节课时间简单讲过编译器的词法语法分析, 但是当时好像听的似懂非懂；因为有 antlr 就也没有多花功夫. 这次重新看了一下龙书和网上资料, 简单学了学这些基础知识.

上下文无关文法

定义

• 终结符号: terminal node, 最小单元
• 非终结符号: 就是多个符号的组合
• 产生式: 构造非终结符号的方法, 如 A -> aB

二义性: 一个表达式可以生成多棵语法分析树, 例如 A + B + C 可以解释为 (A + B) + C 或者 A + (B + C). 优先级: * 比 + 高, a + b * c 应解释为 a + (b * c). 结合性: 一个运算数的两边都有符号时, 应当优先考虑哪边的, 如 - 是左结合的, a - b - c 应解释为 (a - b) - c.

词法分析

• 正则表达式
• 状态转换图
  • 将词法分析的不同结果和中间过程以状态的形式表达
  • 每一输入字符代表图上每个节点的一条出边
• 有限状态自动机
  • DFA 和 NFA
  • 根据状态转换图实现词法分析

语法分析

• 朴素的自顶向下分析: 选定一个终结符号作为起始, 依次匹配每一条规则, 若遇到错误就回溯尝试匹配下一条.
• 递归下降分析: 对表达式树做自顶向下分析, look ahead 若干符号, 每一组符号可以对应唯一的下一层节点.
  • 问题: 左递归；解决方案: 改成右递归.
• Pratt Parsing: 通过 binding power 解决优先级和结合性的问题.
  • 交替使用递归和循环实现.
  • 在递归下降的基础上, 规定一个运算符的右儿子的左 binding power 必须低于自身的右 binding power.

Rust 的 Parser Generator: Pest

在 Java 和 C++ 中用过 antlr 了, 体验还是不错的. 而在 Rust 中, pest 是一个 Parser Generator 不错的选择.

与 antlr 有所区别的是, pest 需要自己完成部分 Parser 的解析任务, 即需要手动从一个线性结构生成树形 AST (在 antlr 中是通过 CST 生成 AST), 所以需要自己考虑一些优先级和解析顺序的问题. 不过 Mx 的语法不算复杂, 所以除了在 parse_expr 中手动定义 pratt parsing 以解决优先级和结合性问题外, 其他部分似乎都问题不大.

fn parse_expr(pair: Pair<Rule>) -> Result<Expr, Error> {
    PRATT_PARSER
        .map_primary(|primary| Self::parse_primary(primary))
        .map_prefix(|prefix, expr| Self::parse_prefix(prefix, expr.unwrap()))
        .map_infix(|lhs, op, rhs| Self::parse_infix(lhs.unwrap(), op, rhs.unwrap()))
        .map_postfix(|expr, postfix| Self::parse_postfix(postfix, expr.unwrap()))
        .parse(pair.into_inner())
}

生命周期与所有权

写 Rust 和 C++ 最大的一个区别就是要考虑引用的生命周期和变量的所有权, 万幸的是, 在 parser 部分, 由于是直接调用 pest 的接口, 很少会遇到相关的问题, 顶多就是在调用一些接口 (例如 find_tagged) 后 pair 的所有权会被转移, 所有有一些信息 (例如 loc) 可能需要手动 copy 一下.

很遗憾的是, 接下来的部分似乎就不是那么的风平浪静了…