Top-Down Parsing(2)

Nonrecursive Predictive Parsing

• 만약 $w$가 지금까지 match해온 input이라면, stack에는 $S\,\,\overset{*}{\underset{lm}\Rightarrow}\,\,w\alpha$를 만족하는 sequence of grammar symbols $\alpha$가 존재한다.

• Algorithm 4.34 : Table-driven predictive parsing
  • INPUT : A string $w$ and a parsing table $M$ for grammar $G$
  • OUTPUT : If $w$ is in $L(G)$, a leftmost derivation of $w$; otherwise, an error indication.
  • METHOD : 처음에 input buffer에는 $w\$$가 들어있고 $G$의 start symbol $S$가 $\$$ 위의 stack의 제일 윗부분에 위치해 있다. 아래 프로그램은 predictive parsing table $M$을 이용해서 predictive parse를 만들어 낸다.