Indexed LL(k) grammars. (English) Zbl 0577.68077

The classes of indexed LL(k) grammars and strong indexed LL(k) grammars are defined. First the class of strong indexed LL(k) grammars is investigated. In particular, it is shown that the strong indexed LL(k) property is decidable and that the class of strong indexed LL(k) languages is contained in the class of deterministic indexed languages. Furthermore it is proved that the deterministic context-free languages coincide with the right linear strong indexed LL(1) languages and are a proper subset of the strong indexed LL(1) languages. The remainder of the paper is devoted to proving the decidability of the (general) indexed LL(k) property. To prove this result, a general transformation of indexed grammars is introduced. This transformation unifies proof techniques used in the context-free and indexed areas. (Authors’ summary).
Reviewer: J.Pittl


68Q45 Formal languages and automata
68N20 Theory of compilers and interpreters