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

6 Citations (Scopus)

50 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

Keywords

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

Access to Document

10.1145/512950.512959

Nijholt77left
open
Final published version, 744 KB

Cite this

Nijholt, A., & Aho, A. V. (Ed.) (1977). On the covering of left recursive grammars. 86-96. https://doi.org/10.1145/512950.512959

@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 = "1",

doi = "10.1145/512950.512959",

language = "Undefined",

pages = "86--96",

}

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

ER -