Tcl Library Source Code

Hi!

As promised, I reworked a series of bug fixes on PEG transformations (realizability, dropping) into a fix branch: [https://core.tcl.tk/tcllib/timeline?r=pt-container-ssoberni].

In short:

1. minimize: the drop operations were in wrong order.

2. realizability: kleene star and optionals should be set realizable by definition (is consistent with other PEG environments, incl. tcllib's page).

3. Drop: 

o wrong variable name in one, previously untested code branch.

o drop was too permissive on expressions other than choice. In line with the realizability ruling, only choice should survive any removed children.

Generally, offering the otherwise CFG-aware grammar transformations should maybe prominently be marked with a disclaimer in the docs? This is because treating a PEG as a CFG is not necessarily a good idea, although limited use of transformations is warranted. A disclaimer should state that realizability of an ordered choice cannot be decided statically and is conceptually itchy (non-disjointness). Also, realizability of predicates is certainly debatable (in the sense of a non-productive or a non-recognising expression). In any case, the message should be that the result of a minimisation will not yield a minimal PEG, rather a conservative approximation of a minimisation, at best.

What do you think?

Final observation, but also debatable: ::pt::peg::op::drop::unrealizable starts from the set of defined non-terminals (RHS of rules), and not all reachable ones. This is not an issue per se, but if one composes PEGs or the corresponding rules (e.g., with deferred non-terminals) then they will be just dropped, along with most of the rest of the rules set. A more permissive, conservative setting would switching from

   set all [$container nonterminals]

to

   set all [::pt::peg::op reachable $container]

Let me know what you think!

Thx,
Stefan

Branch integrated, see commit [3720e40747].

And commit [4bbe140a79] makes the change to the `all` set of `drop unrealizable`.

For the disclaimer in the docs please provide a PR/branch.

Closing this ticket now as done.

Thank you for your patience.

Added some more tests, comments, notes.

Commmit [d907079d5b].

Regarding documentation question: I see no problem adding disclaimers about transform limitations and will accept PRs.

Wrt start set for `drop unrealizable` ... I can see that this can ignore unreachable. Even if they are realizable they would either go away later in the minimize, or simply be ignored during execution of either grammar interpreter or a generated parser.

Thank you for the additional test cases.

Had to put in some fixes to make them work, not much however: Disabled forgotten debug output in minimize, added forgotten pt_pexpr_op.tcl (pt::pe::op) to the set of supporting packages.

Commit [8436048fee].