1page_util_norm_peg(n) Parser generator tools page_util_norm_peg(n)
2______________________________________________________________________________
6
8 page_util_norm_peg - page AST normalization, PEG
9
11 package require page::util::norm_peg ?0.1?
12 package require snit
14 ::page::util::norm::peg tree
16______________________________________________________________________________
18
20 This package provides a single utility command which takes an AST for a
21 parsing expression grammar and normalizes it in various ways. The re‐
22 sult is called a Normalized PE Grammar Tree.
23 Note that this package can only be used from within a plugin managed by
25 the package page::pluginmgr.
26
28 ::page::util::norm::peg tree
29 This command assumes the tree object contains for a parsing ex‐
30 pression grammar. It normalizes this tree in place. The result
31 is called a Normalized PE Grammar Tree.
32 The following operations are performd
34 [1] The data for all terminals is stored in their grand‐
36 parental nodes. The terminal nodes and their parents are
37 removed. Type information is dropped.
38 [2] All nodes which have exactly one child are irrelevant and
40 are removed, with the exception of the root node. The im‐
41 mediate child of the root is irrelevant as well, and re‐
42 moved as well.
43 [3] The name of the grammar is moved from the tree node it is
45 stored in to an attribute of the root node, and the tree
46 node removed.
47 The node keeping the start expression separate is removed
49 as irrelevant and the root node of the start expression
50 tagged with a marker attribute, and its handle saved in
51 an attribute of the root node for quick access.
52 [4] Nonterminal hint information is moved from nodes into at‐
54 tributes, and the now irrelevant nodes are deleted.
55 Note: This transformation is dependent on the removal of
57 all nodes with exactly one child, as it removes the all
58 'Attribute' nodes already. Otherwise this transformation
59 would have to put the information into the grandparental
60 node.
61 The default mode given to the nonterminals is value.
63 Like with the global metadata definition specific infor‐
65 mation is moved out out of nodes into attributes, the now
66 irrelevant nodes are deleted, and the root nodes of all
67 definitions are tagged with marker attributes. This pro‐
68 vides us with a mapping from nonterminal names to their
69 defining nodes as well, which is saved in an attribute of
70 the root node for quick reference.
71 At last the range in the input covered by a definition is
73 computed. The left extent comes from the terminal for the
74 nonterminal symbol it defines. The right extent comes
75 from the rightmost child under the definition. While this
76 not an expression tree yet the location data is sound al‐
77 ready.
78 [5] The remaining nodes under all definitions are transformed
80 into proper expression trees. First character ranges,
81 followed by unary operations, characters, and nontermi‐
82 nals. At last the tree is flattened by the removal of su‐
83 perfluous inner nodes.
84 The order matters, to shed as much nodes as possible
86 early, and to avoid unnecessary work later.
87
89 This document, and the package it describes, will undoubtedly contain
90 bugs and other problems. Please report such in the category page of
91 the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please
92 also report any ideas for enhancements you may have for either package
93 and/or documentation.
94 When proposing code changes, please provide unified diffs, i.e the out‐
96 put of diff -u.
97 Note further that attachments are strongly preferred over inlined
99 patches. Attachments can be made by going to the Edit form of the
100 ticket immediately after its creation, and then using the left-most
101 button in the secondary navigation bar.
102
104 PEG, graph walking, normalization, page, parser generator, text pro‐
105 cessing, tree walking
106
108 Page Parser Generator
109
111 Copyright (c) 2007 Andreas Kupries <andreas_kupries@users.sourceforge.net>
112tcllib 1.0 page_util_norm_peg(n)