PE Grammar Tree, after Reachables Computation
=============================================

This file documents the augmentations to a Normalized PE Grammar Tree
as inserted by the transformational package 'pg::peg::reachable'. The
input to the transformation is assumed to be a 'Normalized PE Grammar
Tree' as described in 'doc_normalize.txt', possibly with augmentations
from other transformation, as long as they are not in conflict with
the augmentations specified here.

General information
-------------------

* The specification of 'doc_normalize.txt' applies fully.

Structure
---------

* The structure of the tree is unchanged.

Attributes
----------

Name	Type	Details
----	----	-------
pg::peg::reachable
	list
		Root node only. The presence of this attribute
		indicates that the reachable computation has been been
		executed on the grammar and that we have valid
		results.

		Contains a list of the nodes (definition, and
		expression) which are reachable from the root node of
		the start expression.
----	----	-------
pg::peg::unreachable
	list
		Root node only. Contains a list of the nodes
		(definition, and expression) which are __not__
		reachable from the root node of the start expression.
----	----	-------

Reachability is defined on the definition and expression nodes via

- The root node of the start expression is reachable.
- An expression node is reachable if its parent node (expression or
  definition) is reachable.
- A definition node is reachable, if at least one its using expression
  nodes is reachable.
- No other node is reachable.

This definition leads to a simple recursive (top-down) algorithm for
sweeping a grammar and marking all reachable nodes. We do however
remember only the reachbility of definitions, as that is the only
information truly relevant.

Transformation
--------------

The reachable transformation is based on the reachable computation and
the agumented tree generated by it. The transformation removes all
definitions which are not reachable. This may leave the grammar
without definitions.

Note that this change may remove invokations of undefined nonterminal
symbols. It however cannot produce new invokations of undefined
nonterminal symbols as the removed definitions have no actual users by
definition. Those which have invoking nodes (as recorded in 'users')
are used by an unreachable definition (This can be an unreachable
circle of definitions).