2 分钟阅读

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

Let:

  • P be the set of all predictive parsers
  • Q be the set of all recursive descent parsers
  • Δ be the set of all top-down parsers

Informally we have the following relationship:

  • PΔ
  • QΔ
  • PQ
  • PQ
  • QP

Informally we can define like:

P={pΔp deterministically picks a production for derivation in each step}P={pΔp undeterministically picks a production, backtracking if failed}Q={pΔp calls procedure A(), which recusively calls X1(),,Xn(), if production AX1Xn is picked}Q={pΔp maintains a stack explicitly, rather than implicitly via recursive calls}

Examples:

  • PQ : e.g. a vanilla LL(1) parser
  • PQ : e.g. an LL(1) parser using a stack
  • PQ : e.g. an PEG parser which handles prioritized choice Ae1/e2//en
    • A() calls e1(), if failed, backtracks and calls e2().
    • Repeat until some ei() succeeds
  • PQ: e.g. a PEG parser like above, but using a stack

2. LL(k)=?PPermalink

理想情况下你可以认为 LL(k)=P.

现实世界中,你可能会有些 LL(k) variant,比方说:我主体框架是个 LL(1) parser,但其中有一个 production Aαβ 是用 special rule 限定的。此时你这个 parser 肯定不是严格意义的 LL(1),但它也能算是 predictive. 此时就是 LL(k)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]=(SaX) and M[S,b]=(SbY),但程序可以写成:

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

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

注意 PQ 一般会用 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::=e1/e2//en

这么一来,这个 parser 既有 predictive 成分 (来自 LL(0) 或者 LL(1)),又有 backtracking 成分 (来自 PEG 的 prioritized choice). 理论上这个 parser 既 PP,但它 Δ.

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

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

分类:

更新时间:

留下评论