Rust 实现一个表达式 Parser(7) Parser Combinator-六虎

本文将完结一套简略的 Parser Combinator 作为 Parser 东西

或许会有一点点麻烦, 不过一切都是很值得的, 因为用起来真的很省心

在这儿放一下目前高 Star 的 Rust Parser Combinator 库 nom

对应源码 src/parser/parser_combinator

本文完结的 Parser Combinator 是参阅了一位外国大佬的博客并依据需求进行了修改, 不过真实找不到原文链接了, 在此提前抱歉

Parser Trait

在开端之前, 咱们先将相关的类型定义好, 如下

// 单次解析的成果
pub type ParserResult<Output> = Result<(TokenStream, Output), TokenStream>;
// 完结了这个 Trait 就认为是一个 Parser
pub trait Parser<'input, Output> {
    fn parse(&self, input: TokenStream) -> ParserResult<Output>;
}

这儿随手完结出一般的 Parser

impl<'input, Output, F> Parser<'input, Output> for F
where
    F: Fn(TokenStream) -> ParserResult<Output>,
{
    fn parse(&self, input: TokenStream) -> ParserResult<Output> {
        self(input)
    }
}

解释一下, 这儿为一切满意 Fn(TokenStream) -> ParserResult<Output> 的函数完结了 Parser Trait, 这个函数上会存在一个 parse 办法, 直接看一下例子

fn get_a_parser_like_function() -> impl Parser<i32> {
    |input: TokenStream| {
        Ok((input, 666))
    }
}

上面这个函数 get_a_parser_like_functon 回来一个闭包函数, 这个闭包函数满意 Parser Trait 的束缚, 也就意味着, 这个被回来出去的闭包函数便是一个 Parser, 具体运用办法如下

let parser = get_a_parser_like_function();
let input = vec![];
let parse_result = parser.parse(input);

BoxedParser

为了便于支撑后续的链式调用, 再独自封装一个特殊的结构体, 如下

pub struct BoxedParser<'input, Output> {
    // 这儿的 parser 是一个 Trait Bound 对象
    // 意为这个 Box 里面塞的东西有必要完结了 Parser Trait
    pub parser: Box<dyn Parser<'input, Output> + 'input>,
}
impl<'input, Output> BoxedParser<'input, Output> {
    pub fn new<P>(parser: P) -> Self
    where
        P: Parser<'input, Output> + 'input,
    {
        BoxedParser {
            parser: Box::new(parser),
        }
    }
}

为 BoxedParser 随手完结 Parser Trait

impl<'input, Output> Parser<'input, Output> for BoxedParser<'input, Output> {
    fn parse(&self, input: TokenStream) -> ParserResult<Output> {
        // 调用 parser 上的 parse 办法来进行解析
        self.parser.parse(input)
    }
}

这样咱们就完结准备工作了

API 完结

因为解析的内容比较简略, 并没有用到一些杂乱的 Combinator, 以下的完结都十分简略, 因而就直接贴出代码加个测试用例

atom

这个 Parser 能够获取 Token 流中的下一个 Token

pub fn atom<'input>() -> impl Parser<'input, Token> {
    move |input: TokenStream| {
        // 获取迭代器
        let mut it = input.iter();
        match it.next() {
            Some(next) => Ok((
                // 下次输入需求跳过一项
                input.iter().skip(1).map(|t| t.to_owned()).collect(),
                // 本次输入为当时这一项
                next.to_owned(),
            )),
            // 若输入流为空, 则直接原样回来
            None => Err(input),
        }
    }
}

运用举例如下

#[test]
fn test_atom() {
    let input = vec![(NUM, "1".to_string()), (NUM, "2".to_string())];
    assert_eq!(
        Ok((vec![(NUM, "2".to_string())], (NUM, "1".to_string()))),
        atom().parse(input)
    );
}

map

这个 Combinator 能够对一个 Parser 的解析成果进行映射, 作用相似 Iterator::map

pub fn map<'input, P, Output, MapFn, NewOutput>(
    parser: P,
    map_fn: MapFn,
) -> impl Parser<'input, NewOutput>
where
    P: Parser<'input, Output>,
    MapFn: Fn(Output) -> NewOutput,
{
    move |input| {
        parser
            .parse(input)
            // parse 的回来值是一个 Result
            // 这儿直接调用 Result::map 来将该 Parser 的成果映射为 map_fn 的回来值
            .map(|(next_input, output)| (next_input, map_fn(output)))
    }
}

运用如下, 这儿运用 map 将 atom 的解析成果映射为 (PLUS, "+")

 #[test]
fn test_map() {
    let input = vec![(NUM, "1".to_string()), (NUM, "2".to_string())];
    assert_eq!(
        Ok((vec![(NUM, "2".to_string())], (PLUS, "+".to_string()))),
        map(atom(), |_| (PLUS, "+".to_string())).parse(input)
    );
}

and_then

这个 Combinator 能够连续执行两个 Parser, 只有两个 Parser 都成功了才会成功

pub fn and_then<'input, CurParser, CurOutput, NextFn, NextParser, NextOutput>(
    cur_parser: CurParser,
    next_fn: NextFn,
) -> impl Parser<'input, NextOutput>
where
    CurParser: Parser<'input, CurOutput>,
    NextFn: Fn(CurOutput) -> NextParser,
    NextParser: Parser<'input, NextOutput>,
{
    move |input| {
        // 测验第一个 Parser 是否成功
        match cur_parser.parse(input) {
            // 若成功则测验第二个 Parser
            // 留意这儿第二个 Parser 的输入是第一个 Parser 的输出
            Ok((next_input, cur_output)) => {
                match next_fn(cur_output).parse(next_input) {
                    // 若两个 Parser 都成功, 最终回来第二个 Parser 的输出
                    Ok((final_input, next_output)) => Ok((final_input, next_output)),
                    Err(err) => Err(err),
                }
            },
            // 不然原样回来当时输入
            Err(err) => Err(err),
        }
    }
}

运用如下

#[test]
fn test_and_then() {
    let input = vec![(NUM, "1".to_string()), (NUM, "2".to_string())];
    assert_eq!(
        Ok((vec![], (NUM, "2".to_string()))),
        and_then(atom(), |_| { atom() }).parse(input)
    )
}

这儿或许比较含糊, 解释一下:

这儿第一个 Parser 是一个 atom, 会匹配到 (NUM, "1")
第二个 Parser 也是一个 atom, 会匹配到 (NUM, "2")
input 中只有这两项
解析完结后, input 变成了一个空的 Vector, 输出则是第二个解析的成果 (NUM, "2")

judge

这个 Combinator 能够运用一个判断函数来控制一个 Parser 是否回来成果

pub fn judge<'input, P, Output, JudgeFn>(
    parser: P,
    judge_fn: JudgeFn,
) -> impl Parser<'input, Output>
where
    P: Parser<'input, Output>,
    JudgeFn: Fn(&Output) -> bool,
{
    move |input: TokenStream| {
        match parser.parse(input.clone()) {
            // 若解析成功, 且 judge_fn 回来 true
            // 则回来解析成果
            Ok((next_input, output)) if judge_fn(&output) => Ok((next_input, output)),
            _ => Err(input),
        }
    }
}

运用如下

#[test]
fn test_judge() {
    let input = vec![(PLUS, "+".to_string())];
    assert_eq!(
        Ok((vec![], (PLUS, "+".to_string()))),
        judge(atom(), |(kind, _)| *kind == PLUS).parse(input)
    )
}

either

这个 Combinator 能够从两个 Parser 挑选一个成功的 Parser 执行, 优先第一个

pub fn either<'input, P1, P2, Output>(parser1: P1, parser2: P2) -> impl Parser<'input, Output>
where
    P1: Parser<'input, Output>,
    P2: Parser<'input, Output>,
{
    move |input: TokenStream| {
        // 若 parser1 解析成功则回来 parser1 的解析成果
        match parser1.parse(input.clone()) {
            Ok((next_input, output)) => Ok((next_input, output)),
            // 若 parser1 解析失利则回来 parser2 的解析成果
            Err(_) => parser2.parse(input),
        }
    }
}

运用如下

#[test]
fn test_either() {
    let input = vec![(NUM, "1".to_string())];
    // 解析一个 NUM 类型的 Token
    let number_parser = judge(atom(), |(kind, _)| *kind == NUM);
    // 解析一个 PLUS 类型的 Token
    let plus_parser = judge(atom(), |(kind, _)| *kind == PLUS);
    assert_eq!(
        Ok((vec![], (NUM, "1".to_string()))),
        either(number_parser, plus_parser).parse(input)
    )
}

zero_or_more

这个 Combinator 能够将一个 Parser 重复匹配 0 次或更屡次

pub fn zero_or_more<'input, P, Output>(parser: P) -> impl Parser<'input, Vec<Output>>
where
    P: Parser<'input, Output>,
{
    move |mut input: TokenStream| {
        // 保存解析成果
        let mut result = Vec::new();
        // 本次的输出应该作为下一次循环中 parser 的输入
        while let Ok((next_input, item)) = parser.parse(input.clone()) {
            input = next_input;
            result.push(item)
        }
        Ok((input, result))
    }
}

运用如下

#[test]
fn test_zero_or_more() {
    let num_one = (NUM, "1".to_string());
    // 匹配一个 (NUM, "1")
    let num_parser = judge(atom(), |(kind, text)| *kind == NUM && text == "1");
    let input = vec![];
    // 将 (NUM, "1") 匹配了 0 次
    assert_eq!(Ok((vec![], vec![])), zero_or_more(num_parser).parse(input));
    // 匹配一个 (NUM, "1")
    let num_parser = judge(atom(), |(kind, text)| *kind == NUM && text == "1");
    let input = vec![num_one.clone(), num_one.clone(), num_one.clone()];
    // 将 (NUM, "1") 匹配了 3 次
    assert_eq!(
        Ok((
            vec![],
            vec![num_one.clone(), num_one.clone(), num_one.clone()]
        )),
        zero_or_more(num_parser).parse(input)
    );
}

single_token

这个 Parser 能够测验匹配一个希望的 SyntaxKind 类型

pub fn single_token(expect: SyntaxKind) -> impl Parser<'static, Token> {
    // 结合 atom 和 judge 能够很轻松的完结这个需求
    judge(atom(), move |(kind, _)| *kind == expect)
}

运用如下

#[test]
fn test_single_token() {
    let input = vec![(PLUS, "+".to_string())];
    assert_eq!(
        Ok((vec![], (PLUS, "+".to_string()))),
        single_token(PLUS).parse(input)
    )
}

完结链式调用

目前咱们现已完结了要用到的一切东西函数, 但运用起来仍然感觉不行灵敏不行舒服, 因而来凭借 BoxedParser 完结链式调用

咱们将上面封装好的一些函数直接添加到 Parser Trait 中并给予默认完结, 这样任何一个 Parser 都能够链式调用这些办法

完结如下, 添加了 map, and_then, or 三个办法, 这儿的 or 便是 either, 只不过以中缀方式存在的话, 叫 or 会更加贴切一点

pub trait Parser<'input, Output> {
    fn parse(&self, input: TokenStream) -> ParserResult<Output>;
    fn map<MapFn, NewOutput>(self, map_fn: MapFn) -> BoxedParser<'input, NewOutput>
    where
        Self: Sized + 'input,
        Output: 'input,
        NewOutput: 'input,
        MapFn: Fn(Output) -> NewOutput + 'input,
    {
        BoxedParser::new(map(self, map_fn))
    }
    fn and_then<NextFn, NextParser, NextOutput>(
        self,
        next_fn: NextFn,
    ) -> BoxedParser<'input, NextOutput>
    where
        Self: Sized + 'input,
        Output: 'input,
        NextParser: Parser<'input, NextOutput> + 'input,
        NextFn: Fn(Output) -> NextParser + 'input,
        NextOutput: 'input,
    {
        BoxedParser::new(and_then(self, next_fn))
    }
    fn or<OtherParser>(self, other_parser: OtherParser) -> BoxedParser<'input, Output>
    where
        Self: Sized + 'input,
        Output: 'input,
        OtherParser: Parser<'input, Output> + 'input,
    {
        BoxedParser::new(either(self, other_parser))
    }
}

能够看到, 这儿几乎没有写任何逻辑, 只是调用了事前封装好的函数, 再将回来的 Parser 用 BoxedParser 包裹并回来, 这样相当于又回来了一个完结了 Parser Trait 的对象, 因而就能够完结链式调用

#[test]
fn test_chained_call() {
    let input = vec![(NUM, "1".to_string())];
    assert_eq!(
        Ok((vec![], (PLUS, "+".to_string()))),
        atom().map(|_| (PLUS, "+".to_string())).parse(input)
    );
}

How it works

这儿特意将这个内容放到最终来说, 是希望读者能在大致过了一遍前面的源码完结后再来看这一部分, 咱们先来看一段简略的代码

#[test]
fn data_stream() {
    let input = vec![
        (NUM, "1".to_string()),
        (PLUS, "+".to_string()),
        (NUM, "2".to_string()),
    ];
    assert_eq!(
        Ok((
            vec![(PLUS, "+".to_string()), (NUM, "2".to_string())],
            (PLUS, "1".to_string())
        )),
        judge(atom(), |(kind, _)| *kind == NUM)
            .map(|(_, text)| (PLUS, text))
            .parse(input)
    );
}

回想笔者在前面的文章中提到的, “FP 的工作办法相似一条流水线“, 咱们现在将 TokenStream 视为一条流水线, 将 Parser 和 Combinator 想象为流水线上面的某台机器或者闸门, 如下

留意, 这儿示意图为了明晰简洁, 和实践解析顺序不同, 但是大致的工作办法是没问题的

Rust 实现一个表达式 Parser(7) Parser Combinator

这条流水线上面有许多的 Token 流过, 通过一层层阀门的加工和挑选, 直到最终被彻底挑选处理完毕, 解析完毕

咱们独自来看 atom 到 any parser 这段

一开端 [NUM, PLUS, NUM] 作为输入流入 atom
atom 解析成功后, 将 NUM 作为输出流入岔道, 剩下部分 [NUM, PLUS] 作为下一次输入继续在流水线上活动, 作为 any parser 的输入

咱们再来看岔道上这段

atom 解析成功, 输出 NUM 作为输入流入到 judge
judge 希望一个 NUM, 解析成功, 原样输出到 map
map 接收到 NUM, 将 NUM 映射为 PLUS, 输出

以上便是大致的工作办法

咱们组合不同的 Parser 的进程便是在搭建这条流水线, 通过控制输入输出来在流水线分出岔道并设置相应的条件, 而调用 Parser Trait 上面的 parse 办法相当所以把某个地方的阀门打开, 让数据流能够流入, 而最外层的 parse 办法的调用便是控制整条数据流的流入时机

Q&A

Q: 这么长的调用链不会爆栈么?

A: 好问题, 我一开端也有过相似的忧虑, 现在这个 tiny-expr-parser 比较简略, 如果不是拿家里座机跑的话应该不至于爆栈, 我在另一个相似性质的项目里 debug parser 部分逻辑的时分看到调用栈心里一紧, 其实 Parser Combinator 是函数式风味很重的一种解决方案, 最开端貌似是 haskell 那边搞出来的, 纯函数式言语的内存管理策略一般与其他类型的言语不同, 我记得是需求专门针对 gc 做优化的, 因为在纯函数式言语里会存在很多的高高高高阶函数, 或许一调用瞬间就会发生很多的临时变量, 又会在一会儿全部变成废物, 这点与其他言语区别极大, 像 Rust, Java, Js 这样的言语的内存应该是缓步上升的(我猜的), 我之前读到一篇文章, 据说在纯函数式言语里, 能把内存分配优化到比原地修改还要快, 因而这个在纯函数式言语里应该不是问题, 在其他言语中呢? 反正我目前的实践中, 除非遇到左递归, 不然还没爆过栈, 所以放心写吧

Q: 为什么写的这么丑?

A: 一方面我觉得 Rust 的生命周期标示和 Trait Bound 的确有点影响可读性, 另一方面我觉得不能以阅览指令式编程的办法来阅览函数式编程的代码, 将每个函数视为一个黑盒, 只关注函数名, 输入, 输出, 这样还是蛮好读的, 并且到下一篇正式完结 Parser 的时分会发现其实 Parser Combinator 挺高雅的

Rust 实现一个表达式 Parser(7) Parser Combinator

Parser Trait

BoxedParser

API 完结

atom

map

and_then

judge

either

zero_or_more

single_token

完结链式调用

How it works

Q&A

相关文章

Firewalld防火墙基础

幻兽帕鲁来啦！京东云召唤你一键开服，快来私服联机

天气太热，希望这个小风扇能给你带来一点凉意

go chan 设计与实现

作者信息