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:
- Bibkey:
- 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)
- Copy Citation:
- PDF:
- https://aclanthology.org/1993.iwpt-1.16.pdf
Export citation
@inproceedings{nederhof-sarbo-1993-increasing,
title = "Increasing the Applicability of {LR} Parsing",
author = "Nederhof, Mark-Jan and
Sarbo, Janos J.",
editor = "Bunt, Harry and
Berwick, Robert and
Church, Ken and
Joshi, Aravind and
Kaplan, Ronald and
Kay, Martin and
Lang, Bernard and
Nagao, Makoto and
Nijholt, Anton and
Steedman, Mark and
Thompson, Henry and
Tomita, Masaru and
Vijay-Shanker, K. and
Wilks, Yorick and
Wittenburg, Kent",
booktitle = "Proceedings of the Third International Workshop on Parsing Technologies",
month = aug # " 10-13",
year = "1993",
address = "Tilburg, Netherlands and Durbuy, Belgium",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/1993.iwpt-1.16",
pages = "187--202",
abstract = "In this paper we describe a phenomenon present in some context-free grammars, called \textit{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.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="nederhof-sarbo-1993-increasing">
<titleInfo>
<title>Increasing the Applicability of LR Parsing</title>
</titleInfo>
<name type="personal">
<namePart type="given">Mark-Jan</namePart>
<namePart type="family">Nederhof</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Janos</namePart>
<namePart type="given">J</namePart>
<namePart type="family">Sarbo</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>1993-aug 10-13</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Third International Workshop on Parsing Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Harry</namePart>
<namePart type="family">Bunt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Robert</namePart>
<namePart type="family">Berwick</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ken</namePart>
<namePart type="family">Church</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aravind</namePart>
<namePart type="family">Joshi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ronald</namePart>
<namePart type="family">Kaplan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Martin</namePart>
<namePart type="family">Kay</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bernard</namePart>
<namePart type="family">Lang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Makoto</namePart>
<namePart type="family">Nagao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anton</namePart>
<namePart type="family">Nijholt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mark</namePart>
<namePart type="family">Steedman</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Henry</namePart>
<namePart type="family">Thompson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Masaru</namePart>
<namePart type="family">Tomita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">K</namePart>
<namePart type="family">Vijay-Shanker</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Yorick</namePart>
<namePart type="family">Wilks</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Kent</namePart>
<namePart type="family">Wittenburg</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Tilburg, Netherlands and Durbuy, Belgium</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<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.</abstract>
<identifier type="citekey">nederhof-sarbo-1993-increasing</identifier>
<location>
<url>https://aclanthology.org/1993.iwpt-1.16</url>
</location>
<part>
<date>1993-aug 10-13</date>
<extent unit="page">
<start>187</start>
<end>202</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings %T Increasing the Applicability of LR Parsing %A Nederhof, Mark-Jan %A Sarbo, Janos J. %Y Bunt, Harry %Y Berwick, Robert %Y Church, Ken %Y Joshi, Aravind %Y Kaplan, Ronald %Y Kay, Martin %Y Lang, Bernard %Y Nagao, Makoto %Y Nijholt, Anton %Y Steedman, Mark %Y Thompson, Henry %Y Tomita, Masaru %Y Vijay-Shanker, K. %Y Wilks, Yorick %Y Wittenburg, Kent %S Proceedings of the Third International Workshop on Parsing Technologies %D 1993 %8 aug 10 13 %I Association for Computational Linguistics %C Tilburg, Netherlands and Durbuy, Belgium %F nederhof-sarbo-1993-increasing %X 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. %U https://aclanthology.org/1993.iwpt-1.16 %P 187-202
Markdown (Informal)
[Increasing the Applicability of LR Parsing](https://aclanthology.org/1993.iwpt-1.16) (Nederhof & Sarbo, IWPT 1993)
- Increasing the Applicability of LR Parsing (Nederhof & Sarbo, IWPT 1993)
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.