Re: ambiguity

Stefan Kauer <kauer@paxp01.mipool.uni-jena.de> writes:


>Hello,


>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
>unambigious?


>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.
Foster."


[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
mickunas@cs.uiuc.edu (217) 333-6351
http://www-sal.cs.uiuc.edu/~mickunas
--

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