module analysis::grammars::dramb::Termination
Usage
import analysis::grammars::dramb::Termination;
Source code
http://github.com/cwi-swat/drambiguity/blob/main/src/analysis/grammars/dramb/Termination.rsc
Dependencies
import Grammar;
import ParseTree;
import analysis::grammars::dramb::Util;
import analysis::grammars::Dependency;
import Set;
data Production
data Production (int weight=0)
function terminationWeights
Annotate grammar rules in a grammar with stochastic information.
Grammar terminationWeights(Grammar g)
If a grammar is used to generate random trees then recursion will quickly lead to very deep trees that almost always produce StackOverflow exceptions.
To counter this, this analysis annotates a grammar. Every rule is given a "weight" that will determine its likelihood to be randomly selected with respect to its alternatives.
To make sure random tree generation terminates often (almost always), we distinguish between recursive rules and non-recursive rules via grammar analysis. For every non-terminal, the group of non-recursive alternatives is always given at least 50% of the total weight.
Consider an expression grammar, there are usually only a few of those "terminating"
rules (Id, Number) and all the others are recursive (e+e, e*e, e[e]).
After this grammar transformation, any algorithm that can generate trees randomly can make use of these weights. The distribution of weight within a group of alternatives is uniform.
function dependencies
Extracts which non-terminal depends on which others.
rel[Symbol,Symbol] dependencies(map[Symbol, Production] gr)