1page_util_norm_peg(n)       Parser generator tools       page_util_norm_peg(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       page_util_norm_peg - page AST normalization, PEG
9

SYNOPSIS

11       package require page::util::norm_peg  ?0.1?
12
13       package require snit
14
15       ::page::util::norm::peg tree
16
17______________________________________________________________________________
18

DESCRIPTION

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
24       Note that this package can only be used from within a plugin managed by
25       the package page::pluginmgr.
26

API

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
33              The following operations are performd
34
35              [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
39              [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
44              [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
48                     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
53              [4]    Nonterminal hint information is moved from nodes into at‐
54                     tributes, and the now irrelevant nodes are deleted.
55
56                     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
62                     The default mode given to the nonterminals is value.
63
64                     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
72                     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
79              [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
85                     The order matters, to shed  as  much  nodes  as  possible
86                     early, and to avoid unnecessary work later.
87

BUGS, IDEAS, FEEDBACK

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
95       When proposing code changes, please provide unified diffs, i.e the out‐
96       put of diff -u.
97
98       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

KEYWORDS

104       PEG,  graph  walking,  normalization, page, parser generator, text pro‐
105       cessing, tree walking
106

CATEGORY

108       Page Parser Generator
109
111       Copyright (c) 2007 Andreas Kupries <andreas_kupries@users.sourceforge.net>
112
113
114
115
116tcllib                                1.0                page_util_norm_peg(n)
Impressum