Pushdown Accepters for Context-Free Languages

It is easy to design a pushdown accepter that carries out the operation of top-down syntax analysis. Let G=(N,T,P,S ) be an arbitrary context-free grammar.

Construction of a pushdown accepter M that “derives” any string in L(G):

Suppose that S Þ j ₁A_{1b 1} Þ ...Þ j _kA _{kb k Þ w} is the leftmost derivation of w where

j _iÎ T^* , A_i Î N, b _i Î (NÈ T) ^* g_i=1,..,k

For any context-free grammar G, one can construct a pushdown accepter M, such that L(M)=L(G). Moreover, the accepting move sequences in M are in one-to-one correspondence with leftmost derivations in G.

Back to Table of contents of Chapter6