This is the base package to support the generation and optimization of Julia expressions from a grammar. The package contains many basic functions for declaring and working with grammars and expression trees.

```
Pkg.add("ExprRules")
```

Once it's installed, start using the package by calling:

In [1]:

```
using ExprRules
```

Grammars are specified by production rules that specify substitutions of non-terminal symbols. Each production rule is an equality with a non-terminal on the left side and a Julia expression on the right side.

The _() syntax is a special function where the argument is evaluated at the time of derivation tree's construction and the value is held constant throughout the life of the tree. The pipe (|) syntax is a short-hand that allows the user to define multiple production rules on a single line (i.e., Backus-Naur Form). The |() syntax is another similar short-hand that takes a collection as argument and creates a production rule for each element in the collection.

In [2]:

```
grammar = @grammar begin
Real = x # symbol
Real = Real * Real # julia expression
Real = f(Real) # function call
Real = _(Base.rand(1.0:5.0)) # special syntax, eval argument of _() at derivation time
Real = A | B | cos(Real) # multiple rules on a single line
Real = 1 | 2 | 3
Real = |(4:6) # same as Real = 4 | 5 | 6
Real = |([7,8,9]) # same as Real = 7 | 8 | 9
end
```

Out[2]:

In [3]:

```
f(x) = 2x
```

Out[3]:

List non-terminals of the grammar:

In [4]:

```
nonterminals(grammar)
```

Out[4]:

Grammars are indexed by non-terminal symbols and return the corresponding production rule numbers with that nonterminal.

In [5]:

```
grammar[:Real]
```

Out[5]:

Get the return type of the first production rule:

In [6]:

```
return_type(grammar, 1)
```

Out[6]:

Get the number of children of the second production rule:

In [7]:

```
nchildren(grammar, 2)
```

Out[7]:

Get the child types of the second production rule:

In [8]:

```
child_types(grammar, 2)
```

Out[8]:

Get the maximum number of children (arity) of the grammar:

In [9]:

```
max_arity(grammar)
```

Out[9]:

Determine if the third production rule is terminal:

In [10]:

```
isterminal(grammar, 3)
```

Out[10]:

Determine if the fourth production rule is a special _() function:

In [11]:

```
iseval(grammar, 4)
```

Out[11]:

An expression tree represents the derivation of an expression as a tree. The nodes in an expression tree contain an index to a production rule.

Define an expression tree manually:

In [ ]:

```
rulenode = RuleNode(3, [RuleNode(6)])
display(rulenode, grammar)
```

Generate a random expression tree from the grammar:

In [ ]:

```
using Random
```

In [ ]:

```
Random.seed!(138)
rulenode = rand(RuleNode, grammar, :Real, 10)
display(rulenode, grammar)
```

Evaluate the expression defined by the expression tree:

In [ ]:

```
x=0.5
Core.eval(rulenode, grammar)
```

Get the executable Julia expression from an expression tree:

In [ ]:

```
ex = get_executable(rulenode, grammar)
```

Rather than using Julia's built-in eval function, a much more performant way of evaluating an expression is to use ExprRule's interpreter by providing a custom symbol table. SymbolTable can try to automatically populate the symbol table by analyzing the grammar. Symbols corresponding to input variables should be provided at on-the-fly. Benchmarking suggests that using the custom interpreter can yield up to 20x performance improvement.

In [ ]:

```
S = SymbolTable(grammar)
S[:x] = 5
Core.eval(S, ex)
```

Sample a random node in the tree:

In [ ]:

```
Random.seed!(0)
sample(rulenode)
```

Sample a random node of type :Real in the expression tree:

In [ ]:

```
Random.seed!(3)
sample(rulenode, :Real, grammar)
```

Sample a random node in the tree and store the location in a NodeLoc object:

In [ ]:

```
Random.seed!(1)
loc = sample(NodeLoc, rulenode)
```

Retrieve the node pointed to by the NodeLoc object:

In [ ]:

```
get(rulenode, loc)
```

Replace the subtree pointed to by loc with a randomly generated subtree:

In [ ]:

```
Random.seed!(28)
insert!(rulenode, loc, rand(RuleNode, grammar, :Real, 3))
display(rulenode, grammar)
```

Compute the minimum depth of all possible subtrees for each production rule:

In [ ]:

```
dmap = mindepth_map(grammar)
```

Compute the minimum depth of all possible subtrees starting from a given start symbol:

In [ ]:

```
mindepth(grammar, :Real, dmap) #zero for terminals
```

Iterate over all possible expressions of a grammar up to depth 2:

In [ ]:

```
grammar = @grammar begin
Real = Real + Real
Real = 1 | 2
end
iter = ExpressionIterator(grammar, 2, :Real)
collect(iter)
```

Count the number of expressions of a grammar up to depth 2:

In [ ]:

```
count_expressions(grammar, 2, :Real)
```

In [ ]:

```
using AbstractTrees
```

Print RuleNode tree in textual format. Leaf nodes are the rule numbers in the grammar.

In [ ]:

```
tree = RuleNode(1, [RuleNode(2), RuleNode(1, [RuleNode(2), RuleNode(3)])])
print_tree(tree)
```

In [ ]:

```
```