On Parsing LL-Languages

Usually, a parser for an LL(k)-grammar G is a deterministic pushdown transducer which produces a leftmost derivation for a given input string $x \in L(G)$. Ukkonen (1983) has given a family of LL(2)-grammars proving that every parser for these grammars has exponential size. If we add to a parser the possibility to manipulate a constant number of pointers which point to positions within the constructed part of the leftmost derivation and to change the output in such positions, we obtain an extended parser for the LL(k)-grammar G. Given an arbitrary LL(k)-grammar G, we will show how to construct an extended parser of polynomial size manipulating at most k² pointers.