### Abstract

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.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 56 |

Publication status | Published - Sep 1975 |

### Keywords

- EWI-9552
- HMI-SLT: Speech and Language Technology

## Cite this

Nijholt, A. (1975).

*On the covering of parsable grammars*. Enschede: University of Twente, Department of Applied Mathematics.