Index: modules/pt/pkgIndex.tcl ================================================================== --- modules/pt/pkgIndex.tcl +++ modules/pt/pkgIndex.tcl @@ -19,11 +19,11 @@ # Parsing Expression Grammar support. package ifneeded pt::peg 1 [list source [file join $dir pt_pegrammar.tcl]] package ifneeded pt::peg::container 1 [list source [file join $dir pt_peg_container.tcl]] package ifneeded pt::peg::interp 1.0.1 [list source [file join $dir pt_peg_interp.tcl]] -package ifneeded pt::peg::op 1.0.1 [list source [file join $dir pt_peg_op.tcl]] +package ifneeded pt::peg::op 1.0.2 [list source [file join $dir pt_peg_op.tcl]] package ifneeded pt::parse::peg 1.0.1 [list source [file join $dir pt_parse_peg.tcl]] # Export/import managers. Assumes an untrusted environment. package ifneeded pt::peg::export 1 [list source [file join $dir pt_peg_export.tcl]] Index: modules/pt/pt_peg_op.man ================================================================== --- modules/pt/pt_peg_op.man +++ modules/pt/pt_peg_op.man @@ -1,10 +1,11 @@ [comment {-*- text -*- doctools manpage}] -[manpage_begin pt_peg_op i 1.0.1] +[vset VERSION 1.0.2] +[manpage_begin pt_peg_op i [vset VERSION]] [include include/module.inc] [titledesc {Parser Tools PE Grammar Utility Operations}] -[require pt::peg::op 1.0.1] +[require pt::peg::op [opt [vset VERSION]]] [description] [include include/ref_intro.inc] This package provides a number of utility commands manipulating a PE grammar (container) in various ways. Index: modules/pt/pt_peg_op.tcl ================================================================== --- modules/pt/pt_peg_op.tcl +++ modules/pt/pt_peg_op.tcl @@ -137,19 +137,19 @@ # calls = array (x -> called-by-x) # caller = array (x -> users-of-x) set changed [$container nonterminals] while {[llength $changed]} { -puts <$changed> + #puts <$changed> set scan $changed set changed {} foreach sym $scan { # Rule 1 if {![llength $calls($sym)] && ($mode($sym) eq "value")} { -puts (1)$sym + #puts (1)$sym set mode($sym) leaf } # Rule 2 set callmode [CallMode $caller($sym) mode] @@ -188,14 +188,14 @@ # # ## ### ##### ######## ############# proc ::pt::peg::op::minimize {container} { flatten $container - drop unreachable $container drop unrealizable $container + drop unreachable $container flatten $container - optmodes $container + modeopt $container dechain $container return } # # ## ### ##### ######## ############# @@ -302,19 +302,19 @@ # unrealizable children when we drop unrealizable symbols # from a grammar. return [tcl::mathfunc::max {*}$arguments] } - x - * - + - ? - & - ! { + x - + - & - ! { # All other operators are realizable if and only if all # its children are realizable. return [tcl::mathfunc::min {*}$arguments] } default { - # The terminals and special forms are realizable by - # definition. + # Terminals, special forms, Kleene closure (*), and + # optionals (?) are realizable by definition. return 1 } } } @@ -371,7 +371,7 @@ namespace eval ::pt::peg::op {} # # ## ### ##### ######## ############# ##################### ## Ready -package provide pt::peg::op 1.0.1 +package provide pt::peg::op 1.0.2 return ADDED modules/pt/pt_peg_op.test Index: modules/pt/pt_peg_op.test ================================================================== --- /dev/null +++ modules/pt/pt_peg_op.test @@ -0,0 +1,49 @@ +# -*- tcl -*- +# pe_peg_op.test: tests for the pt::peg::op package. +# +# Copyright (c) 2018 by Stefan Sobernig +# All rights reserved. +# + +# ------------------------------------------------------------------------- + +source [file join \ + [file dirname [file dirname [file join [pwd] [info script]]]] \ + devtools testutilities.tcl] + +testsNeedTcl 8.5 +testsNeedTcltest 2.0 + +support { + useAccel [useTcllibC] struct/sets.tcl struct::set + TestAccelInit struct::set + + use fileutil/fileutil.tcl fileutil ; # For tests/common + use snit/snit.tcl snit + + use pt/pt_pegrammar.tcl pt::peg + use pt/pt_peg_container.tcl pt::peg::container + use pt/pt_pexpr_op.tcl pt::pe::op + + source [localPath tests/common] +} +testing { + useLocal pt_peg_op.tcl pt::peg::op +} + +# ------------------------------------------------------------------------- + +set mytestdir tests/data + +# ------------------------------------------------------------------------- + +TestAccelDo struct::set setimpl { + source [localPath tests/pt_peg_op.tests] +} + +#---------------------------------------------------------------------- + +unset mytestdir +TestAccelExit struct::set +testsuiteCleanup +return Index: modules/pt/pt_pexpr_op.tcl ================================================================== --- modules/pt/pt_pexpr_op.tcl +++ modules/pt/pt_pexpr_op.tcl @@ -63,34 +63,30 @@ proc ::pt::pe::op::Drop {dropset pe op arguments} { if {$op eq "n"} { lassign $arguments symbol if {[struct::set contains $dropset $symbol]} { - return @@ - } else { - return $pe - } - } - - switch -exact -- $op { - / - x - * - + - ? - & - ! { - set newarg {} - foreach a $arguments { - if {$a eq "@@"} continue - lappend newarg $a - } - - if {![llength $newarg]} { - # Nothing remained, drop the whole expression - return [pt::pe epsilon] - } elseif {[llength $newarg] < [llength $argument]} { - # Some removed, construct a new expression + set pe @@ + } + } elseif {$op in {/ x * + ? & !}} { + set newarg {} + foreach a $arguments { + if {$a eq "@@"} continue + lappend newarg $a + } + if {![llength $newarg]} { + # Nothing remained, drop the whole expression + set pe [pt::pe epsilon] + } elseif {[llength $newarg] < [llength $arguments]} { + # Some removed, construct a new expression + if {$op eq "/"} { set pe [list $op {*}$newarg] - } ; # None removed, no change. - } + } else { + set pe @@ + } + } ; # None removed, no change. } - return $pe } proc ::pt::pe::op::Rename {nt ntnew pe op arguments} { #puts R($op)/$arguments/ ADDED modules/pt/tests/pt_peg_op.tests Index: modules/pt/tests/pt_peg_op.tests ================================================================== --- /dev/null +++ modules/pt/tests/pt_peg_op.tests @@ -0,0 +1,244 @@ +# -*- tcl -*- +# Testsuite for pt::peg::op. + +# [ok] drop unreachable +# [ok] drop unrealizable +# [ok] flatten +# [ok] minimize + +# TODO +# [..] called +# [..] dechain +# [..] modeopt +# [..] reachable +# [..] realizable + +# ------------------------------------------------------------------------- +# Basic syntax + +foreach op { + called + dechain + flatten + minimize + modeopt + reachable + realizable + {drop unreachable} + {drop unrealizable} +} { + test pt-peg-op-set:${setimpl}-${op}-0.0 "$op, wrong#args, not enough" -body { + pt::peg::op {*}$op + } -returnCodes error -result "wrong # args: should be \"pt::peg::op $op container\"" + + test pt-peg-op-set:${setimpl}-${op}-0.1 "$op, wrong#args, too many" -body { + pt::peg::op {*}$op Container X + } -returnCodes error -result "wrong # args: should be \"pt::peg::op $op container\"" +} + +# ------------------------------------------------------------------------- +# General support for testing transforms + +proc sl {v} { + # Remove comment lines + regsub -all -line {^\s*#.*$} $v {} +} + +proc g {s r} { + # quick constructor of a grammar value + return [list pt::grammar::peg [list rules $r start $s]] +} + +proc TestTransformation {op data setImpl} { + # Convert operation and data table into series of test cases + set debug 0 + # Note, the `op` changes the container (here ::In) in-place. + append bodyScript [list {*}::pt::peg::op::$op ::In] \; + if {$debug} { + append bodyScript "puts stderr \[::In serialize\]" \; + append bodyScript "puts stderr \[::Expected serialize\]" \; + } + # After the op, when all is well, the content of ::In should be + # the same as ::Expected. + append bodyScript "pt::peg equal \[::In serialize\] \[::Expected serialize\]" \; + set n 1 + foreach {inStart inRulesSet outStart outRulesSet} [sl $data] { + set testLabel "pt-peg-op-set:${setImpl}-[join $op -]-$n" + if {$debug} { + puts stderr >>>>$testLabel<<<< + } + test $testLabel "OP '$op' vs. expected" -setup { + pt::peg::container ::In deserialize [g $inStart $inRulesSet] + pt::peg::container ::Expected deserialize [g $outStart $outRulesSet] + } -body $bodyScript -result 1 -cleanup { + ::In destroy + ::Expected destroy + } + incr n + } +} + +# ------------------------------------------------------------------------- +# op: flatten + +TestTransformation flatten { + # --- stays as-is #1 + epsilon {} + epsilon {} + # --- stays as-is #2 + {n S} { + S {is {n A} mode value} + A {is {t a} mode value} + } + {n S} { + S {is {n A} mode value} + A {is {t a} mode value} + } + # --- flatten start expr and rules: single-element sequences + {x {n S}} { + S {is {x {n A}} mode value} + A {is {n A} mode value} + } + {n S} { + S {is {n A} mode value} + A {is {n A} mode value} + } + # --- flatten start expr and rules: single-element choices + {/ {n S}} { + S {is {/ {n A}} mode value} + A {is {n A} mode value} + } + {n S} { + S {is {n A} mode value} + A {is {n A} mode value} + } + # --- flatten start expr and rules: nested sequences + {x {n S}} { + S {is {x {n A} {x {n A} {n A}}} mode value} + A {is {n A} mode value} + } + {n S} { + S {is {x {n A} {n A} {n A}} mode value} + A {is {n A} mode value} + } + # --- flatten start expr and rules: nested choices + {x {n S}} { + S {is {/ {n A} {/ {n A} {n A}}} mode value} + A {is {n A} mode value} + } + {n S} { + S {is {/ {n A} {n A} {n A}} mode value} + A {is {n A} mode value} + } +} $setimpl + +# ------------------------------------------------------------------------- +# op: drop unrealizable + +TestTransformation "drop unrealizable" { + # (1) stays as-is + epsilon {} + epsilon {} + # (2) S <-- X; X <-- X; => epsilon + {n S} { + S {is {n X} mode value} + X {is {n X} mode value} + } + epsilon {} + # (3) S <-- X?; X <-- X; => S <-- epsilon + {n S} { + S {is {? {n X}} mode value} + X {is {n X} mode value} + } + {n S} { + S {is epsilon mode value} + } + # (4) S <-- X*; X <-- X; => S <-- epsilon + {n S} { + S {is {* {n X}} mode value} + X {is {n X} mode value} + } + {n S} { + S {is epsilon mode value} + } + # (5) S <-- X 'y'; X <-- X; => epsilon + {n S} { + S {is {x {n X} {t y}} mode value} + X {is {n X} mode value} + } + epsilon {} + # (6) S <-- X / 'y'; X <-- X; => S <-- 'y' (unflattened!) + {n S} { + S {is {/ {n X} {t y}} mode value} + X {is {n X} mode value} + } + {n S} { + S {is {/ {t y}} mode value} + } +} $setimpl + +# ------------------------------------------------------------------------- +# op: drop unrealizable + +TestTransformation "drop unreachable" { + # (1) stays as-is + epsilon {} + epsilon {} + # S <-- a; A <-- a ==> S <-- a (A not reachable, dropped) + {n S} { + S {is {t a} mode leaf} + A {is {t a} mode void} + } + {n S} { + S {is {t a} mode leaf} + } + # S <-- a; A <-- B; B <-- a ==> A, B unreachable, dropped + {n S} { + S {is {t a} mode leaf} + A {is {n B} mode void} + B {is {t a} mode void} + } + {n S} { + S {is {t a} mode leaf} + } +} $setimpl + +# ------------------------------------------------------------------------- +# op: minimize + +TestTransformation minimize { + # --- stays as-is + epsilon {} + epsilon {} + # --- minimize away (unrealizable) + # S <-- A; A <-- A + {n S} { + S {is {n A} mode value} + A {is {n A} mode value} + } + epsilon {} + # --- already minimal + {n S} { + S {is {n A} mode leaf} + A {is {t a} mode void} + } + {n S} { + S {is {n A} mode leaf} + A {is {t a} mode void} + } + # --- drop unrealizable *before* unreachable + # S <-- AB / a; A <-- aA; B <-- a + {n S} { + S {is {/ {x {n A} {n B}} {t a}} mode value} + A {is {x {t a} {n A}} mode value} + B {is {t a} mode leaf} + } + {n S} { + S {is {t a} mode leaf} + } +} $setimpl + +# ------------------------------------------------------------------------- +rename sl {} +rename g {} +rename TestTransformation {}