Tcl Library Source Code

View Ticket
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to
or submit via the online form by Sep 9.
Ticket UUID: 351b8b2f55519f12d5c4f889b68ecee7db97118a
Title: Bug fixes on PT/PEG transformation operations
Type: Bug Version: trunk
Submitter: ssoberni Created on: 2018-06-14 14:39:38
Subsystem: pt (parsetools) Assigned To: aku
Priority: 5 Medium Severity: Severe
Status: Closed Last Modified: 2018-07-09 21:29:58
Resolution: Fixed Closed By: aku
    Closed on: 2018-07-09 21:29:58

As promised, I reworked a series of bug fixes on PEG transformations (realizability, dropping) into a fix branch: [].

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]


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

Let me know what you think!

User Comments: aku added on 2018-07-09 21:29:58:

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.

aku added on 2018-07-09 21:17:28:

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.

aku added on 2018-07-09 19:50:03:

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].