Abstract
In this paper we describe a phenomenon present in some context-free grammars, called hidden left recursion. We show that ordinary LR parsing according to hidden left-recursive grammars is not possible and we indicate a range of solutions to this problem. One of these solutions is a new parsing technique, which is a variant of traditional LR parsing. This new parsing technique can be used both with and without lookahead and the nondeterminism can be realized using backtracking or using a graph-structured stack.- Anthology ID:
- 1993.iwpt-1.16
- Volume:
- Proceedings of the Third International Workshop on Parsing Technologies
- Month:
- August 10-13
- Year:
- 1993
- Address:
- Tilburg, Netherlands and Durbuy, Belgium
- Editors:
- Harry Bunt, Robert Berwick, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 187–202
- Language:
- URL:
- https://aclanthology.org/1993.iwpt-1.16
- DOI:
- Cite (ACL):
- Mark-Jan Nederhof and Janos J. Sarbo. 1993. Increasing the Applicability of LR Parsing. In Proceedings of the Third International Workshop on Parsing Technologies, pages 187–202, Tilburg, Netherlands and Durbuy, Belgium. Association for Computational Linguistics.
- Cite (Informal):
- Increasing the Applicability of LR Parsing (Nederhof & Sarbo, IWPT 1993)
- PDF:
- https://preview.aclanthology.org/teach-a-man-to-fish/1993.iwpt-1.16.pdf