On the covering of left-recursive grammars

Anton Nijholt

On the covering of left-recursive grammars

Research output: Book/Report › Report › Other research output

Abstract

In this report 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. Some additional results concerning parsing and covering strict determinisitc grammars are also given.

Original language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Number of pages	27
Publication status	Published - Apr 1976

Keywords

HMI-SLT: Speech and Language Technology
EWI-9554

Cite this

@book{f8aa6071cc7b4856a8d593b6375561d8,

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

abstract = "In this report 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. Some additional results concerning parsing and covering strict determinisitc grammars are also given.",

keywords = "HMI-SLT: Speech and Language Technology, EWI-9554",

author = "Anton Nijholt",

year = "1976",

month = apr,

language = "Undefined",

publisher = "University of Twente, Department of Applied Mathematics",

}

TY - BOOK

T1 - On the covering of left-recursive grammars

AU - Nijholt, Anton

PY - 1976/4

Y1 - 1976/4

N2 - In this report 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. Some additional results concerning parsing and covering strict determinisitc grammars are also given.

AB - In this report 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. Some additional results concerning parsing and covering strict determinisitc grammars are also given.

KW - HMI-SLT: Speech and Language Technology

KW - EWI-9554

M3 - Report

BT - On the covering of left-recursive grammars

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -