On the covering of left recursive grammars

Anton Nijholt; A.V. Aho

doi:10.1145/512950.512959

On the covering of left recursive grammars

Anton Nijholt, A.V. Aho (Editor)

Research output: Contribution to conference › Paper › peer-review

6 Citations (Scopus)

162 Downloads (Pure)

Abstract

In this paper we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar.

Original language	Undefined
Pages	86-96
Number of pages	11
DOIs	https://doi.org/10.1145/512950.512959
Publication status	Published - Jan 1977
Event	4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - Los Angeles, USA Duration: 1 Jan 1977 → 1 Jan 1977

Conference

Conference	4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages
Period	1/01/77 → 1/01/77

Keywords

IR-66787
EWI-8806
HMI-SLT: Speech and Language Technology

Access to Document

10.1145/512950.512959

Nijholt77leftFinal published version, 744 KB

Cite this

@conference{c4dfa42e78d8408897c932e06ab485d9,

title = "On the covering of left recursive grammars",

abstract = "In this paper we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar.",

keywords = "IR-66787, EWI-8806, HMI-SLT: Speech and Language Technology",

author = "Anton Nijholt and A.V. Aho",

year = "1977",

month = jan,

doi = "10.1145/512950.512959",

language = "Undefined",

pages = "86--96",

note = "null ; Conference date: 01-01-1977 Through 01-01-1977",

}

TY - CONF

T1 - On the covering of left recursive grammars

AU - Nijholt, Anton

A2 - Aho, A.V.

PY - 1977/1

Y1 - 1977/1

N2 - In this paper we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar.

AB - In this paper we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar.

KW - IR-66787

KW - EWI-8806

KW - HMI-SLT: Speech and Language Technology

U2 - 10.1145/512950.512959

DO - 10.1145/512950.512959

M3 - Paper

SP - 86

EP - 96

Y2 - 1 January 1977 through 1 January 1977

ER -