ExpressionIterator(grammar::Grammar, max_depth::Int, sym::Symbol)

An iterator over all possible expressions of a grammar up to max_depth with start symbol sym.

Grammar

Represents a grammar and its production rules. Use the @grammar macro to create a Grammar object.

Interpreter.SymbolTable(grammar::Grammar, mod::Module=Main)

Returns a symbol table populated with mapping from symbols in grammar to symbols in module mod or Main, if defined.

NodeLoc

A helper struct that points to a node in the tree via its parent such that the child can be easily swapped out. If i is 0 the node pointed to is the root node and parent is the node itself.

Use a circular buffer to contain used RuleNodes to be recycled. First check the recycle bin to see if there are available RuleNodes, if not allocated a new one. This helps minimize memory allocations and improves performance

RuleNode

Type for representing nodes in an expression tree.

append!(grammar1::Grammar, grammar2::Grammar)

Appends the production rules of grammar2 to grammar1.

get(root::RuleNode, loc::NodeLoc)

Obtain the node pointed to by loc.

insert!(loc::NodeLoc, rulenode::RuleNode)

Replaces the subtree pointed to by loc with the given rulenode.

Return the number of vertices in the tree rooted at root.

rand(::Type{RuleNode}, grammar::Grammar, typ::Symbol, dmap::AbstractVector{Int}, max_depth::Int=10)

Generates a random RuleNode of return type typ and maximum depth max_depth guided by a minimum depth map dmap.

rand(::Type{RuleNode}, grammar::Grammar, typ::Symbol, max_depth::Int=10)

Generates a random RuleNode of return type typ and maximum depth max_depth.

Core.eval(tab::SymbolTable, ex::Expr)

Evaluate the expression ex using symbol table tab

Core.eval(rulenode::RuleNode, grammar::Grammar)

Evaluate the expression tree with root rulenode.

child_types(grammar::Grammar, rule_index::Int)

Returns the types of the children (nonterminals) of the production rule at rule_index.

child_types(grammar::Grammar, node::RuleNode)

Returns the list of child types in the production rule used by node.

contains_returntype(node::RuleNode, grammar::Grammar, sym::Symbol, maxdepth::Int=typemax(Int))

Returns true if the tree rooted at node contains at least one node at depth less than maxdepth with the given return type.

count_expressions(iter::ExpressionIterator)

Count the number of possible expressions in the expression iterator.

count_expressions(grammar::Grammar, max_depth::Int, sym::Symbol)

Count the number of possible expressions of a grammar up to max_depth with start symbol sym.

depth(root::RuleNode)

Return the depth of the expression tree rooted at root.

get_childtypes(rule::Any, types::AbstractVector{Symbol})

Returns the child types of a production rule.

get_executable(rulenode::RuleNode, grammar::Grammar)

Returns the executable julia expression represented in the expression tree with root rulenode. The returned expression can be evaluated using eval().

iseval(rule::Any)

Returns true if the rule is the special evaluate immediately function, i.e., _()

iseval(grammar::Grammar, rule_index::Int)

Returns true if the production rule at rule_index contains the special _() eval function.

iseval(grammar::Grammar)

Returns true if any production rules in grammar contain the special _() eval function.

isterminal(rule::Any, types::AbstractVector{Symbol})

Returns true if the rule is terminal, ie does not contain any of the types in the provided vector. For example, :(x) is terminal, and :(1+1) is terminal, but :(Real + Real) is typically not.

isterminal(grammar::Grammar, rule_index::Int)

Returns true if the production rule at rule_index is terminal, i.e., does not contain any nonterminal symbols.

isterminal(grammar::Grammar, node::RuleNode)

Returns true if the production rule used by node is terminal, i.e., does not contain any nonterminal symbols.

max_arity(grammar::Grammar)

Returns the maximum arity (number of children) over all production rules in the grammar.

mindepth(grammar::Grammar, typ::Symbol, dmap::AbstractVector{Int})

Returns the minimum depth achievable for a given nonterminal symbol

mindepth_map(grammar::Grammar)

Returns the minimum depth achievable for each production rule, dmap.

nchildren(grammar::Grammar, rule_index::Int)

Returns the number of children (nonterminals) of the production rule at rule_index.

nchildren(grammar::Grammar, node::RuleNode)

Returns the number of children in the production rule used by node.

node_depth(root::RuleNode, node::RuleNode)

Return the depth of node for an expression tree rooted at root. Depth is 1 when root == node.

nonterminals(grammar::Grammar)

Returns a list of nonterminals in the grammar.

return_type(grammar::Grammar, rule_index::Int)

Returns the type of the production rule at rule_index.

return_types(grammar::Grammar, node::RuleNode)

Returns the return type in the production rule used by node.

root_node_loc(root::RuleNode)

Returns a NodeLoc pointing to the root node.

sample(root::RuleNode, typ::Symbol, grammar::Grammar, maxdepth::Int=typemax(Int))

Selects a uniformly random node from the tree, limited to maxdepth.

sample(root::RuleNode, typ::Symbol, grammar::Grammar,
                      maxdepth::Int=typemax(Int))

Selects a uniformly random node of the given return type, typ, limited to maxdepth.

sample(::Type{NodeLoc}, root::RuleNode, maxdepth::Int=typemax(Int))

Selects a uniformly random node in the tree no deeper than maxdepth using reservoir sampling. Returns a NodeLoc that specifies the location using its parent so that the subtree can be replaced.

sample(::Type{NodeLoc}, root::RuleNode, typ::Symbol, grammar::Grammar)

Selects a uniformly random node in the tree of a given type, specified using its parent such that the subtree can be replaced. Returns a NodeLoc.

@grammar

Define a grammar and return it as a Grammar. For example:

grammar = @grammar begin
    R = x
    R = 1 | 2
    R = R + R
end

Evaluates an expression without compiling it. Uses AST and symbol lookups. Only supports :call and :(=) expressions at the moment. Example: tab = SymbolTable(:f => f, :x => x) ex = :(f(x)) interpret(tab, ex)