Rust 实现一个表达式 Parser(8) Parser 实现

最困难的部分现已完毕了, 剩下的部分都非常简略

本文将完成 Parser 的中心逻辑

也便是运用上一篇文章封装好的 Parser Combinator 描绘文法

源码: src/parser/grammar.rs

回想一下

在这儿给出咱们上上篇文章定义好的文法

Expr   -> Add ;
Add    -> Mul (("+" | "-") Mul)* ;
Mul    -> Factor (("*" | "/") Factor)* ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

这儿为了少写冗余代码, 咱们再最后最后化简一步, 然后统一一下命名

Expr   -> Term (("+" | "-") Term)* ;
Term   -> Factor (("*" | "/") Factor)* ;
Factor -> "(" Expr ")"
        | Literal
        ;
Literal -> NUM ;

定义一下

在正式开端写之前, 应该先将 AST 上的节点类型定义一下, 这儿就直接用 enum 穷举, 源码方位在 src/parser/node.rs , 完成如下

#[derive(Debug, Clone, PartialOrd, PartialEq)]
pub enum Node {
    Literal {
        kind: SyntaxKind,
        value: i32,
        raw: String,
    },
    Expr {
        kind: SyntaxKind,
        left: Box<Node>,
        op: SyntaxKind,
        right: Box<Node>,
    },
}

需求注意的是, Expr 表明表达式节点, left 和 right 能够是 Expr 或者 Literal, 是一个递归类型, 因而需求运用 Box 包裹一下将实践内容存放到堆上, 否则编译器无法核算需求分配多少内存, 编译无法经过

写一下

直接开端写, 现在只需求根据现有的 Parser Combinator 来描绘文法就能够了

literal

Literal 文法如下

Literal -> NUM ;

代码如下, 运用 single_token 匹配出一个 NUM 类型的 Token, 再运用 map 将他映射为 Literal 节点类型即可

pub fn literal() -> impl Parser<'static, Node> {
    single_token(NUM).map(|(_, value)| Literal {
        kind: NUM,
        // 这儿直接调 unwrap 即可, 由于前面的 Lexer 能够确保必定能够被转为整数
        // 不考虑溢出的情况的话...
        value: value.parse().unwrap(),
        raw: value,
    })
}

factor

下一个是 Factor, 文法如下

Factor -> "(" Expr ")"
        | Literal
        ;

关于 "(" Expr ")" 咱们能够直接用一连串 and_then 来接连匹配, 如下

fn factor() -> impl Parser<'static, Node> {
    either(
        literal(),
        single_token(token!["("])
            // 这儿假定现已事前定义出 expr 函数
            .and_then(|_| expr())
            .and_then(|node| {
                single_token(token![")"])
                    .map(move |_| node.to_owned())
            }),
    )
}

term

Term 文法如下

Term -> Factor (("*" | "/") Factor)* ;

这儿咱们直接运用 zero_or_more 来将 ("*" | "/") Factor) 匹配 0 次或更屡次, 咱们先不考虑节点的构建, 搭出结构如下

fn term() -> impl Parser<'static, Node> {
    factor().and_then(|left| {
        // 将传入 Parser 重复匹配 0 次或更屡次
        zero_or_more(
            either(
                single_token(token!["*"]),
                single_token(token!["/"])
            ).and_then(|(op, _)| {
                // 这儿将整个结果映射为一个二元组 (操作符, 操作数)
                factor().map(move |right| (op, right))
            }),
        )
        // 运用 map 将匹配到的内容映射为 Node 类型
        .map(move |node_list| {
            // TODO 怎么构建 Expr 节点
        })
    })
}

这儿简略的解说一下

• zero_or_more 会将给定的 Parser 重复匹配 0 次或更屡次, 返回值是一个装有匹配结果的 Vector
• 在上面的完成中, zero_or_more 内部的 Parser 将输出映射为一个二元组, 包含操作符以及操作数, 详细类型为 (SyntaxKind, Node)
• 整个 zero_or_more 的输出便是一个装有这个二元组的 Vector, 详细来说, 输出类型为 Vec<(SyntaxKind, Node)>

咱们先暂时疏忽这儿的节点构建, 先完成最后一个 Expr 的文法描绘

expr

这儿其实是 Term 的镜像版别, 因而就不多做解说了, 文法如下

Expr -> Term (("+" | "-") Term)* ;

完成如下

pub fn expr() -> impl Parser<'static, Node> {
    term().and_then(|left| {
        zero_or_more(
            either(
                single_token(token!["+"]),
                single_token(token!["-"])
            ).and_then(|(op, _)| {
                term().map(move |right| (op, right))
            }),
        )
        .map(move |node_list| {
            // TODO 怎么构建 Expr 节点
        })
    })
}

build_expr_node

经过上面的完成, 能够发现, 目前能够抽离一个用来构建表达式节点的公用函数, 由于 expr 和 term 都会需求, 并且他们的结构几乎相同, 下面就来完成

先来看看 Expr 节点的结构

pub enum Node {
    Expr {
        kind: SyntaxKind,
        left: Box<Node>,
        op: SyntaxKind,
        right: Box<Node>,
    },
}

Expr 的 left 和 right 都是一个递归类型, 那么咱们应该怎么来构建呢, 详细来说便是该怎么来构建这棵 AST

看这个比如 "1 + 2 + 3"

假如咱们期望按照正常核算顺序来核算的话, 结合之前说到的 AST 的遍历顺序, 这棵树应该长下面这样

那么 "1 + 2 + 3 + 4" 呢, 长这样

咱们会发现, 这棵树总是应该往左下角成长

其实这儿是存在问题的, 由于 AST 往左下角成长意味着左递归, 而咱们运用的解析算法无法处理左递归的文法, 因而在前面的文章中就对左递归问题进行过消除, 实践上是改写成了右递归

这儿就产生了一个抵触, 咱们期望经过非左递归的文法, 解析出一棵左递归的树, 因而这儿不行能从文法层面去完成这个需求

只能把 向左递归成长 的逻辑完成在这个函数里边, 那么每个 Expr 有 left, right 字段, 对应联系又怎么呢, 以下简略打开一下

举例如 "1 + 2 + 3", 他会匹配 Expr 的文法

Expr -> Term (("+" | "-") Term)* ;

对 Expr 进行简略的整理并推导打开

咱们期望优先核算 1 + 2, 这意味着 "1 + 2" 应该独自构成一个 Expr 并作为子节点, 则有

而带上右边的 "+ 3" 时, 1 + 2 构成的 Expr 就应该作为这个表达式的左子节点, 如下

这样咱们就得到了咱们期望中的往左递归成长的树

下面再将无关的标识去掉, 只重视各个部分与 left, right 字段的对应联系, 如下

经过分析, 详细完成还是比较简略的, 结合上文说到的 node_list 的类型, 完成如下

fn build_expr_node(expr: Node, mut node_list: Vec<(SyntaxKind, Node)>) -> Node {
    match node_list.len() {
        // 若当时 node_list 为空, 回溯
        0 => expr,
        // 当时 node_list 不为空, 递归构建
        _ => {
            // 这儿现已对 node_list 长度进行过判别, 能够放心 unwrap
            let (op, right) = node_list.pop().unwrap();
            // 构建表达式节点
            Expr {
                kind: match op {
                    token!["+"] => ADD_EXPR,
                    token!["-"] => SUB_EXPR,
                    token!["*"] => MUL_EXPR,
                    token!["/"] => DIV_EXPR,
                    // 这儿应该直接 panic
                    _ => UNKNOW,
                },
                // 向左递归构建子树
                left: Box::new(build_expr_node(expr, node_list)),
                op,
                right: Box::new(right),
            }
        }
    }
}

如上就能够完成节点的递归构建, 最主要的是需求理清文法中各部分在 Expr 中对应的角色, 详细一点说便是需求理清文法中各部分在 Expr 中要赋值给哪个字段

完善一下

如上完成了 build_expr_node 函数, 现在现已能够来完善前面的部分了

/// Expr -> Term (("+" | "-") Term)*
pub fn expr() -> impl Parser<'static, Node> {
    term().and_then(|left| {
        zero_or_more(
            either(
                single_token(token!["+"]),
                single_token(token!["-"])
            ).and_then(|(op, _)| {
                term().map(move |right| (op, right))
            }),
        )
        .map(move |node_list| build_expr_node(left.to_owned(), node_list))
    })
}
/// Term -> Factor (("*" | "/") Factor)*
fn term() -> impl Parser<'static, Node> {
    factor().and_then(|left| {
        zero_or_more(
            either(
                single_token(token!["*"]),
                single_token(token!["/"])
            ).and_then(|(op, _)| {
                factor().map(move |right| (op, right))
            }),
        )
        .map(move |node_list| build_expr_node(left.to_owned(), node_list))
    })
}

跑一下

别跑了, 我在源码里边写了很多测验用例, 太长了, 而且很丑, 就不 copy 过来了, 代码是没问题的

模块导出

目前现已完成了 parser 的大部分逻辑, 简略封装一个函数作为模块导出

源码: src/parser/mod.rs

pub fn syntax(tokens: TokenStream) -> Result<Node, String> {
    match expr().parse(tokens) {
        Ok((_, n)) => Ok(n),
        Err(output) => Err(format!(
            "panic at parsing `{}`",
            output.iter().fold(String::new(), |mut res, (_, cur)| {
                res.push_str(cur);
                res
            })
        )),
    }
}

Q&A

Q: 为什么变量名一向改来改去的?

A: 最开端书写文法的时分, 为了看起来更明晰, 就选择 Add 和 Mul 为文法命名, Expr -> Add 这种文法其实是没有意义的, 由于只要一个产生式, 适当于是整了个别名, 实践完成的时分就没必要存在, 因而就干脆一点把这条冗余的规矩去掉了, 然后对应的修改了一下文法命名, 其实应该是不影响阅览和理解的

Q: 上篇文章说 Parser Combinator 高雅, 高雅在哪?

A: 很奇特的一点就在于传说可读性差的函数式编程范式, 在这儿可读性意外的高, 只需求把变量名连在一起读就能读懂大约的意思, 此外笔者在完成的时分发现 Parser Combinator 的设计还意外的契合软件工程中 高复用, 细粒度, 高可控, 易测验 的理念, 简略来说便是每个 Parser 和 Combinator 都是 小类短方法, 这儿的开发体验真的不错, 当然也由于代码量很小, 可是好歹看起来挺明晰挺舒服的