左递归解析表达式语法（PEG）

lrpeg 允许左递归规则，并使用 ratpack 解析以提高速度。我写了一篇 博客文章 来介绍 lrpeg 的概念。

现有的 rust PEG 解析生成器不允许左递归，这使得编写语法变得非常尴尬。可以编写一个允许左递归的 PEG 解析生成器，就像 左递归 一样，正如 python 现在使用的。

请参阅 IRP 语法 以获取完整的 lrpeg 语法和 IRP 的处理。

如何使用 lrpeg

将 lrpeg 添加到您的 Cargo.toml 中的构建依赖项

[build-dependencies]
lrpeg = "0"

[dependencies]
regex = "1"
unicode-xid = "0.2"

现在将一个 build.rs 添加到您的项目根目录，其中包含

use std::env;
use std::path::PathBuf;

fn main() {
    let out_dir = env::var("OUT_DIR").unwrap();
    lrpeg::process_files(&PathBuf::from("src"), &PathBuf::from(out_dir));
}

编写您的 peg 语法，并将其放入以 .peg 结尾的文件中，例如 src/calculator.peg

calculator <- expr EOI;

expr <- expr ("+" / "-") WHITESPACE term
    / term;

term <- term ("*" / "/" / "%") WHITESPACE  factor
    / factor;

factor <- "(" WHITESPACE  expr ")" WHITESPACE
    / num;

num <- re#[0-9]+# WHITESPACE;

当您运行 cargo build 时，calculator.rs 将生成到您的 target/... 目录。您需要将此模块包含到您的项目中，然后您可以像这样实例化 PEG

include!(concat!(env!("OUT_DIR"), "/calculator.rs"));

use calculator::{Node, Rule};

fn main() {
    let mut parser = calculator::PEG::new();

    let args: Vec<String> = std::env::args().collect();

    if args.len() != 2 {
        eprintln!("Usage {} EXPRESSION", &args[0]);
        std::process::exit(2);
    }

    let input = &args[1];

    println!("parsing: {}", input);

    match parser.parse(input) {
        Ok(node) => {
            fn walk(node: &Node, input: &str) -> u64 {
                match node.rule {
                    Rule::num => u64::from_str_radix(node.children[0].as_str(input), 10).unwrap(),
                    Rule::expr => {
                        if node.alternative == Some(0) {
                            let left = walk(&node.children[0], input);
                            let right = walk(&node.children[3], input);

                            match node.children[1].as_str(input) {
                                "+" => left + right,
                                "-" => left - right,
                                _ => unreachable!(),
                            }
                        } else {
                            walk(&node.children[0], input)
                        }
                    }
                    Rule::term => {
                        if node.alternative == Some(0) {
                            let left = walk(&node.children[0], input);
                            let right = walk(&node.children[3], input);

                            match node.children[1].as_str(input) {
                                "*" => left * right,
                                "/" => left / right,
                                "%" => left % right,
                                _ => unreachable!(),
                            }
                        } else {
                            walk(&node.children[0], input)
                        }
                    }
                    Rule::factor => {
                        if node.alternative == Some(0) {
                            walk(&node.children[2], input)
                        } else {
                            walk(&node.children[0], input)
                        }
                    }
                    Rule::calculator => walk(&node.children[0], input),
                    _ => {
                        unreachable!()
                    }
                }
            }

            println!("result: {}", walk(&node, input));
        }
        Err((line_no, col_no)) => {
            eprintln!("parser error at {}:{}", line_no, col_no);
        }
    }
}

此示例可在 lrpeg-example 中找到。

如何编写语法

PEG 语法是一组规则。在 lrpeg 中，每个规则都必须以分号 (;) 结尾。解析从顶部规则开始。

• 每个规则必须以标识符开头，后跟 <- 和术语，并以分号 (;) 结尾
• 术语可以用 *、+ 或可选的 ? 重复。
• 术语列表不能为空（但术语可以是可选的）
• 文本字面量可以用单引号或双引号编码 ("foo" 或 'bar')
• 正则表达式必须写成 re#[0-9]+#。
• 替代项用 / 表示。例如 foo <- "a" / "b";
• 存在特殊的术语 WHITESPACE、EOI 和 XID_IDENTIFIER（用于 Unicode 标识符）