Properties of deterministic top down grammars

Publisher Website
Google Scholar
Abstract
The class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are first defined and a procedure is given for determining if a context free grammar is LL(k) for a given value of k. It is shown that &egr;-rules can be eliminated from an LL(k) grammar, at the cost of increasing the value of k by one, and a description is given of a canonical pushdown machine for recognizing LL(k) languages. It is shown that for each value of k there are LL(k+l) languages that are not LL(k) languages. It is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.

This publication has 0 references indexed in Scilit: