1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
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).
|
