# cfg#

A context free grammar is a formal grammar where the rules all have a codomain of length 1.

## Summary#

 `Tree` A tree is a rule for the `root` and a list of trees called `branches`. `Rule` A rule is a generator of free operads, given by an atomic type `dom`, a type `cod` of arbitrary length and an optional `name`. `Word` A word is a leaf in a context-free tree. `Id` The identity is a rule that does nothing. `Operad` An operad is a category with a method `__call__` which constructs a tree from a root and a list of branches. `Algebra` An algebra is a functor with the free operad as domain and a given operad as codomain.

## Axioms#

The axioms of multicategories (aka operads) hold on the nose.

```>>> x, y = Ty('x'), Ty('y')
>>> f, g = Rule(x @ x, x, name='f'), Rule(x @ y, x, name='g')
>>> h = Rule(y @ x, x, name='h')
>>> assert f(g, h) == Tree(f, *[g, h])
```
```>>> assert Id(x)(f) == f == f(Id(x), Id(x))
>>> left = f(Id(x), h)(g, Id(x), Id(x))
>>> right = f(g, Id(x))(Id(x), Id(x), h)
>>> assert f(g, h) == left == right
```