Re: Grammar normalization?

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

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