Automatic Transformation of CFG to LL/LR

ramki@cs.du.edu (Ramki Thurimella)
Fri, 29 Jan 1993 18:13:15 GMT

          From comp.compilers

Related articles
Top-Down Parser Construction Conjectures bart@cs.uoregon.edu (1993-01-18)
Re: Recursive descent parsing is better than LL(1) pjj@cs.man.ac.uk (Pete Jinks) (1993-01-27)
Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-01-29)
Re: Automatic Transformation of CFG to LL/LR bart@cs.uoregon.edu (1993-02-02)
Re: Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-02-03)
| List of all articles for this month |

Newsgroups: comp.compilers
From: ramki@cs.du.edu (Ramki Thurimella)
Keywords: LL(1), parse
Organization: Compilers Central
References: 93-01-122 93-01-204
Date: Fri, 29 Jan 1993 18:13:15 GMT



I remember seeing recently a posting on this newsgroup requesting
pointers to the following question: given an arbitrary context-free
grammar, does there exist a program/tool that would automatically
convert it to LL(1) or LR(1) grammar.


While testing to see if a given CFG is LL(1) or LR(1) simple and
decidable, converting one is undecidable. Exercises 5.1.12 and 5.2.12 of


          Aho, A.V. and Ullman, J.D., "The Theory of Parsing, Translation,
          and Compiling," Vol. 1: Parsing, Prentice-Hall, Englewood Cliffs,
          N.J., 1972.


raise the same issues as that of the previous posting.


Ramki Thurimella
--


Post a followup to this message

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