On the Transformation of LL(k)-linear Grammars to LL(1)-linear

摘要

It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of m~(2k-O(1)) where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(l)-linear grammar must have at least n·(m- 1)~(2k-O(log k) nonterminal symbols.