65.9K
CodeProject 正在变化。 阅读更多。
Home

用 Rust 实现的 PEG 解析器组合子

刘俊峰
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2投票s)

2017年1月17日

CPOL

9分钟阅读

viewsIcon

10731

一个用 Rust 实现的 PEG 解析器组合子库，使用运算符重载而非宏。

引言

本文介绍了 pom，一个用 Rust 实现的 PEG 解析器组合子库，它使用运算符重载而不是宏。

为什么选择 Rust？

Rust

在学习了 C/C++ 和 C# 之后，我发现选择一门新的编程语言会极大地影响程序员的生产力。一方面，我一直在研究新语言。有数百种语言，我考察并选择我最喜欢的，我最喜欢的是 C#、Ruby、TypeScript 和 Rust。另一方面，我尝试自己设计一门新语言并实现一个编译器。

我喜欢 C# 提供的语法，但讨厌庞大的 .NET 运行时。对 CLR 的依赖使得分发用 C# 编写的应用程序变得非常困难。编译成本地代码一直是我对编程语言的期望。在 2003 年，我认为编译器可以通过在目标程序中的适当位置生成内存释放指令来摆脱垃圾回收器。但我没有深入研究这个机制的细节设计，我决定首先写一个能工作的编译器，然后一点一点地改进语言设计和编译器实现。

编译的第一阶段是解析。我尝试了一些解析器生成器，但对结果并不满意。然后我深入研究了解析理论，阅读了几本书，实现了 DFA、NFA、NFA 到 DFA 的转换、LL(1)、LR、LALR 算法，然后写了一个解析器来解析 BNF、EBNF 或 TBNF 语法文件，并生成与语法对应的解析器代码。

编译器的语法/语义分析和代码生成部分更加困难。我甚至尝试定义了一个中间汇编语言，当时我还不知道 LLVM。我编写编译器的努力中断了好几年，然后 Rust 诞生了。

乍一看，Rust 的语法有点奇怪，为什么用 fn 而不是 def，为什么用 let mut 而不是 var，它并没有吸引我。阅读 O'Reilly 的出版物 Why Rust? 后，我突然意识到这就是我试图构建的语言。当你真正开始使用 Rust 时，你会发现 fn 和 let mut 非常符合 Rust 的逻辑。对我来说，Rust 曾是梦想，如今成为现实。

Rust 的学习曲线很陡峭，比我之前学过的任何编程语言都更具挑战性。当你最终让你的程序正常工作并完善它时，所有这些学习都是值得的。面向对象的类层次结构不足以进行代码重用，Rust 的 enum、tuple、struct 和 trait 类型系统是更好的解决方案。我仍在想 Rust 编译器是否足够智能，可以消除所有生命周期参数，它们在读写程序时大部分是噪音和障碍。

什么是 PEG？

当我发现 PEG 时，我知道我之前所有的 LALR 工作都可以丢弃了。我使用 PEG 重写了我的解析器生成器。使用这个解析器生成器，我创建了一个 YAML 解析器 和一个 Lua 解释器。

解析表达式语法 (PEG) 是 上下文无关语法 (CFG) 的一种替代方案，用于形式化地指定语法。CFG 描述了一个生成语言字符串的规则系统，而 PEG 描述了一个识别语言字符串的规则系统。

CFG

PEG

与 CFG 不同，PEG 不会产生歧义；如果一个字符串能够解析，它就只有一个有效的解析树。我们通常直接通过识别方式来指定我们的语言，因此 PEG 既更贴近语法实践，又比确定性 CFG 更强大。

解析表达式

Expr 描述
ε 空字符串
a 终结符 (a ∈ Σ)
A 非终结符 (A ∈ N)
e1 e2 序列
e1 / e2 优先选择
e?, e*, e+ 可选，零次或多次，一次或多次
&e, !e 语法谓词

什么是解析器组合子？

当我第一次在 Haskell 世界听到 Parsec 时，我明白了解析器组合子的概念。

解析器 是一个函数，它将一个字符串（一系列符号）作为输入，并返回匹配结果作为输出。

组合子 是一个高阶函数（一个“泛函”），它接收零个或多个函数（每个函数类型相同）作为输入，并返回一个类型相同的同类新函数作为输出。

解析器组合子 是一个高阶函数，它接收解析器作为输入，并返回一个新的解析器作为输出。

解析器组合子允许你直接在宿主语言中编写语法规则并创建解析器，而无需分离的解析器生成步骤，因此整个过程更加流畅。

如何实现解析器组合子？

我深入思考了如何使用 Rust 提供的语言构造来实现解析器组合子。总的来说，有四种方法：

  1. 解析器作为闭包

    pub fn empty<I>() -> impl Fn(&mut Input<I>) -> Result<()> { 
  |_: &mut Input<I>| Ok(()) 
} 
 
pub fn term<I>(t: I) -> impl Fn(&mut Input<I>) -> Result<I> { 
    ...
} 
 
pub fn seq<'a, I>(tag: &'a [I]) -> impl Fn(&mut Input<I>) -> Result<&'a [I]> {
  ...
}
...
// To create a parser for integer
let parser = concatenate(optional(one_of("+-")), one_or_more(one_of("0123456789")));

    优点：实现代码少。

    缺点：不能重载运算符，可读性差。

  2. 解析器作为结构体

    pub struct Parser<I, O> {
    method: Box<Fn(&mut Input<I>) -> Result<O>>,
}

impl<I, O> Parser<I, O> {
    /// Create new parser.
    pub fn new<P>(parse: P) -> Parser<I, O>
        where P: Fn(&mut Input<I>) -> Result<O> + 'static
    {
        Parser { method: Box::new(parse) }
    }

    /// Apply the parser to parse input.
    pub fn parse(&self, input: &mut Input<I>) -> Result<O> {
        (self.method)(input)
    }
    ...
}

pub fn empty<I>() -> Parser<I, ()> {
    Parser::new(|_: &mut Input<I>| Ok(()))
}

pub fn term<I>(t: I) -> Parser<I, I> {
    ...
}
...
impl<I: Copy, O, U> Add<Parser<I, U>> for Parser<I, O> {
    type Output = Parser<I, (O, U)>;

    fn add(self, other: Parser<I, U>) -> Self::Output
        where I: 'static,
              O: 'static,
              U: 'static
    {
        Parser::new(move |input: &mut Input<I>| {
            let start = input.position();
            let result = self.parse(input)
                .and_then(|out1| other.parse(input).map(|out2| (out1, out2)));
            if result.is_err() {
                input.jump_to(start);
            }
            result
        })
    }
}
...
// To create a parser for integer
let parser = one_of("+-").opt() + one_of("0123456789").repeat(1..);

    优点：可以重载运算符，代码优雅。

    缺点：依赖编译器的零成本抽象来优化运行时性能。

    Crate pom 使用了这种方法。

  3. 解析器作为 trait

    pub trait Parser  {
  type I: ?Sized;
  type O;

  fn parse<'a>(&self, data: &'a Self::I) -> ParseResult<&'a Self::I, Self::O>;
}
      
pub trait ParserCombinator : Parser + Clone {
  fn then<P: Parser<I=Self::I>>(&self, p: P) -> ChainedParser<Self,P> {
    ChainedParser{first: self.clone(), second: p}
  }
  ...
}
      
pub fn opt<T: Parser>(t: T) -> OptionParser<T> {
  OptionParser{parser: t}
}

pub fn recursive<I:?Sized,O, F:  Fn() -> 
    Box<Parser<I=I,O=O>>>(f: F) -> RecursiveParser<I,O,F> {
  RecursiveParser{parser: Rc::new(f)}
}

...

pub struct ChainedParser<A,B> {
  first: A,
  second: B,
}
...
impl<C: ?Sized, A: Parser<I=C>, B: Parser<I=C>> Parser for ChainedParser<A, B> {
  type I = C;
  type O = (A::O,B::O);

  fn parse<'a>(&self, data: &'a Self::I) -> ParseResult<&'a Self::I, Self::O>{
    match self.first.parse(data) {
      Ok((a, d2)) => match self.second.parse(d2) {
        Ok((b, remain)) => Ok(((a, b), remain)),
        Err(err) => Err(err)
      },
      Err(err) => Err(err)
    }
  }
}

impl<C: ?Sized, A: ParserCombinator<I=C>, 
     B: ParserCombinator<I=C>>  Clone for ChainedParser<A, B> {
    ...
}
...

    优点：可以重载运算符。

    缺点：代码臃肿。

    Crate peruse 使用了这种方法。

  4. 解析器作为宏

    #[macro_export]
macro_rules! do_parse (
  (__impl $i:expr, $consumed:expr, ( $($rest:expr),* )) => (
    $crate::IResult::Done($i, ( $($rest),* ))
  );

  (__impl $i:expr, $consumed:expr, $e:ident >> $($rest:tt)*) => (
    do_parse!(__impl $i, $consumed, call!($e) >> $($rest)*);
  );
  (__impl $i:expr, $consumed:expr, 
     $submac:ident!( $($args:tt)* ) >> $($rest:tt)*) => (
    {
      match $submac!($i, $($args)*) {
        $crate::IResult::Error(e)      => $crate::IResult::Error(e),
        $crate::IResult::Incomplete($crate::Needed::Unknown) =>
          $crate::IResult::Incomplete($crate::Needed::Unknown),
        $crate::IResult::Incomplete($crate::Needed::Size(i)) =>
          $crate::IResult::Incomplete($crate::Needed::Size($consumed + i)),
        $crate::IResult::Done(i,_)     => {
          do_parse!(__impl i,
            $consumed + ($crate::InputLength::input_len(&($i)) -
                         $crate::InputLength::input_len(&i)), $($rest)*)
        },
      }
    }
  );

  (__impl $i:expr, $consumed:expr, $field:ident : $e:ident >> $($rest:tt)*) => (
    do_parse!(__impl $i, $consumed, $field: call!($e) >> $($rest)*);
  );

  (__impl $i:expr, $consumed:expr, 
   $field:ident : $submac:ident!( $($args:tt)* ) >> $($rest:tt)*) => (
    {
      match  $submac!($i, $($args)*) {
        $crate::IResult::Error(e)      => $crate::IResult::Error(e),
        $crate::IResult::Incomplete($crate::Needed::Unknown) =>
          $crate::IResult::Incomplete($crate::Needed::Unknown),
        $crate::IResult::Incomplete($crate::Needed::Size(i)) =>
          $crate::IResult::Incomplete($crate::Needed::Size($consumed + i)),
        $crate::IResult::Done(i,o)     => {
          let $field = o;
          do_parse!(__impl i,
            $consumed + ($crate::InputLength::input_len(&($i)) -
                         $crate::InputLength::input_len(&i)), $($rest)*)
        },
      }
    }
  );

  // ending the chain
  (__impl $i:expr, $consumed:expr, $e:ident >> ( $($rest:tt)* )) => (
    do_parse!(__impl $i, $consumed, call!($e) >> ( $($rest)* ));
  );

  (__impl $i:expr, $consumed:expr, 
   $submac:ident!( $($args:tt)* ) >> ( $($rest:tt)* )) => (
    match $submac!($i, $($args)*) {
      $crate::IResult::Error(e)      => $crate::IResult::Error(e),
      $crate::IResult::Incomplete($crate::Needed::Unknown) =>
        $crate::IResult::Incomplete($crate::Needed::Unknown),
      $crate::IResult::Incomplete($crate::Needed::Size(i)) =>
        $crate::IResult::Incomplete($crate::Needed::Size($consumed + i)),
      $crate::IResult::Done(i,_)     => {
        $crate::IResult::Done(i, ( $($rest)* ))
      },
    }
  );

  (__impl $i:expr, $consumed:expr, 
   $field:ident : $e:ident >> ( $($rest:tt)* )) => (
    do_parse!(__impl $i, $consumed, $field: call!($e) >> ( $($rest)* ) );
  );

  (__impl $i:expr, $consumed:expr, 
   $field:ident : $submac:ident!( $($args:tt)* ) >> ( $($rest:tt)* )) => (
    match $submac!($i, $($args)*) {
      $crate::IResult::Error(e)      => $crate::IResult::Error(e),
      $crate::IResult::Incomplete($crate::Needed::Unknown) =>
        $crate::IResult::Incomplete($crate::Needed::Unknown),
      $crate::IResult::Incomplete($crate::Needed::Size(i)) =>
        $crate::IResult::Incomplete($crate::Needed::Size($consumed + i)),
      $crate::IResult::Done(i,o)     => {
        let $field = o;
        $crate::IResult::Done(i, ( $($rest)* ))
      },
    }
  );

  ($i:expr, $($rest:tt)*) => (
    {
      do_parse!(__impl $i, 0usize, $($rest)*)
    }
  );
);
...
// To create a parser for integer
named!(integer<&[u8], i64>, map!( 
  pair!( 
    opt!(sign), 
    map_res!(map_res!(digit, str::from_utf8), i64::from_str) 
  ), 
  |(sign, value): (Option<i64>, i64)| { sign.unwrap_or(1) * value } 
));

    优点：可以创建 DSL 语法，性能高。

    缺点：宏本身难以阅读、编写和调试。

    Crate nom 使用了这种方法。

根据以上比较，解析器作为 struct 是最佳方法。最初，我选择使用 nom 来创建一个 PDF 解析器，结果一个特殊的 PDF 功能阻碍了我。在解析 PDF 流对象时，其长度可能是一个引用对象，因此需要从读取器中获取长度。named! 宏不能接受额外的参数，在流对象解析器中没有明显的方法来读取长度对象。这是我开始开发 pom 的主要原因。

Pom 中预定义解析器和组合子的列表

基本解析器 描述
empty() 总是成功，不消耗任何输入。
end() 匹配输入结束。
sym(t) 匹配单个终结符t。
seq(s) 匹配符号序列。
list(p,s) 匹配 p 的列表，由 s 分隔。
one_of(set) 当前输入符号在集合中时成功。
none_of(set) 当前输入符号不在集合中时成功。
range(r) 当范围包含当前输入符号时成功。
is_a(predict) 当 predict 对当前输入符号返回 true 时成功。
not_a(predict) 当 predict 对当前输入符号返回 false 时成功。
take(n) 读取n个符号。
skip(n) 跳过n个符号。
call(pf) 调用解析器工厂，可用于创建递归解析器。

这些是创建基本解析器的函数。

解析器组合子 描述
p + q 匹配 p 和 q，如果两者都成功则返回结果对。
p - q 匹配 p 和 q，如果两者都成功则返回 p 的结果。
p * q 匹配 p 和 q，如果两者都成功则返回 q 的结果。
p >> q 解析 p 并获取结果 P，然后解析并返回 q(P) 的结果。
-p 当 p 成功时成功，不消耗输入。
!p 当 p 失败时成功，不消耗输入。
p.opt() 使解析器成为可选。
p.repeat(m..n) p.repeat(0..) 重复 p 零次或多次
p.repeat(1..) 重复 p 一次或多次
p.repeat(1..4) 匹配 p 至少 1 次，最多 4 次
p.map(f) 将解析器结果转换为期望的值。
p.collect() 收集所有匹配的输入符号。
p.discard() 丢弃解析器输出。

这些是基于其他解析器创建新解析器的操作。运算符的选择由它们的运算符优先级、元数和“含义”确定。

使用 `*` 在表达式开头忽略第一个操作数的结果，`+` 和 `-` 可以满足表达式其余部分的需求。
例如，A * B * C - D + E - F 将返回 C 和 E 的结果作为一个对。

Using the Code

有三种方法可以创建解析器：

  1. 作为变量，通常用于构建另一个解析器。

    let integer = one_of(b"+-").opt() + one_of(b"0123456789").repeat(1..);

  2. 作为闭包，当在构建另一个解析器时被引用多次。

    let integer = || one_of(b"+-").opt() + one_of(b"0123456789").repeat(1..);
let pair = sym(b'(') * integer() - sym(b',') + integer() - sym(b')');

  3. 作为函数，提供高级构造。

    fn integer() -> Parser<u8, (Option<u8>, Vec<u8>)> {
    one_of(b"+-").opt() + one_of(b"0123456789").repeat(1..)
}

JSON 解析器示例

我将通过创建一个 JSON 解析器来更详细地解释解析器组合子。语法图可以在 json.org 上找到。

extern crate pom;
use pom::{Parser, DataInput};
use pom::char_class::hex_digit;
use pom::parser::*;

use std::str::FromStr;
use std::char::{decode_utf16, REPLACEMENT_CHARACTER};
use std::collections::HashMap;

#[derive(Debug, PartialEq)]
pub enum JsonValue {
    Null,
    Bool(bool),
    Str(String),
    Num(f64),
    Array(Vec<JsonValue>),
    Object(HashMap<String,JsonValue>)
}

导入预定义的解析器组合子和实用函数，将 JSON 解析器的输出值定义为一个 enum。

fn space() -> Parser<u8, ()> {
    one_of(b" \t\r\n").repeat(0..).discard()
}

匹配零个或多个空格字符，输出被忽略。

fn number() -> Parser<u8, f64> {
    let integer = one_of(b"123456789") - one_of(b"0123456789").repeat(0..) | sym(b'0');
    let frac = sym(b'.') + one_of(b"0123456789").repeat(1..);
    let exp = one_of(b"eE") + one_of(b"+-").opt() + one_of(b"0123456789").repeat(1..);
    let number = sym(b'-').opt() + integer + frac.opt() + exp.opt();
    number.collect().map(|v|String::from_utf8(v).unwrap()).map
                        (|s|f64::from_str(&s).unwrap())
}

忽略整数、分数或指数的每个输出，collect() 方法将所有匹配的字符作为 Vec<u8> 获取，然后将其转换为 string，再转换为 float 数字。

fn string() -> Parser<u8, String> {
    let special_char = sym(b'\\') | sym(b'/') | sym(b'"')
        | sym(b'b').map(|_|b'\x08') | sym(b'f').map(|_|b'\x0C')
        | sym(b'n').map(|_|b'\n') | sym(b'r').map(|_|b'\r') | sym(b't').map(|_|b'\t');
    let escape_sequence = sym(b'\\') * special_char;
    let char_string = (none_of(b"\\\"") | 
    escape_sequence).repeat(1..).map(|bytes|String::from_utf8(bytes).unwrap());
    let utf16_char = sym(b'\\') * sym(b'u') * 
    is_a(hex_digit).repeat(4..5).map(|digits|
    u16::from_str_radix(&String::from_utf8(digits).unwrap(), 16).unwrap());
    let utf16_string = utf16_char.repeat(1..).map
    (|chars|decode_utf16(chars).map(|r| r.unwrap_or
    (REPLACEMENT_CHARACTER)).collect::<String>());
    let string = sym(b'"') * (char_string | utf16_string).repeat(0..) - sym(b'"');
    string.map(|strings|strings.concat())
}

大部分代码用于解析转义序列。根据 Wikipedia，UTF-16 代理对是某些 JSON 解析器遗漏的细节。我们利用 Rust 的 Unicode 支持轻松实现了这一点。

fn array() -> Parser<u8, Vec<JsonValue>> {
    let elems = list(call(value), sym(b',') * space());
    let arr = sym(b'[') * space() * elems.opt() - sym(b']');
    arr.map(|elems|elems.unwrap_or(vec![]))
}

fn object() -> Parser<u8, HashMap<String, JsonValue>> {
    let member = string() - space() - sym(b':') - space() + call(value);
    let members = list(member, sym(b',') * space());
    let obj = sym(b'{') * space() * members.opt() - sym(b'}');
    obj.map(|members|members.unwrap_or(vec![]).into_iter().collect::<HashMap<_,_>>())
}

fn value() -> Parser<u8, JsonValue> {
    ( seq(b"null").map(|_|JsonValue::Null)
    | seq(b"true").map(|_|JsonValue::Bool(true))
    | seq(b"false").map(|_|JsonValue::Bool(false))
    | number().map(|num|JsonValue::Num(num))
    | string().map(|text|JsonValue::Str(text))
    | array().map(|arr|JsonValue::Array(arr))
    | object().map(|obj|JsonValue::Object(obj))
    ) - space()
}

array 和 object 解析起来非常直接，注意 call(value)，一开始我将其写为 value()，然后就创建了一个无限循环。递归解析通过向 pom 添加 call() 来解决。

pub fn json() -> Parser<u8, JsonValue> {
    space() * value() - end()
}

最终的 JSON 解析器，声明为 public。根据 RFC 7159，JSON 文本是六种类型中任何一种的序列化值。end() 用于确保输入中没有额外的文本。

fn main() {
    let test = br#"
    {
        "Image": {
            "Width":  800,
            "Height": 600,
            "Title":  "View from 15th Floor",
            "Thumbnail": {
                "Url":    "http://www.example.com/image/481989943",
                "Height": 125,
                "Width":  100
            },
            "Animated" : false,
            "IDs": [116, 943, 234, 38793]
        },
        "escaped characters": "\u2192\uD83D\uDE00\"\t\uD834\uDD1E"
    }"#;

    let mut input = DataInput::new(test);
    println!("{:?}", json().parse(&mut input));
}

使用 JSON 解析器解析 JSON 文本，输出是

cargo run --example json
   Compiling pom v0.6.0 (file:///work/pom)
    Finished debug [unoptimized + debuginfo] target(s) in 2.20 secs
     Running `target/debug/examples/json`
Ok(Object({"Image": Object({"Width": Num(800), 
"Title": Str("View from 15th Floor"), "Height": Num(600), 
"Animated": Bool(false), "IDs": Array([Num(116), Num(943), 
Num(234), Num(38793)]), "Thumbnail": Object({"Height
": Num(125), "Url": Str("http://www.example.com/image/481989943"), 
"Width": Num(100)})}), "escaped characters": Str("→😀\"\t𝄞")}))

上面的解析器假设输入字节是 UTF-8 编码的文本；否则，您可以使用 JSON 解析器的字符版本。

JSON 示例中没有涵盖 p >> q。它用于将 p 的输出传递给 p 的解析器创建。

let mut input = DataInput::new(b"5oooooooo");
let parser = one_of(b"0123456789").map(|c|c - b'0') >> |n| {
    take(n as usize) + sym(b'o').repeat(0..)
};
let output = parser.parse(&mut input);
assert_eq!(output, Ok( (vec![b'o';5], vec![b'o';3]) ));

第一个字符指示要解析的 o 的数量，然后该数字用于闭包 |n| take(n)。

更多示例

结论

我认为我创造了一些非常酷的东西，您可以使用 pom 优雅地编写各种解析器。我帮助 pom 版本逐版本发展至今，pom 也极大地帮助我提升了 Rust 编程技能。当然，仍有改进的空间，欢迎任何反馈。

关注点

我尝试给 Parser 添加一个 cache() 方法。在给定的输入位置上记忆结果，再次调用时直接返回结果，从而有效地实现 Packrat 解析算法。但有两个问题：

  1. 保存结果意味着修改一个 Hashmap，所以 Parser 的方法字段应该是 Box 的 FnMut，
  2. Hashmap 返回给定键的值的引用，值不能被移动，所以需要使值可克隆。

历史

  • 2017 年 1 月 17 日：初始版本
© . All rights reserved.