### Abstract

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

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

}

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

**On the covering of parsable grammars.** / Nijholt, Anton.

Research output: Book/Report › Report › Other research output

TY - BOOK

T1 - On the covering of parsable grammars

AU - Nijholt, Anton

PY - 1975/9

Y1 - 1975/9

N2 - 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.

AB - 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.

KW - EWI-9552

KW - HMI-SLT: Speech and Language Technology

M3 - Report

BT - On the covering of parsable grammars

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -