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.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||51|
|Publication status||Published - Sep 1975|
- HMI-SLT: Speech and Language Technology