Re: Grammar normalization?

jjan@cs.rug.nl (Beeblebrox)
20 Dec 1995 11:34:43 -0500

          From comp.compilers

Related articles
Grammar normalization? Olivier.Ridoux@irisa.fr (1995-12-19)
Re: Grammar normalization? pardo@cs.washington.edu (1995-12-19)
Re: Grammar normalization? jjan@cs.rug.nl (1995-12-20)
Re: Grammar normalization? mickunas@mickunas.cs.uiuc.edu (1995-12-20)
| List of all articles for this month |

From: jjan@cs.rug.nl (Beeblebrox)
Newsgroups: comp.compilers
Date: 20 Dec 1995 11:34:43 -0500
Organization: Dept. of Computing Science, Groningen University
References: 95-12-120
Keywords: parse, theory

Olivier.Ridoux@irisa.fr (Olivier Ridoux) wrote:
< While we are at this, what is the state-of-the-art of *automatically*
< transforming a grammar *with* attributes (or actions, or generation
< points) into its Greibach normal form?


I remember from Compiler courses that a simple CFG with only synthetic
attributes and attribute evaluation rules, with leftrecursion (hence
not LL(1)), could be translated into an equivalent LL(1)
grammar. BUT... it required introducing inherited attributes to keep
equivalence in semantic meaning, i.e. the attributes calculate the
same information as in the original grammar. Therefore, I suspect that
transforming a grammar into its Greibach normal form will not be
simpler, in the presence of attributes/actions.


Greibach normal form: Every context free language L without epsilon can
be generated by a grammar for which every production is of the form
    A -> a \alpha
with A nonterminal, a a terminal symbol and \alpha a string of
(non-)terminals. For more on Greibach NF see for instance
Hopcroft,Ullman: 'Introduction to Automata Theory, Languages and
Computation', Addison-Wesley, 1979.


--
Jan Jongejan email: jjan@cs.rug.nl
Dept. Comp.Sci.,
Univ. of Groningen, 8-{)
Netherlands.
--


Post a followup to this message

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