|ambiguity email@example.com (Stefan Kauer) (1997-05-22)|
|Re: ambiguity firstname.lastname@example.org (1997-05-25)|
|From:||email@example.com (Dennis Mickunas)|
|Date:||25 May 1997 13:28:24 -0400|
|Organization:||University of Illinois at Urbana|
|Keywords:||parse, theory, bibliography|
Stefan Kauer <firstname.lastname@example.org> 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 Survey of Normal Form Covers For Context Free Grammars"
Informatica Rapport 49
"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 .
Soisalon-Soininen  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 . This trick can also be used for a
transformation presented in Wood  and which is due to J.M.
 Kurki-Suonio, R., "On top-to-bottom recognition and left
recursion," CACM 9 (1966), pp. 527-528.
 Nijholt, A., "On the covering of left-recursive grammars," 4th
POPL (1977), pp. 86-96.
 Soisalon-Soininen, E., "On the covering problem for
left-recursive grammars," Theor. Comput. Science 8 (1979), pp. 1-12.
 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
email@example.com (217) 333-6351
Return to the
Search the comp.compilers archives again.