最简单的解析器库 (TSPL)

TSPL 是一个在 Rust 中工作的最简单的解析器库。

概念

在纯函数式语言如 Haskell 中，解析器可以表示为一个函数

Parser<A> ::= String -> Reply<A, Error>

这使我们能够为 Parser<A> 实现一个 Monad 实例，让我们可以使用 do-notation 创建简单而优雅的自定义类型解析器。遗憾的是，Rust 没有等效的功能。然而，我们可以通过以下方式轻松模拟它：

1. 使用结构和 impl 内部管理光标状态。

2. 返回一个 Result，这使我们能够使用 Rust 的 ? 来模拟单调块。

这个库仅公开了一些函数来实现以这种方式实现的解析器，除此之外没有其他功能。

示例

作为一个示例，让我们使用 TSPL 创建一个 λ-Term 解析器。

1. 实现你想要创建解析器的类型。

enum Term {
  Lam { name: String, body: Box<Term> },
  App { func: Box<Term>, argm: Box<Term> },
  Var { name: String },
}

2. 定义你的语法。我们将使用以下

<term> ::= <lam> | <app> | <var>
<lam>  ::= "λ" <name> " " <term>
<app>  ::= "(" <term> " " <term> ")"
<var>  ::= alphanumeric_string

3. 使用 new_parser()! 宏创建一个新的解析器。

TSPL::new_parser!(TermParser);

4. 使用你的语法创建一个 impl TermParser

impl<'i> TermParser<'i> {
  fn parse(&mut self) -> Result<Term, String> {
    self.skip_trivia();
    match self.peek_one() {
      Some('λ') => {
        self.consume("λ")?;
        let name = self.parse_name()?;
        let body = Box::new(self.parse()?);
        Ok(Term::Lam { name, body })
      }
      Some('(') => {
        self.consume("(")?;
        let func = Box::new(self.parse()?);
        let argm = Box::new(self.parse()?);
        self.consume(")")?;
        Ok(Term::App { func, argm })
      }
      _ => {
        let name = self.parse_name()?;
        Ok(Term::Var { name })
      }
    }
  }
}

5. 使用你的解析器！

fn main() {
  let mut parser = TermParser::new("λx(λy(x y) λz z)");
  match parser.parse() {
    Ok(term) => println!("{:?}", term),
    Err(err) => eprintln!("{}", err),
  }
}

完整的示例可在 ./examples/lambda_term.rs 中找到。使用以下命令运行它：

cargo run --example lambda_term

致谢

此设计基于 T6 为 HVM-Core 的新解析器，比旧的 HOPA 方法更干净。