Re: ambiguity (Dennis Mickunas)
25 May 1997 13:28:24 -0400

          From comp.compilers

Related articles
ambiguity (Stefan Kauer) (1997-05-22)
Re: ambiguity (1997-05-25)
| List of all articles for this month |

From: (Dennis Mickunas)
Newsgroups: comp.compilers
Date: 25 May 1997 13:28:24 -0400
Organization: University of Illinois at Urbana
References: 97-05-270
Keywords: parse, theory, bibliography

Stefan Kauer <> writes:


>I have a rather theoretical question, for which I found no answer in
>several standard books on compiler writing.

>I have a context free, unambigious grammar, which contains left
>recursion. When the left recursion is removed (by any well known
>standard algorithm), is always the case, that the new grammar is also

>If not, I'd like to see an example. If yes, I'd like to see the proof
>(or a reference to a book or paper).

Even better--cover grammars. From a tech report by Anton Nijholt:

A. Nijholt
"A Survey of Normal Form Covers For Context Free Grammars"
Informatica Rapport 49
Vrije Universiteit
(February, 1979)

"Any e-free CFG G (cycle-free, no useless symbols) can be
transformed to a NLR [non left-recursive] grammmar G' such that
G'[r/r]G and G'[l/r]G. This result first appeared in Nijholt [7].
Soisalon-Soininen [11] gave a more simple proof of this result. One
of the transformations which is used in the latter paper is based on
an idea of Kurki-Suonio [5]. This trick can also be used for a
transformation presented in Wood [14] and which is due to J.M.

[5] Kurki-Suonio, R., "On top-to-bottom recognition and left
recursion," CACM 9 (1966), pp. 527-528.

[7] Nijholt, A., "On the covering of left-recursive grammars," 4th
POPL (1977), pp. 86-96.

[11] Soisalon-Soininen, E., "On the covering problem for
left-recursive grammars," Theor. Comput. Science 8 (1979), pp. 1-12.

[14] Wood, D., "The normal form theorem -- another proof," Computer
Journal 12 (1966), pp. 139-147.
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801 (217) 333-6351

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.