CIDR25——Runtime-Extensible Parsers阅读

最早是在DuckDB的Blog中发现的这篇文章，作者是Hannes Mühleisen和Mark Raasveldt，是DuckDB的员工。

Runtime-Extensible SQL Parsers Using PEG

顺带发现了几个月前构建的DuckDB RSSHub订阅失效了，可能这周末修复

（实际修复于2024.12.11：fix(route/duckdb): change blogs link and author ）

该论文目前已被CIDR2025接收：下载地址

文章还提到了相关实现库：

https://github.com/yhirose/cpp-peglib

https://github.com/hannes/peg-parser-experiments

甚至有一个JIT的版本用于PL/0的示范😆

https://github.com/yhirose/pl0-jit-compiler

正文内容

image-20241209164636639

目前大部分的数据库解析都沿用了YACC的Style，使用BCNF，LALR的解析样式

（但我记得LLVM不是这么做的，这点还需要确认🤔)

image-20241209172545287

the most advanced SQL systems of 2024 use parser technology from the 1960s.

的确如此，长期以来人们不觉得从上世纪70年代沿用至今的SQL解析器有什么问题

in their traditional design, parser construction is a compile-time activity where enormous grammar files are translated into state machine transition lookup tables which are then baked in a system binary. Having those always be present in the parser might be wasteful especially for size-conscious binary distributions like WebAssembly (Wasm).

在传统的方案中，每增加新的语法，都会转成状态机查找表，嵌入到系统解析器的二进制文件中。这不利于编译器扩展

While this is also true in other ecosystems like Python, the design of SQL with its heavy focus on syntax and not function calls makes the extensions second-class citizens that have to somehow work around the restrictions by the original parser, e.g., by embedding custom expressions in strings.

但 SQL 的设计非常注重语法而非函数调用，这使得扩展必须以某种方式绕过原始解析器的限制，例如在字符串中嵌入自定义表达式，从而成为二等公民

(Note: 之前我在YeSQL的文章中看到过这种说法，相比较于YeSQL通过添加C扩展的方案，我认为这里从解析器入手是个不错的选项)

Parsing Expression Grammar

Parser Expression Grammars (PEG)，一种Top-Down的解析，Recursive-Decent，在Python的PEP617中成为Python的解析

Another big advantage of PEG parsers is error handling: [11] describes a practical technique where parser rules are annotated with “recovery” actions, which can 1) show more than a single error and 2) annotate errors with a more meaningful error message.

PEG输出的错误信息也会更加友善些

Lexical analysis is typically part of the PEG parser itself, which removes the need for a separate step.

词法与语法解析一体？😮Interesting

One big advantage is that PEG parsers do not require a compilation step where the grammar is converted to for example a finite state automaton based on lookup tables.

不需要编译？😮Interesting

A possible disadvantage of memoized packrat parsing is the memory required for memoization: the amount required is proportional to the input size, not the stack size.

一个可能缺点是 memoization 所需的内存：所需内存与输入大小成正比，而不是与堆栈大小成正比🤔

（意思是内存消耗有点大？）

allow syntax extensions, new statements, or to add entirely new query languages.

允许语法扩展？听起来不错

总有人想着把图运算加入SQL，也出现了Cypher这种专门处理图处理的语言，但其也可以通过PEG扩展得到

One of the most-reported support issues with data management systems are unhelpful syntax errors.

点名批评了MySQL的错误报错提示🤣

Given the token list and the grammar, there are now two main ways to decide whether the input matches the grammar: Top-down and Bottom-up

我记得火山模型就是Top-down，这是向量化处理的前置条件，而YACC’s LALR是典型的Bottom-Up

Postgres’ parser for example makes heavy use of reduce actions to create the abstract syntax tree for the query (PGNode).

PGNode是PG Syntax Tree的体现，对我而言有点意外，但想想确实是这么回事

Because the parser does not need to generate a state machine, we are immediately able to accept the new syntax.

等等，连状态机也不用了？

For the actual parsing, YACC parses TPC-H Query 1 in ca. 0.03 ms, where cpp-peglib takes ca. 0.3 ms, a ca. 10 times increas

比YACC慢10倍？啊这，但Blog中也指出了这是可以改进的，而cpp-peglib的作者也将其列为了Issue

For example, parser extension load order should ideally not influence the final grammar.

居然没有个BenchMark图？😅要是有的话就完美了

文章在最后提到，会逐步把DuckDB的Postgres YACC转为PEG

总结

PEG易于扩展SQL语法(不需要提前预编译)，而且许动态更改可接受的查询语法并提供更好的错误恢复

扩展资料

Shift-Reduce冲突

Shift-reduce 冲突是编译原理中解析上下文无关文法（Context-Free Grammar, CFG）时可能遇到的一种冲突，尤其是在使用LALR(1)或LR(1)等自底向上解析方法的时候。这种冲突出现在解析器无法决定在给定的输入符号上执行“移入”（shift）动作还是“归约”（reduce）动作。

Shift 动作

  • 当解析器选择“移入”时，它会将当前输入符号从输入流中读取并推入到解析栈中，然后继续解析下一个输入符号。

Reduce 动作

  • “归约”意味着解析器已经识别出一个句柄（即文法规则右侧的一系列符号），并且会用该文法规则左侧的非终结符替换这个句柄。这相当于按照某个产生式规则进行反向替换。

Shift-reduce 冲突的例子

考虑如下简单的算术表达式文法：

E -> E + T
E -> T
T -> num

假设解析栈中有 num +，而下一个输入符号也是 num。此时，解析器面临两种选择：

  1. Shift：将 num 移入栈中，期望之后能匹配规则 E -> E + T。
  2. Reduce：立即使用规则 T -> num 对栈顶的 num 进行归约。

由于存在这两种合法的选择，解析器遇到了 shift-reduce 冲突。

解决冲突

对于 LR 解析器来说，默认情况下通常会选择“移入”操作以期后续能够完成正确的归约。然而，实际应用中的解决策略可能会根据具体的语言和解析器设计有所不同。例如，在 Yacc 或 Bison 这样的工具中，可以通过优先级和结合性规则来明确指定如何处理这些冲突。

在某些情况下，重新设计文法可以消除 shift-reduce 冲突，使得解析过程更加清晰且无歧义。

PEG

中文维基百科：https://zh.wikipedia.org/zh-cn/%E8%A7%A3%E6%9E%90%E8%A1%A8%E8%BE%BE%E6%96%87%E6%B3%95

使用指南：https://berthub.eu/articles/posts/practical-peg-parsing/

cpp-peglib

cpp-peglib的作者提供了一个在线的Playground，我想应该是转成WASM了

下面是一个解析Vector的样例

image-20241212110436520

而项目本身应该用了Gtest，CMake，我在Debian-Sid的测试环境中使用GCC-14运行没有任何问题，比预想的要顺利很多😘

下面贴一个最简单的加法

#include <assert.h>
#include <iostream>
#include <peglib.h>

using namespace peg;
using namespace std;

int main(void) {
  // (2) Make a parser
  parser parser(R"(
        # Grammar for Calculator...
        Additive    <- Multiplicative '+' Additive / Multiplicative
        Multiplicative   <- Primary '*' Multiplicative^cond / Primary
        Primary     <- '(' Additive ')' / Number
        Number      <- < [0-9]+ >
        %whitespace <- [ \t]*
        cond <- '' { error_message "missing multiplicative" }
    )");

  assert(static_cast<bool>(parser) == true);

  // (3) Setup actions
  parser["Additive"] = [](const SemanticValues &vs) {
    switch (vs.choice()) {
    case 0: // "Multiplicative '+' Additive"
      return any_cast<int>(vs[0]) + any_cast<int>(vs[1]);
    default: // "Multiplicative"
      return any_cast<int>(vs[0]);
    }
  };

  parser["Multiplicative"] = [](const SemanticValues &vs) {
    switch (vs.choice()) {
    case 0: // "Primary '*' Multiplicative"
      return any_cast<int>(vs[0]) * any_cast<int>(vs[1]);
    default: // "Primary"
      return any_cast<int>(vs[0]);
    }
  };

  parser["Number"] = [](const SemanticValues &vs) {
    return vs.token_to_number<int>();
  };

  // (4) Parse
  parser.enable_packrat_parsing(); // Enable packrat parsing.

  int val = 0;
  //parser.parse(" (1 + 2) * ", val);
    
  parser.parse(" (1 + 2) * 3", val);
  std::cout << val << std::endl;

  // assert(val == 9);
  //assert(val == 0);
}

相比较于Bison，个人觉得看起来简单易懂，这个的输出结果为9

你甚至能看到使用PEG解析Docx：docx.cc，源代码有些长，这里就不贴了

思考

和正文内容没多大关系😂大伙们忽略就行

我时常在想，SQL解析器本质是对自然语言的一种处理/抽象，那为什么不能直接跨过SQL解析，直接Text2Data？（似乎和这篇文章无关了），低结构化跟容易达成共识，就像C与LISP，HTML与XML一样。只能说大伙们习惯SQL了，瘦死的骆驼终究比马大。