Top-Down Parsers: Recursive Descent, Predictive, and More

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

Let:

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

Informally we have the following relationship:

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

Informally we can define like:

\[\begin{aligned} \mathcal{P} &= \lbrace p \in \Delta \mid p \text{ deterministically picks a production for derivation in each step} \rbrace \newline \mathcal{P}^\complement &= \lbrace p \in \Delta \mid p \text{ undeterministically picks a production, backtracking if failed} \rbrace \newline \mathcal{Q} &= \lbrace p \in \Delta \mid p \text{ calls procedure } A() \text{, which recusively calls } X_1(), \dots, X_n() \text{, if production } A \to X_1 \dots X_n \text{ is picked} \rbrace \newline \mathcal{Q}^\complement &= \lbrace p \in \Delta \mid p \text{ maintains a stack explicitly, rather than implicitly via recursive calls} \rbrace \newline \end{aligned}\]

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}$

理想情况下你可以认为 $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”

对 $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”

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)$ + PEG

我完全可以做出一个 “四不像” 的 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 既 $\not \in \mathcal{P}$ 也 $\not \in \mathcal{P}^\complement$，但它 $\in \Delta$.

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

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