1. “Recursive Descent” and “Predictive” are just 2 implementation mechanisims of top-down parsersPermalink

Let:

• $\mathcal{P}$ be the set of all predictive parsers
• $\mathcal{Q}$ be the set of all recursive descent parsers
• $\mathrm{\Delta }$ be the set of all top-down parsers

Informally we have the following relationship:

• $\mathcal{P}\subset \mathrm{\Delta }$
• $\mathcal{Q}\subset \mathrm{\Delta }$
• $\mathcal{P}\cap \mathcal{Q}\ne \varnothing$
• $\mathcal{P}\not\subset \mathcal{Q}$
• $\mathcal{Q}\not\subset \mathcal{P}$

Informally we can define like:

Examples:

• $\mathcal{P}\cap \mathcal{Q}$ : e.g. a vanilla $LL(1)$ parser
• $\mathcal{P}\cap {\mathcal{Q}}^{\complement }$ : e.g. an $LL(1)$ parser using a stack
• ${\mathcal{P}}^{\complement }\cap \mathcal{Q}$ : e.g. an PEG parser which handles prioritized choice $A\to e_1/e_2/\dots /e_n$
  • $A()$ calls $e_1()$, if failed, backtracks and calls $e_2()$.
  • Repeat until some $e_i()$ succeeds
• ${\mathcal{P}}^{\complement }\cap {\mathcal{Q}}^{\complement }$: e.g. a PEG parser like above, but using a stack

2. $LL(k)\stackrel{?}{=}\mathcal{P}$Permalink

理想情况下你可以认为 $LL(k)=\mathcal{P}$.

现实世界中，你可能会有些 $LL(k)$ variant，比方说：我主体框架是个 $LL(1)$ parser，但其中有一个 production $A\to \alpha \mid \beta$ 是用 special rule 限定的。此时你这个 parser 肯定不是严格意义的 $LL(1)$，但它也能算是 predictive. 此时就是 $LL(k)\subset \mathcal{P}$.

3. $LL(k)$: “Table-Driven” vs “Hardcoded”Permalink

对 $LL(0)$ 而言，根本就不需要 PPT (predictive parsing table)，你照着 production 写就完事了。比如：

S : 'a' X;
X : 'x';

def S():
    match('a')
    X()

def X():
    match('x')

对于 $LL(1)$ 而言，PPT (predictive parsing table) 中的每一个 cell 至多只有 1 条 production，所以 parser 程序完全没有查表的必要，直接 if-else hardcode 就搞定了。比如：

S : 'a' X;
  | 'b' Y;
X : 'x' ;
Y : 'y' ;

假设 PPT 为 $M$，有 $M[S,a]=(S\to aX)$ and $M[S,b]=(S\to bY)$，但程序可以写成：

def S():
    if lookahead() == 'a':
        match('a')
        X()
    elif lookahead() == 'b':
        match('b')
        Y()
    else:
        raise error()

即使上升到 $LL(2)$，你仍然是可以用 if-else 的，但是就不够优雅、高效，此时就可以在程序里上 PPT 了。

注意 $\mathcal{P}\cap {\mathcal{Q}}^{\complement }$ 一般会用 PPT 实现，以至于有的地方讲到 “table-driven” 都默认是 stack + table 了，I don’t like this.

4. PEG: “Parser Combinator”Permalink

PEG parser 经常会讲到 “parser combinator” 的概念。这里 combinator 又是 Lambda Calculus 的概念，但我们只用把它简单理解成：a combinator is a higher-order function that

1. takes one or more functions as input,
2. combines them using only function application (no free variables or external state),
3. returns a new function as a result

在 PEG parser 中主要体现在某些辅助函数，比如这个 parse_one_or_more():

def parse_one_or_more(symbol) -> list[dict]:
    first_result = symbol()
    rest_results = parse_zero_or_more(symbol)
    return first_result + rest_results

那么 grammar 中的 <program> ::= <statement>+ 的 parsing 就可以写成：

def statement():
    pass

def program():
    return parse_one_or_more(statement)

Unix pipes 也可以理解成为一种 combinator: new_cmd ::= cmd_1 | cmd_2

5. Hybirds of $LL(k)$ + PEGPermalink

我完全可以做出一个 “四不像” 的 parser，比如：

• 它可以用 $LL(0)$ 或者 $LL(1)$ 做底
• 但某些 production 我们用 prioritized choice $S::=e_1/e_2/\dots /e_n$

这么一来，这个 parser 既有 predictive 成分 (来自 $LL(0)$ 或者 $LL(1)$)，又有 backtracking 成分 (来自 PEG 的 prioritized choice). 理论上这个 parser 既 $\notin \mathcal{P}$ 也 $\notin {\mathcal{P}}^{\complement }$，但它 $\in \mathrm{\Delta }$.

我也可以让这个 parser 一半用 recursive calls，一半用 table-driven.

总之就是说，现实情况可能会很复杂 (各种补丁)，要灵活应对。