1 个不稳定版本

0.4.0 2023年7月27日

#2592解析器实现

MIT 许可证

240KB
2.5K SLoC

Panfix 解析

Panfix 解析是一种基于(但比操作符优先文法更具有表达性)的新解析方法。

它不是基于上下文无关文法(CFGs),也不是基于解析表达式文法(PEGs)。它拥有一种不同的文法风格,大致上是一系列多固定运算符。构成有效文法的规则极其简单(与LR或LALR解析相比)。

Panfix 解析始终在 线性时间 内运行,不依赖于语法的规模。也就是说,如果 N 是要解析的文本大小,而 G 是语法的规模,那么Panfix解析器的运行时间是在 O(N)(而不是像Packrat PEG解析那样的 O(NG))。

它提供了非常 宽松 的解析器,它们会在存在各种错误的情况下愉快地生成解析树。一方面,这增加了处理解析树时需要处理的案例数量。另一方面,这些额外的情况是错误情况,这将是为它们生成自定义错误消息的好时机。

示例:JSON

最好的介绍可能是通过一个工作示例。让我们看看使用Panfix解析解析JSON需要什么。这是一个JSON的Panfix语法

use panfix::{Parser, Grammar, GrammarError};

fn make_json_parser() -> Result<Parser, GrammarError> {
    let mut grammar = Grammar::new("[ \n\r\t]+")?;
    grammar.regex("String", r#""([^\\"]|(\\.))*""#)?;
    grammar.regex("Number", r#"-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?"#)?;
    grammar.regex("Invalid", r#"[a-zA-Z_][a-zA-Z0-9_]*"#)?; // for catching missing qutoes
    grammar.string("Null", "null")?;
    grammar.string("True", "true")?;
    grammar.string("False", "false")?;
    grammar.op("Array", pattern!("[" "]"))?;
    grammar.op("Object", pattern!("{" "}"))?;
    grammar.right_assoc();
    grammar.op("Keyval", pattern!(_ ":" _))?;
    grammar.right_assoc();
    grammar.op("Comma", pattern!(_ "," _))?;
    grammar.finish()
}

regexstring 行定义了如何解析像字符串和布尔值这样的常量。 regex 表示“匹配这个正则表达式模式”,string 表示“匹配这个精确字符串”。Array 行表示[开始一个数组并]结束它。类似的,“Object”行。

接下来是

    grammar.right_assoc();
    grammar.op("Keyval", pattern!(_ ":" _))?;
    grammar.right_assoc();
    grammar.op("Comma", pattern!(_ "," _))?;

两个 right\_assoc 调用开始了两个 优先级组,每个组有一个运算符。优先级组有两个效果。

首先,在先前定义的组中定义的运算符比在后来定义的组中定义的运算符绑定更紧密。例如,您会将在优先级较低的组中定义 &&,而不是在优先级较高的组中定义 >,这样 x < y && y < z 就会被解析为 (x < y) && (y < z),而不是 x < (y && y) < z

其次,每个优先级组声明其运算符是左结合还是右结合。例如,字段访问 _._ 应声明为右结合,以便 person.birthday.month 被解析为 (person.birthday).month,而不是 person.(birthday.month)。在 JSON 示例中,我们声明 :, 为右结合,但在这种情况下,左结合同样适用。

pattern!(_ "," _) 声明 , 是一个接受左右参数的操作符,分别由开始和结束处的下划线表示。相比之下,pattern!("[" "]") 缺少下划线,因此表示 JSON 数组不接受左右参数。另一方面,在标记之间总是允许 存在 参数:例如在 [] 之间。

注意这个语法没有说明的一些事情。它没有说 : 只允许在对象 {...} 内部使用,也没有说对象键必须是字符串。正前缀解析在这方面相当不寻常。您不是定义想要的精确语法,而是定义一个语法的 超集,然后在处理解析树时构建上下文特定的错误消息。

解析一些(格式不佳的)JSON

让我们看看当我们这样解析格式不佳的 "JSON" 时会发生什么:

{
    "id": 999,
    "object_class:" "safe",
    "weight_kg": 54.5
    "disposition": "friendly",
    "diet": [
        "M&Ms",
        "Necco wafers",
        "other sweets",
    ],
    "interactions": {
        "target_id": 682,
        "effect": mixed,
    }
}

如下:

let parser = make\_json\_parser().unwrap();
let input = ...read that JSON file...;
let source = Source::new("bad\_json", input);
match parser.parse(&source) { ... }

parse 的调用实际上会返回 Ok 而不是 Err!这是因为正前缀解析故意非常宽松。它唯一关心的是运算符是否完整,在这个例子中,[ 总是与 ] 匹配,而 { 总是与 } 匹配。因此,parse 返回 Ok(tree)。当你 Display 这个树时,你会得到:

(Object
  (Comma (Keyval "id" 999)
    (Comma (_ "object_class:" "safe")
      (Comma
        (Keyval "weight_kg"
          (Keyval (_ 54.5 "disposition") "friendly"))
        (Comma
          (Keyval "diet"
            (Array
              (Comma "M&Ms"
                (Comma "Necco wafers"
                  (Comma "other sweets" _)))))
          (Keyval "interactions"
            (Object
              (Comma (Keyval "target_id" 682)
                (Comma (Keyval "effect" mixed) _)))))))))

解析宽松性的机制在于隐式插入两种类型的节点,显示为上面所示的 _

空节点

节点是在缺少参数的地方插入的。例如,考虑JSON的“饮食”部分

"diet": [
    "M&Ms",
    "Necco wafers",
    "other sweets",
],

, 定义为接受两个参数,但缺少了 之后 的参数 "other sweets",。因此,在解析树中插入一个空节点,记作 _

(Array
  (Comma "M&Ms"
    (Comma "Necco wafers"
      (Comma "other sweets" _)))))

在JSON中这是一个错误,尽管在一些允许尾随逗号的编程语言中不会是错误。

并列节点

并列节点是空节点的补充:它们是在一行中有两个表达式但没有任何连接它们的地方插入的。例如,这个JSON片段

"weight_kg": 54.5
"disposition": "friendly",

变成了解析树中的这个片段

(Keyval "weight_kg"
  (Keyval (_ 54.5 "disposition") "friendly"))

其中 _ 是一个并列节点,表示 54.5"disposition" 是并列的(即相邻的)。

就像空节点不总是错误一样,并列节点的情况可能也是预期的。例如,即使在JSON中,空列表 [] 也会解析为 (Array _)

空节点和并列节点的组合使得前缀解析非常宽松。这在某种程度上是有益的,我们将在下面看到。

解析树 -> JSON

现在怎么办?生成解析树(附带源位置)的艰苦工作已经完成。剩下的是 简单但冗长 的工作,即遍历该树并将其转换为 Json 类型。

    #[derive(Debug)]
    enum Json {
        String(String),
        Number(f64),
        Boolean(bool),
        Null,
        Array(Vec<Json>),
        Object(HashMap<String, Json>),
    }

您可以在 examples/json.rs 中找到此转换。它是冗长的但简单的。以下是从其中摘录的一段:

fn parse_list(&mut self, mut visitor: Visitor<'s, '_, '_>, elems: &mut Vec<Json>) {
    while visitor.name() == "Comma" {
        let [head, tail] = visitor.children();
        let head = self.parse_value(head);
        elems.push(head);
        visitor = tail;
    }
    if visitor.name() == "Blank" {
        self.error(visitor, "JSON does not allow trailing commas.");
    } else {
        elems.push(self.parse_value(visitor));
    }
}

这可能感觉像是忙碌的工作,但并非如此。好的错误信息极其依赖于上下文;panfix 没有足够的知识来独立生成高质量的错误信息。注意,例如,上面的信息:“JSON不允许尾随逗号”。这只能手动编写。

visitor 是树中节点的引用。您可以通过调用 .children() 来获取其子节点,并通过 .error(message) 在该源位置构建错误信息。

panfix 解析如此宽松的事实得到了体现:我们的JSON示例为我们查看的无效JSON产生了一整套有用的错误信息。

Parse Error: Expected a key:value pair.
At 'stdin' line 2.

    "object_class:" "safe",
    ^^^^^^^^^^^^^^^^^^^^^^

Parse Error: Expected a JSON value here, not a key:value pair.
At 'stdin' lines 3-4.
    "weight_kg": 54.5
                 ^^^^
    "disposition": "friendly",
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Parse Error: JSON does not allow trailing commas.
At 'stdin' line 8.

        "other sweets",
                       ^

Parse Error: Missing quotes.
At 'stdin' line 12.

        "effect": mixed,
                  ^^^^^

Parse Error: JSON does not allow trailing commas.
At 'stdin' line 12.

        "effect": mixed,
                        ^

有关JSON解析的完整示例,请参阅 examples/json.rs。另一个示例,请参阅 examples/calc.rs

规范

现在您已经了解了整个情况,让我们转到关注细节、要求和保证。

前缀语法

一个前缀 Grammar 由一个空白正则表达式和一组 运算符 组成。从数字到标识符,再到二元运算符和函数定义,一切都是运算符。每个运算符都具有以下属性

  • 名称 给运算符一个名称,这样您就可以在解析树中稍后识别它。
  • 标记 用于表示操作符匹配的标记序列。例如:标识符可能匹配正则表达式标记 [a-zA-Z_]+;用于分组的括号会匹配标记序列 "()";函数定义可能匹配 "function","(",")","{}"。
  • 优先级 表示其绑定紧密程度。例如,字段访问 _._ 的绑定应该比数组索引 _[_] 更紧密,因此 catalog.entries[0] 解析为 (catalog.entries)[0],而不是 catalog.(entries[0])
  • 结合性 表示其如何与自身结合。例如,减号应该是 左结合,所以 1 - 2 - 3 等于 ((1 - 2) - 3) = -1 - 3 = -4,而不是 右结合,在这种情况下它等于 (1 - (2 - 3)) = 1 - -1 = 0
  • 固定性 表示它是否接受左参数以及是否接受右参数。例如:字段访问 _._ 既要左参数也要右参数;数组索引 _[_] 只接受左参数,不接受右参数(因为 第一个标记之前有一个参数最后一个标记之后没有参数);例如一个数字如 2.5 既不接受左参数也不接受右参数。

您可以使用 grammar.add_raw_op(name, prec, assoc, fixity, tokens) 手动指定这些属性,但还有一个更高层次的接口来简化这个过程。

  • grammar.grammar(name: &str, regex_pattern: &str) 定义了一个具有单个标记且没有参数的操作符。由于它没有参数,优先级和结合性无关紧要。可以用于例如标识符、数字和字符串字面量。
  • grammar.string(name: &str, string_pattern: &str) 与此相同,但它匹配的是字符串字面量模式而不是正则表达式模式。
  • grammar.left_assoc()grammar.right_assoc() 引入了一个新的 操作符组。在这些之后定义的操作符属于该操作符组。操作符组中的操作符都具有相同的结合性,并且都具有与其他操作符相同的优先级。较早组中定义的操作符的优先级比较晚组中定义的操作符的优先级更高。(如果没有调用这些方法之一,则默认为左结合性。)
  • grammar.op(name: &str, pattern: Pattern) 定义了一个操作符。它继承了其组的优先级和结合性,而 pattern 指定了它的 固定性标记。在 pattern! 宏中,通过在左侧或右侧参数前放置前导或尾随下划线来声明固定性,并在中间用引号放置标记。例如,pattern!(_ "[" "]") 有两个标记,并且它的固定性是有左参数但没有右参数。

语法必须遵守三个简单规则

  1. 其正则表达式必须是良好形成的。
  2. 最多只能有两个操作符以相同的标记开始:一个有左参数,一个没有。 (例如,这允许同时有前缀和后缀减号操作符:它们都以标记“-”开始,但二进制减号有左参数,而一元减号没有。)
  3. 具有相同优先级的操作符必须具有相同的结合性。(此规则由构建器模式强制执行,因此您只需要在使用 add_raw_op 时考虑。)

这三个规则都由 Grammar 类型强制执行;如果您在调用 Grammar.finish() 时违反了它们,您将收到错误。

词法分析

当源代码进行词法分析时,语法中的多个正则表达式可能匹配。用于确定使用哪个正则表达式的规则是

  • 匹配更长的一个获胜,
  • 如果失败,则字符串模式胜过正则表达式模式,
  • 如果失败,则语法中较早定义的模式胜出。

解析

给定一个前缀语法和源文件,您可以在 线性时间 内解析源代码,生成解析错误或解析树。

存在三种解析错误

  • 词法错误。例如,在JSON中遇到字符 %
  • 意外的标记。例如,在没有任何 ( 的情况下遇到 )
  • 运算符开始但没有完成。例如,遇到一个 ( 但没有跟随的 )

这些都是唯一的错误。如果没有乱码标记,并且括号等匹配,解析将成功!

如果解析成功,它将生成一个 解析树。树中的每个节点都有一个运算符和源位置。树中的运算符包括语法中定义的运算符,以及两个额外的运算符

  • "Blank" 运算符表示缺少参数。例如,在源代码 true || 中,一个 "Blank" 运算符将被插入到 || 的右边。
  • "Juxtapose" 运算符表示两个表达式相邻。例如,在源代码 2 3 中,一个 "Jutxapose" 运算符将被插入到 23 之间。

解析树保证是良好形成的,即

  1. 每个节点按以下顺序有子节点:(i)如果它有一个左参数,则为其左参数一个子节点;(ii)为其标记之间的每个空格一个子节点;(iii)如果有的话,为其右参数一个子节点。空白节点没有子节点,Juxtapose 节点有两个子节点。(例如,数组索引 _[_] 有两个子节点:1 个为其左参数,1 个为其第一个和第二个标记之间的空格。)
  2. 如果一个节点有左参数,那么它要么比第一个子节点优先级低,要么它是左结合的,并且与第一个子节点具有相同的优先级。同样,如果它有右参数,那么它要么比最后一个子节点优先级低,要么它是右结合的,并且具有相同的优先级。
  3. 空白和Juxtapose并不多。例如,1 + 2 将被解析为 (+ 1 2),而不是 (Juxtapose (+ 1 Blank) 2)

将这些放在一起

  1. 从文件、stdin 或其他内容构建一个 Source
  2. 使用构建器模式构建一个 Grammar,或者如果需要更多控制,使用 add_raw_op。调用 Grammar.finish() 获取一个 Parser。这将检查语法是否有效,如果不是则返回 Error
  3. 使用 Parser.parse(Source) 进行解析。如果出现任何错误,则放弃并显示它们。
  4. 如果解析成功,将 ParseTree 转换为 AST(或您内部表示的任何形式)。这是检查错误的时候。基本上:遍历树,检查每个节点的 name():如果是预期的,则递归,如果不是预期的,则生成自定义错误消息。

再次,要查看完整示例,请参阅 examples/json.rsexamples/calc.rs

依赖项

~2.4–4MB
~71K SLoC