Regular extensions of some classes of grammars

Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.