Tcl Library Source Code

Ticket Change Details

Artifact ID: b58fc58ec6c04dbaaedbde9a3f20d65c21b748037a0f7f59a836df5b99055319
Ticket: 351b8b2f55519f12d5c4f889b68ecee7db97118a
Bug fixes on PT/PEG transformation operations
User & Date: ssoberni 2018-06-14 14:57:26

  1. Change assignee to "aku"
  2. Change comment to:


    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!

    Thx, Stefan

  3. Change login to "ssoberni"
  4. Change mimetype to "text/plain"