行将正式进入 tiny-expr-parser 的完结, 本文将大致介绍项目全体结构

终究目标

  • 解析疑似表达式的字符串, 构建 AST
  • 依据 AST 对表达式进行求值
  • 依据 AST 对表达式进行格式化

用例如下

#[test]
fn smoke() {
    let expr = "1*2+(3/(4+(-5)))";
    let ast = build_ast(expr).unwrap();
    assert_eq!(-1, eval(&ast));
    assert_eq!("1 * 2 + 3 / (4 + (-5))", format(&ast));
}

进程

以下三个进程分别对应源码中的三个模块

词法剖析: “src/lexer” 语法剖析: “src/parser” 遍历: “src/traversal”

词法剖析

该阶段需求将传入的表达式字符串处理为 Token 流, 如

Rust 实现一个表达式 Parser(2) 整体设计

留意, 该进程会忽略空格, 当解析到 001 这样的非法输入时应直接报错

这儿在项目中是完结了一个 DFA(Deterministic Finite Automaton)确认有限状况自动机, 详细阐明及完结能够看下篇文章

语法剖析

该阶段接收传入的 Token 流, 并构建 AST, 如

Rust 实现一个表达式 Parser(2) 整体设计

该阶段应正确处理不同表达式的优先级, 并体现在 AST 的结构中

值得一提的是, 这儿在实践完结时会运用 Parser Combinator 来描绘文法, 以下简略介绍一下

Parser 技术

编译器前端的完结存在大量机械性的重复逻辑, 因而很天经地义的出现了一些相关的自动生成东西, 现在有以下两种

  • Parser Generator
    • 依据界说的文法生成一个能够直接运转的编译器前端代码文件
    • 如 yacc,antlr
  • Parser Combinator
    • 运用不同的 Parser 组合子来直接描绘文法
    • 通常作为一个库来完结
    • 如 ts,rust, haskell

以下是运用 Parser Combinator 匹配一个数字节点的代码

pub fn literal() -> impl Parser<Node> {
    single_token(NUM).map(|(_, value)| Literal {
        kind: NUM,
        value: value.parse().unwrap(),
        raw: value,
    })
}

tiny-expr-parser 完结初衷是为了简略了解一下编译前端的详细细节, 因而就仍是选择用 Parser Combinator 来完结, 更详细的原因见 PS

两者基本都能够完结需求, 不过通常情况下, Parser Generator 的功能会比 Parser Combinator 高, 但是貌似有一些技术能够优化 Parser Combinator, 让其效率提高到与 Parser Generator 简直无异

遍历

关于树形结构的遍历思路大致上有两种, 广度优先(DFS)和深度优先(BFS), 这儿该怎么选择遍历思路呢

如上文说到的表达式 "1 * (2 + 3)" 的 AST

Rust 实现一个表达式 Parser(2) 整体设计

咱们期望的计算次序是先履行 (2 + 3), 成果为 5, 再履行 1 * 5, 得出终究成果 5

咱们能够优先拜访左子节点, 再拜访右子节点, 得出两个子节点的值之后再履行根节点指定的运算, 那么咱们就能够凭借 DFS 的回溯进程天然的将表达式的值回来到上一层, 若是运用 BFS 则会在完结上带来必定的费事

而 DFS 若是在寻常二叉树上进行的话会非常简略, 一个递归函数就能够完结, 不过对 AST 来说, 遍历是需求特殊处理一下的, 剧透一下看看该项目中的数字节点 Literal 和表达式节点 Expr 的类型界说

/// 枚举所有 AST 的节点类型
pub enum Node {
    Literal {
        kind: SyntaxKind, // 节点类型
        value: i32,       // 节点实践值
        raw: String,      // 节点原本在字符串中的样子
    },
    Expr {
        kind: SyntaxKind, // 节点类型
        left: Box<Node>,  // 表达式的左操作数
        op: SyntaxKind,   // 表达式的操作符
        right: Box<Node>, // 表达式的右操作数
    },
}

能够看到, 在 Literal 节点中, 咱们期望拜访的应该是其 value 字段, 而在 Expr 节点中, 咱们期望拜访的是 left, op, right 字段, 简略来说便是依据不同的节点类型有不同的拜访逻辑, 因而不能用寻常的完结方式

针对这个需求, 需求运用拜访者形式(Visitor Mode)来进行完结 AST 的 DFS, 将不同的拜访逻辑封装在不同的 visit_xxx 方法中来完结, 详细会在对应文章中打开

PS

关于为什么运用 Parser Combinator 解释一下自己的考虑

我尝试过完结 Parser Generator

完结起来非常繁琐, 并且从我写的测验 Demo 来看, 我生成的的前端全体功能和可读性都底子完全完全无法和 Parser Combinator 的版别比, 首要是因为并没有很好的进行优化, 仍是研讨的不够多, 但是首要仍是太费事太复杂而且生成出来太丑

我觉得 Parser Combinator 很灵敏

运用 Parser Combinator 是在通过组合不同的 Parser 来描绘文法, 操作空间很大, 并且能很好的把握其间的流程细节

我觉得 Parser Combinator 开发体会极好

Parser Combinator 是一种函数式风味很重的 Parser 完结思路, 由于个人对 FP 仍是一知半解, 就不引入范畴论的相关术语, 只谈开发进程中实践体会到的, 每个 Parser 都是一个纯函数, 组合过后的 Parser 也仍是一个 Parser, 承受一个输入, 回来一个输出, 这个进程没有任何的副作用, 这意味着承受的输入相同, 回来的值也必定相同, 这是纯函数带来的极大好处, 测验时也是极为方便

我觉得 FP 很有意思

依照个人的观点, FP 中的函数是对进程的笼统, 笼统的是不同的行为, 是动词, 而以 OOP 为例, 其他编程范式通常是对物体进行笼统, 是名词, 从某个视点来看, FP 就像把整个数据视为一条流水线, 而每个不同的函数都是流水线上的熟练工人, 每个工人都能够稳定的完结必定程度的简略使命, 终究流水线的止境便是我所期待的产品, 在开发进程中, 不需求关怀外部状况的问题, 只需求重视当前函数的输入和输出, 终究拼装起来就能够完结全体需求, 这样的开发体会很奇妙