ANTLR(全名:ANother Tool for Language Recognition)是基于LL(*)算法实现的语法解析器生成器

# 从一个 json 解析器开始

  • 熟悉对比 Rust 的 nom 库和 pest 库
  • 熟悉 Antlr 使用
  • 熟悉 Antlr 生成其他语言的解析器过程

# 基于 Rust pest 的 json 解析器

在代码中使用先安装依赖

cargo install cargo-edit  # 为 cargo 添加 add 子命令
cargo add pest
cargo add pest_derive

pest 需要单独的文件描述文法,可以在 IDEA 中安装 pest 插件来方便 pest 后缀文件的语法高亮

我们创建一个 json.pest,内容如下

WHITESPACE = _{ " " | "\r"? ~ "\n" }
digit = @{ '0'..'9' }
non_zero_digit = @{ '1'..'9' }
hex_digit = @{ '0'..'9' | 'a'..'f' | 'A'..'F' }
e = @{ "e" | "e+" | "e-" | "E" | "E+" | "E-" }
exp = @{ e ~ digit+ }
int = @{ "-"? ~ (digit | non_zero_digit ~ digit+) }
number = @{ int ~ digit+? ~ exp? }
char = @{ !("\\" | "\"") ~ ANY | "\\\"" | "\\\\" | "\\/" | "\\b" | "\\f" | "\\n" | "\\r" | "\\t" | "\\u" ~ hex_digit{4} }
string = @{ "\"" ~ char* ~ "\"" }
object = { "{" ~ "}" | "{" ~ members ~ "}" }
members = { pair ~ ("," ~ members)* }
pair = { string ~ ":" ~ value }
array = { "[" ~ "]" | "[" ~ elements ~ "]" }
elements = { value ~ ("," ~ elements)* }
boolean = { "true" | "false" }
null = { "null" }
value = { string | number | object | array | boolean | null }

在程序中解析对应的 value 类型,可以看到能识别为 Array

extern crate pest;
#[macro_use]
extern crate pest_derive;

use pest::Parser;

#[derive(Parser)]
#[grammar = "json.pest"]
struct JsonParser;


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_pest() {
        let pairs = JsonParser::parse(Rule::value, "[1, {}, null, true, \"a\"]").unwrap_or_else(|e| panic!("{}", e));
        // Because ident_list is silent, the iterator will contain idents
        for pair in pairs {
            // A pair is a combination of the rule which matched and a span of input
            println!("Rule:    {:?}", pair.as_rule());
            println!("Span:    {:?}", pair.as_span());
            println!("Text:    {}", pair.as_str());

            // A pair can be converted to an iterator of the tokens which make it up:
            for inner_pair in pair.into_inner() {
                match inner_pair.as_rule() {
                    Rule::string => println!("String:  {}", inner_pair.as_str()),
                    Rule::number => println!("Number:   {}", inner_pair.as_str()),
                    Rule::object => println!("Object:   {}", inner_pair.as_str()),
                    Rule::array => println!("Array:   {}", inner_pair.as_str()),
                    Rule::boolean => println!("Boolean:   {}", inner_pair.as_str()),
                    Rule::null => println!("Null:   {}", inner_pair.as_str()),
                    _ => unreachable!()
                };
            }
        }
    }
}

运行cargo test pest -- --nocapture输出

Rule:    value
Span:    Span { str: "[1, {}, null, true, \"a\"]", start: 0, end: 24 }
Text:    [1, {}, null, true, "a"]
Array:   [1, {}, null, true, "a"]

官网上有 playground,我的 Json 解析器

官方教程里也有 Json 解析器的写法

# 基于 Rust nom 的 json 解析器

使用作者为了反击 pest 的错误数据而进行评测的实现

但是需要根据新版本的 api 文档进行一些改造(新版本设计中用函数替代了宏

改造包括更改函数的引用模块和添加 null 的识别

#[macro_use]
extern crate nom;

use std::str;
use std::collections::HashMap;
use nom::{number::streaming::recognize_float, character::streaming::multispace0 as sp};

fn is_string_character(c: u8) -> bool {
    //FIXME: should validate unicode character
    c != b'"' && c != b'\\'
}

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

named!(float<f64>, flat_map!(recognize_float, parse_to!(f64)));

named!(
    string<&str>,
    delimited!(
        char!('\"'),
        map_res!(
            escaped!(take_while1!(is_string_character), '\\', one_of!("\"bfnrt\\")),
            str::from_utf8
        ),
        char!('\"')
    )
);

named!(
  boolean<bool>,
  alt!(value!(false, tag!("false")) | value!(true, tag!("true")))
);

named!(
  null,
  tag!("null")
);

named!(
  array<Vec<JsonValue>>,
  preceded!(sp, delimited!(
    char!('['),
    separated_list!(char!(','), value),
    preceded!(sp, char!(']'))
  ))
);

named!(
  key_value<(&str, JsonValue)>,
  preceded!(sp, separated_pair!(string, char!(':'), value))
);

named!(
  hash<HashMap<String, JsonValue>>,
  preceded!(sp, map!(
    delimited!(
      char!('{'),
      separated_list!(char!(','), key_value),
      preceded!(sp, char!('}'))
    ),
    |tuple_vec| tuple_vec
      .into_iter()
      .map(|(k, v)| (String::from(k), v))
      .collect()
  ))
);

named!(
  value<JsonValue>,
  preceded!(sp, alt!(
    hash    => { |h| JsonValue::Object(h)            } |
    array   => { |v| JsonValue::Array(v)             } |
    string  => { |s| JsonValue::Str(String::from(s)) } |
    float   => { |f| JsonValue::Num(f)               } |
    boolean => { |b| JsonValue::Boolean(b)           } |
    null    => { |_| JsonValue::Null                 }
  ))
);

named!(
  pub root<JsonValue>,
  delimited!(
    call!(sp),
    alt!(
      map!(hash, JsonValue::Object) |
      map!(array, JsonValue::Array)
    ),
    not!(complete!(sp))
  )
);

#[cfg(test)]
mod tests {
  use super::*;
  #[test]
  fn test_nom() {
    println!("data:\n{:?}", root("[1, {}, null, true, \"a\"]".as_bytes()));
  }
}

运行cargo test nom -- --nocapture输出

data:
Ok(([], Array([Num(1.0), Object({}), Null, Boolean(true), Str("a")])))

整体用下来感觉 nom 的灵活性更强,pest 的可读性、可调式性更强

两个模块代码见项目

# 基于 Antlr 的 json 解析器

# 基于 Antlr 生成的 golang json 解析器

# ALL(*)

ANTLR v4的语法分析器使用一种新的称为Adaptive LL()或ALL()的语法分析技术,它可以在生成的语法分析器执行前在运行时动态地而不是静态地执行语法分析。

ANTLR v4极大地简化了匹配算术表达式语法结构的文法规则。对于传统的自顶向下的语法分析器生成器来说,识别表达式的最自然的文法是无效的,ANTLR v4则不然,它会自动地将左递归规则重写为非左递归等价物,唯一的约束是左递归必须是直接的,即规则立刻引用它自身。

参考文章