page_util_norm_peg(n)					      Parser generator tools					     page_util_norm_peg(n)

__________________________________________________________________________________________________________________________________________________

NAME

       page_util_norm_peg - page AST normalization, PEG

SYNOPSIS

       package require page::util::norm_peg  ?0.1?

       package require snit

       ::page::util::norm::peg tree

_________________________________________________________________

DESCRIPTION

       This  package  provides a single utility command which takes an AST for a parsing expression grammar and normalizes it in various ways. The
       result is called a Normalized PE Grammar Tree.

       Note that this package can only be used from within a plugin managed by the package page::pluginmgr.

API

       ::page::util::norm::peg tree
	      This command assumes the tree object contains for a parsing expression grammar. It normalizes this tree in  place.   The	result	is
	      called a	Normalized PE Grammar Tree.

	      The following operations are performd

	      [1]    The  data	for  all  terminals is stored in their grandparental nodes. The terminal nodes and their parents are removed. Type
		     information is dropped.

	      [2]    All nodes which have exactly one child are irrelevant and are removed, with the exception of the  root  node.  The  immediate
		     child of the root is irrelevant as well, and removed as well.

	      [3]    The  name	of  the  grammar  is  moved from the tree node it is stored in to an attribute of the root node, and the tree node
		     removed.

		     The node keeping the start expression separate is removed as irrelevant and the root node of the start expression tagged with
		     a marker attribute, and its handle saved in an attribute of the root node for quick access.

	      [4]    Nonterminal hint information is moved from nodes into attributes, and the now irrelevant nodes are deleted.

		     Note:  This transformation is dependent on the removal of all nodes with exactly one child, as it removes the all 'Attribute'
		     nodes already. Otherwise this transformation would have to put the information into the grandparental node.

		     The default mode given to the nonterminals is value.

		     Like with the global metadata definition specific information is moved out out of nodes into attributes, the  now	irrelevant
		     nodes  are  deleted, and the root nodes of all definitions are tagged with marker attributes. This provides us with a mapping
		     from nonterminal names to their defining nodes as well, which is saved in an attribute of the root node for quick reference.

		     At last the range in the input covered by a definition is computed. The left extent comes from the terminal for the nontermi-
		     nal  symbol  it  defines.	The right extent comes from the rightmost child under the definition. While this not an expression
		     tree yet the location data is sound already.

	      [5]    The remaining nodes under all definitions are transformed into proper expression trees. First character ranges,  followed	by
		     unary operations, characters, and nonterminals. At last the tree is flattened by the removal of superfluous inner nodes.

		     The order matters, to shed as much nodes as possible early, and to avoid unnecessary work later.

BUGS, IDEAS, FEEDBACK
       This  document,	will  undoubtedly  contain  bugs  and  other  problems.  Please report such in the category page of the Tcllib SF Trackers
       [http://sourceforge.net/tracker/?group_id=12883].  Please also report any ideas for enhancements you may have.

KEYWORDS

       PEG, graph walking, normalization, page, parser generator, text processing, tree walking

CATEGORY

       Page Parser Generator

COPYRIGHT

       Copyright (c) 2007 Andreas Kupries <andreas_kupries@users.sourceforge.net>

page									1.0						     page_util_norm_peg(n)