(prune-grammar grammar {:keys [wtrek start removed] :as ctx})
Takes a grammar and returns a pruned grammar based on keys specified in the options map. Three different prune operations are performed:
Takes a grammar and returns a pruned grammar based on keys specified in the options map. Three different prune operations are performed: - Removes rules listed in :removed - Prune rule bodies/productions based on :wtrek - If :start is specified in the options or is on the meta of the grammar, then rules are removed that cannot be reached (directly or indirectly) from the start rule/production..
(prune-node* node wtrek cur-path)
Internal: Used by prune-node* to prune rule bodies/productions based on :wtrek
Internal: Used by prune-node* to prune rule bodies/productions based on :wtrek
(reduce-wtrek grammar
wtrek
&
[{:keys [reduced-subset reduce-mode reducer-fn]
:or {reduce-mode :zero reducer-fn reducer-zero}
:as opts}])
Takes a grammar and wtrek and returns a new reduced wtrek with weights reduced/propagated according to reduce-mode.
If the optional reduced-subset is then only those node will be propagated. If reduced-subset is not specified then all reducible/weighted nodes will be considered. The former may result in a wtrek that is not fully reduced but the latter can take a while for large grammars/wtreks.
The way that weights are reduced/propagated depends on reduce-mode:
:zero "If all siblings are zero, reduce parent edge to zero."
:max-child: "If all siblings of a node have a weight that is less than parent weight then reduce the parent to the largest sibling weight."
Algorithm/psuedocode:
- pend <= reduced-subset OR all weighted nodes in the tree
- while pend:
- node <= pop(pend)
- mcw <= get max child weight
- pnodes <= parents(node)
- foreach pnode of pnodes:
- if pnode child weight towards node > mcw
- then:
- push(pend, pnode)
- wtrek[pnode] <= mcw
:reducer: "When all siblings are zero, reduce parent by reducer function and distribute the removed weights to valid (no removed descendant) children."
Algorithm/psuedocode:
- pend <= reduced-subset OR all weighted nodes in the tree
- while pend:
- node <= pop(pend)
- if all node's children are 0:
- reduce node's parents w/ reducer function, accumulate the
total amount that was reduced
- if all node's parent's direct children are 0, add node's
parent to pend
- for each of node's children with no removed descendants:
- distribute accumulated weight evenly among those
children (rounding up unless all parents are 0 in which
case use 0)
Any zero weights in the :wtrek map represent a node edge that has been removed. If all edges of a node are 0 then this is represents a node that has been removed. The normal algorithm will propagate this correctly. However, if the propagation of 0 weights reaches the root/start of the grammar and cannot propagate further then an exception is thrown because this represents an invalid weighted grammar; grammar productions could reach the removed node from the root/start rule (a removed node does not even exist in the sense that epsilon does).
The propagation of node removals continues until there are no more pending node to remove. The call to parent-search may add more nodes to be removed but already removed nodes will not be added again so the process will eventually terminate.
Takes a grammar and wtrek and returns a new reduced wtrek with weights reduced/propagated according to reduce-mode. If the optional reduced-subset is then only those node will be propagated. If reduced-subset is not specified then all reducible/weighted nodes will be considered. The former may result in a wtrek that is not fully reduced but the latter can take a while for large grammars/wtreks. The way that weights are reduced/propagated depends on reduce-mode: :zero "If all siblings are zero, reduce parent edge to zero." :max-child: "If all siblings of a node have a weight that is less than parent weight then reduce the parent to the largest sibling weight." Algorithm/psuedocode: - pend <= reduced-subset OR all weighted nodes in the tree - while pend: - node <= pop(pend) - mcw <= get max child weight - pnodes <= parents(node) - foreach pnode of pnodes: - if pnode child weight towards node > mcw - then: - push(pend, pnode) - wtrek[pnode] <= mcw :reducer: "When all siblings are zero, reduce parent by reducer function and distribute the removed weights to valid (no removed descendant) children." Algorithm/psuedocode: - pend <= reduced-subset OR all weighted nodes in the tree - while pend: - node <= pop(pend) - if all node's children are 0: - reduce node's parents w/ reducer function, accumulate the total amount that was reduced - if all node's parent's direct children are 0, add node's parent to pend - for each of node's children with no removed descendants: - distribute accumulated weight evenly among those children (rounding up unless all parents are 0 in which case use 0) Any zero weights in the :wtrek map represent a node edge that has been removed. If all edges of a node are 0 then this is represents a node that has been removed. The normal algorithm will propagate this correctly. However, if the propagation of 0 weights reaches the root/start of the grammar and cannot propagate further then an exception is thrown because this represents an invalid weighted grammar; grammar productions could reach the removed node from the root/start rule (a removed node does not even exist in the sense that epsilon does). The propagation of node removals continues until there are no more pending node to remove. The call to parent-search may add more nodes to be removed but already removed nodes will not be added again so the process will eventually terminate.
(reduce-wtrek-with-weights grammar
wtrek
weights-to-reduce
&
[{:keys [reduce-mode reducer-fn pick-mode pick-pred]
:or {reduce-mode :zero
reducer-fn reducer-half
pick-mode :weight-dist
pick-pred identity}
:as opts}])
Takes a grammar, wtrek, a weights-to-reduce map, a reduce-mode keyword, and a reducer-fn. A path from weights-to-reduce is selected based on pick-mode. For that path the reducer-fn is called with the weight for the path from wtrek and the weight for the path from weights-to-reduce. Based on those two values the reducer-fn should return a new value to be updated in the wtrek.
pick-mode values: :weight - randomly pick a node weighted by node weights. :dist - randomly pick a node weighted by node distances from the start node :weight-dist - randomly pick a node weighted by node weights multiplied by node distances from the start node.
The resulting wtrek will then be passed to the reduce-wtrek function to propogate the weight reduction according reduce-mode.
Takes a grammar, wtrek, a weights-to-reduce map, a reduce-mode keyword, and a reducer-fn. A path from weights-to-reduce is selected based on pick-mode. For that path the reducer-fn is called with the weight for the path from wtrek and the weight for the path from weights-to-reduce. Based on those two values the reducer-fn should return a new value to be updated in the wtrek. pick-mode values: :weight - randomly pick a node weighted by node weights. :dist - randomly pick a node weighted by node distances from the start node :weight-dist - randomly pick a node weighted by node weights multiplied by node distances from the start node. The resulting wtrek will then be passed to the reduce-wtrek function to propogate the weight reduction according reduce-mode.
(reducer-div divisor start-weight parsed-weight)
If parsed-weight > 0 then returns the next weight in seq-ladder that is lower than start-weight.Designed to be used as a partial like this: (partial reducer-div 2)
If parsed-weight > 0 then returns the next weight in seq-ladder that is lower than start-weight.Designed to be used as a partial like this: (partial reducer-div 2)
(reducer-half start-weight parsed-weight)
If parsed-weight > 0 then returns start-weight divided in two and rounded down.
If parsed-weight > 0 then returns start-weight divided in two and rounded down.
(reducer-ladder seq-ladder start-weight parsed-weight)
If parsed-weight > 0 then returns the next weight in seq-ladder that is lower than start-weight. Designed to be used as a partial like this: (partial reducer-ladder [30 10 3 1]) The values in the ladder will be sorted in descending order and an implicit zero is added to the end.
If parsed-weight > 0 then returns the next weight in seq-ladder that is lower than start-weight. Designed to be used as a partial like this: (partial reducer-ladder [30 10 3 1]) The values in the ladder will be sorted in descending order and an implicit zero is added to the end.
(reducer-zero start-weight parsed-weight)
If parsed-weight > 0 then returns 0
If parsed-weight > 0 then returns 0
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close