We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||56|
|Publication status||Published - Sep 1975|
- HMI-SLT: Speech and Language Technology