PE Grammar Tree, after Realizability Computation
================================================

This file documents the augmentations to a Normalized PE Grammar Tree
as inserted by the transformational package
'page::analysis::peg::realizable'. 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
transformations, as long as they are not in conflict with the
augmentations specified here.

Background
----------

The realizability of a nonterminal is usually defined for Context Free
Grammars. For PE grammars we define the property by treating them as
CFG and then following the usual definition, given below:

	A nonterminal symbol N of a CF grammar G is useful, if and
	only if a terminal sentence can be derived from it in a finite
	number of steps. A terminal sentence is a sentence which is
	either empty or contains only terminal symbols.

This intrinsic specification is equivalent to the following explicit
rules for the computation of realizability of arbitrary parsing
expressions:

*	A char expression (t) is realizable.
*	A range expression (..) is realizable.
*	A special expression (alnum, alpha) is realizable.
*	A dot expression (.) is realizable.
*	An epsilon expression (epsilon) is realizable.
*	A sequence expression (x) is realizable if and only if all of its
	argument expressions are realizable.
*	A choice-expression (/) is realizable if and only if at least one
	of its argument expressions is realizable [1].
*	A Kleene closure (*) is realizable.
*	A positive Kleene closure (+) is realizable, if and only if its
	argument expression is realizable.
*	An optional expression (?) is realizable.
*	A nonterminal expression is realizable if and only if the invoked
	nonterminal definition is realizable.
*	A nonterminal definition is realizable if and only if its
	definining expression is realizable.
*       All other expressions are not realizable.

From the rules above it is clear that the property is defined by the
leaves of the expression trees and then flows upward towards the
roots, and at the roots it jumps over the gap from nonterminal
definition to nonterminal use for further propagation.

This leads to an iterative algorithm which starts with the initial set
of realizable nodes and then works its way to find all of their parents
which are also realizable.

[1]   It is here where we treat the PEG like a CFG. The ordered choice
is implicitly handled like an unordered choice.


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

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

Structure
---------

* The structure of the tree is unchanged.

Attributes
----------

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

		Contains a list of the nodes which are realizable.
----	----	-------
pg::peg::unrealizable
	list
		Root node only. Contains a list of the nodes which are
		__not__ realizable.
----	----	-------

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

The realizability transformation is based on the realizability computation
and the agumented tree generated by it. The transformation removes all
(partial) expressions and definitions are not realizable. This may leave
the grammar without definitions, and without a start expression as
well.

Note that this change may remove invokations of undefined nonterminal
symbols. It however cannot produce new invokations of undefined
nonterminal symbols as a unrealizable definition implies a
unrealizable invokation, i.e. the invokations of unrealizable
definitions are removed themselves as well.