normalizing

Can anybody tell me what does normalizing mean in compiler design jargon?
[Depends what you're normalizing.  A grammar?  A syntax tree?  Something
else?  -John]

On Tue, Mar 08, 2005 at 10:37:11PM -0500, diehard_sundar@yahoo.com wrote:
> Can anybody tell me what does normalizing mean in compiler design jargon?

"Normalization" is a term that compiler designers obtained from their
abstract mathematical roots.  A "normal form" is a restricted form of
some mathematical formalism that preserves the original meaning of the
thing, and normalization is the process by which an arbitrary instance
of the mathematical formalism is converted into the normal form.  There
are many mathematical forms in use in compiler construction (many
deriving from formal language theory).  One example is the context-free
grammar (CFG), whose theory forms the basis for tools like Bison and
Yacc.  A CFG may be converted into a pushdown automaton that accepts the
same language by normalizing the CFG into a suitable normal form first
(Greibach normal form is traditionally used for this purpose IIRC).
There are many other examples.

Database design and data modeling also use the term in the exact same
sense.  The database normal forms are in the same way restricted models
of the original data.

--
The individual has always had to struggle to keep from being overwhelmed by
the tribe.  To be your own man is a hard business.  If you try it, you'll be
lonely often, and sometimes frightened.  But no price is too high to pay for
the privilege of owning yourself.
http://stormwyrm.blogspot.com/

On 8 Mar 2005 22:37:11 -0500 in comp.compilers,
diehard_sundar@yahoo.com wrote:

>Can anybody tell me what does normalizing mean in compiler design jargon?
>[Depends what you're normalizing.  A grammar?  A syntax tree?  Something
>else?  -John]

One of these? http://en.wikipedia.org/wiki/Normal_form
Maybe this one: http://en.wikipedia.org/wiki/Chomsky_normal_form

--
Thanks. Take care, Brian Inglis 	Calgary, Alberta, Canada

Brian.Inglis@CSi.com  	(Brian[dot]Inglis{at}SystematicSW[dot]a
b[dot]ca)
fake address		use address above to reply