predictive parsing

发表于

predictive parsing

能预测使用哪一个production：

  • 通过观察接下来的tokens；
  • 没有回溯；

predictIve parsers接收LL(k)语法（left to right，leftmost derivation），k代码向前看k个tokens

LL(1):每一个step，只能选择一个production

但这里有一个问题就是，对于这样的grammar：

1
2
3
E->T+E|T

T->int | int * T | (E)

很难去根据next token预测T和E；

解决方法就是：left factoring，即去除公共前缀；

1
2
3
4
5
E->TX
X->+E|epsilon

T->intX|(E)
X->*T|epsilon

First Sets

如果a->tB，即a能推导出在第一个位置的t,那么t属于First(a)

定义：

First(X) = {t|X->ta}并{ε|X->ε}

算法：

  1. First(t)={t}
  2. ε属于First(X)
  • if X->ε
  • if X->A1A2...Ana and ε属于First(Aj)for 1<=j<=n
  1. First(a)属于Frist(X) if X->A1..An a and ε属于First(Aj) for 1<=j<=n

Follow Sets

定义：

Follow(X)={t|S->*βXtε}

follow sets没有ε

Intution:

if X->AB, then First(B)属于Follow(A) and Follow(X)属于Follow(B) * if B->*ε then Follow(X)属于Follow(B)

if S 是开始symbol，$属于Follow(S)

algorithm sketch

  1. $属于Follow(S)
  2. First(β)-{ε} 属于 Follow(X), when A->aXβ
  3. Follow(A)属于Follow(X)
  • 对于每一个production， A->aXB 都有B->ε

LL(1) Parsing tables

构建一个parsing tables：

对于每一个production：A->a:

  • 对于每一个终止符t属于First(a): T[A, t] = a
  • 如果ε属于First(a), 对于每一个终止符t属于Follow(A): T[A, t] = a
  • 如果ε属于First(a)，并且$属于Follow(A): T[A, $] = a

如果parsing table中的entry有两项，就会有冲突：

比如：S->Sa|b

First(S) = {b};

Follow(S) = {$, a};

这种情况下，就不是LL(1)。

bottom up parsing

  • bottom up比top down更加常用和有效

这种方式就是主键的规约，回到start symbol：

1
2
3
4
5
6
int * int + int    T->int
int * T + int      T->int * T
T + int            T->int
T + T              E->T
T + E              E->T+E
E
  • trace a rightmost derivation in reverse

shift-reduce parsing

shift,reduce是bottom-up parsing的两个操作

  • Shift a terminal to the left string
  • apply an inverse production at the right end of the left string