Tcl Library Source Code

View Ticket
Login
Ticket UUID: 4a80a491180a452298431fd53039d9505ab2180d
Title: New modes for nonterminals
Type: RFE Version:
Submitter: lars_h_again Created on: 2024-01-24 07:10:26
Subsystem: pt (parsetools) Assigned To: nobody
Priority: 5 Medium Severity: Minor
Status: Open Last Modified: 2024-01-24 07:10:26
Resolution: None Closed By: nobody
    Closed on:
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.