Re: normalizing

Rafael 'Dido' Sevilla <>
15 Mar 2005 01:39:29 -0500

          From comp.compilers

Related articles
normalizing (2005-03-08)
Re: normalizing (Rafael 'Dido' Sevilla) (2005-03-15)
Re: normalizing (Brian Inglis) (2005-03-15)
| List of all articles for this month |

From: Rafael 'Dido' Sevilla <>
Newsgroups: comp.compilers
Date: 15 Mar 2005 01:39:29 -0500
Organization: Compilers Central
References: 05-03-045
Keywords: design
Posted-Date: 15 Mar 2005 01:39:29 EST
Content-Disposition: inline

On Tue, Mar 08, 2005 at 10:37:11PM -0500, 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.

Post a followup to this message

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