Increasing the Applicability of LR Parsing

Mark-Jan Nederhof; Janos J. Sarbo

Increasing the Applicability of LR Parsing

Correct Metadata for

Use this form to create a GitHub issue with structured data describing the correction. You will need a GitHub account. Once you create that issue, the correction will be reviewed by a staff member.

⚠️ Mobile Users: Submitting this form to create a new issue will only work with github.com, not the GitHub Mobile app.

Important: The Anthology treat PDFs as authoritative. Please use this form only to correct data that is out of line with the PDF. See our corrections guidelines if you need to change the PDF.

Title Adjust the title. Retain tags such as <fixed-case>.

Authors Adjust author names and order to match the PDF.

Abstract Correct abstract if needed. Retain XML formatting tags such as <tex-math>. You may use <b>...</b> for bold, <i>...</i> for italic, and <url>...</url> for URLs.

Verification against PDF Ensure that the new title/authors match the snapshot below. (If there is no snapshot or it is too small, consult the PDF.)

Authors concatenated from the text boxes above:

ALL author names match the snapshot above—including middle initials, hyphens, and accents.

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

PDF Cite Search Fix data

Export citation

BibTeX
MODS XML
Endnote
Preformatted

@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."
}

Download as File

<?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>

Download as File

%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

Download as File

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.