RERE.CFG

Context free grammars, where each production is a regular-expression.

Context-free grammars

type CFG n a = Vec n (CFGBase n a)

Context-free grammar represented as n equations of RE (CFGBase) with n variables.

type CFGBase n a = RE (Either (Fin n) a)

Single equation in context-free-grammar equation.

Conversion to recursive regular expressions

cfgToRE :: (SNatI n, Ord a) => Vec (S n) Name -> CFG (S n) a -> RE a

Convert CFG (with names for productions) into RE. Note: the start symbol have to be last equation.

>>> let a = Eps \/ ch_ 'a' <> Var (Left FZ)
>>> let b = Eps \/ ch_ 'b' <> Var (Left (FS FZ))
>>> let cfg = b ::: a ::: VNil

[ begin{aligned} {mathit{b}} &= {varepsilon}cupmathtt{b}{mathit{a}} -- {mathit{a}} &= {varepsilon}cupmathtt{a}{mathit{b}} -- end{aligned}