𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the size of parsers and LR(k)-grammars

✍ Scribed by Hing Leung; Detlef Wotschke

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
122 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we consider two tradeo results regarding the economy of description in parsing. One result is on the tradeo between the size of a parser and its ability to detect an error early. The other result is on the tradeo between the size of an LR(k)-grammar and the length k of the lookahead.

πŸ“œ SIMILAR VOLUMES

On the reduction of LR(k) parsers
On the reduction of LR(k) parsers
✍ Woo-Jun Park; Myung-Joon Lee; Kwang-Moo Choe πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 595 KB
The emptiness of intersection problem fo
The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable
✍ Annie Foret πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 465 KB

This paper is concerned with usual decidability questions on grammars for some classes of categorial grammars that arise in the field of learning categorial grammars. We prove that the emptiness of intersection of two langages is an undecidable problem for the following classes : k-valued classical