| Description: |
It seems to me that the current **pt** mechanisms are missing two modes
for nonterminals, that would make it more convenient to make use of the
ASTs produced.
No node mode
------------
The existing modes are:
* **value** — make a new AST node for this nonterminal, and place all
ASTs for subordinate nonterminals as children.
* **leaf** — make a new AST node for this nonterminal, but discard any
ASTs from subordinate nonterminals.
* **void** — make no new AST node for this nonterminal, and discard any
ASTs from subordinate nonterminals.
This omits the fourth way of combining those two aspects:
* make no new AST node for this nonterminal, but keep any ASTs for
subordinate nonterminals, passing them on to the next level up as
candidates for becoming children.
For want of this, any nonterminal where there can be an inner structure
has to be given mode **value**, and thus give rise to nodes in the AST.
These nodes are frequently of no use, simply passing data on unchanged to
the next level. Not generating them in the first place will save us
from having to write code to do this pointless passing-along operation in
the first place.
This is close to the request in the
[Add "prune" mode](https://core.tcl-lang.org/tcllib/tktview/eb8c1e69ba)
ticket, but I don't suggest omitting nodes when they only have one child,
because that would still carry the possibility that such nodes might
appear and thus require code for dealing with them. I suggest a mode where
a nonterminal *never* appears as the type of an AST node. This is the
natural thing to do when you define a nonterminal because you want to have
a name for a particular parsing expression (perhaps because you want to
make the grammar more comprehensible), but that particular grouping is not
helpful for further processing of the AST.
### Tail recursions: motivations from general theory
As far as the parsing expression language is concerned, repetition can
always be converted to recursion; `P*` is the same as `R` with
`R <- (P R)?`. However, for these to produce the same AST, we don't want
nodes for the `R` — instead all the `P`s should be children of the parent of
the first `R`, just like they would for `P*`. This is exactly the effect
of giving `R` the suggested new mode.
Another recursion is the `S <- P / . S` for using the parser to search for
the first `P` in a document. If `S` here is **value** mode, then the AST
produced begins with an uninteresting stem of `S` nodes that can easily be
thousands of levels deep before we find the `P` we're looking for. That
AST as such is not intractable, merely wasteful, but one should take care
to not generate its string representation; whereas the string
representation of a stem *n* levels deep is merely O(*n*) characters,
together the string representations of all TclObjs in the stem requires
O(*n*^2) characters, and that can realistically push us to GB memory
usage! That is, if we're not careful about keeping the AST always a pure
list, which is doable, but still leaves us with an unnecessary risk; if
you start debugging, then requests for string representations are quick to
follow.
### Several trees going upwards
An objection against passing several sub-ASTs up to the next level might
be that this could be the top level, in which case we would end up with
not one but several roots. However, that is already a possibility, since
the start expression is defined as an *expression*, not a nonterminal.
```
% set peg {
PEG demo ( A B C !. )
A <- 'a'*;
B <- 'b'*;
C <- 'c'*;
END;}
```
is a perfectly good parsing expression grammar, according to the package;
```
% set G [pt::peg::from::peg convert $peg]
pt::grammar::peg {rules {A {is {* {t a}} mode value} B {is {* {t b}} mode value} C {is {* {t c}} mode value}} start {x {n A} {n B} {n C} {! dot}}}
% pt::peg::container GC deserialize $G
::GC
% pt::peg::interp Gparser
% Gparser use ::GC
```
goes through without errors. Of course, it doesn't let you parse anything
```
% Gparser parset aabbbc
Error: insufficient items on stack to fill request
```
but that is arguably more an error in the implementation. ;-)
Text content mode
-----------------
The example of the *pe-grammar-for-peg* demonstrates that in traditional
programming languages, a lot of the relevant information in the parsed
input is available in the AST structure, but as soon as you encounter
identifiers or literal constants, that is no longer sufficient; you need
to consult the actual text of the parsed input. That is straightforward
when you parse a string, since the AST tells you where the data is to be
found, but the general design of the Parser Tools is that the input is
read from a channel, and then random access is not so easy (or cheap)
anymore.
What would help would be a nonterminal mode that instructs the parser to
also record within the AST the contents of the range, since this places the
information close at hand where one would need it, at only a marginal
increase in size of the AST.
A potential catch is that the documented format of ASTs does not allow for
content other than node types, positions, and child nodes; the uniform
iterators `pt::ast bottomup` and `pt::ast topdown` presumably enforce
this restriction through their desire to blindly iterate over every node
of an AST. However, I think I (in some documentation or source file) have
spotted fragments of an intent that the empty string as node name, now
documented as not allowed, could be used to include data with other
structure. Thus a "text content" mode nonterminal node might have at index
3 a list with an empty string as first element, and the text content as
second element
```
Ident 513 515 {"" foo}
```
or some such. Not the most compact, but something that the `pt::ast`
iterators could understand.
|