Does there exist an extension of regular expressions that captures the context free languages? In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:


  $S \to a a S b$
  $S \to $


generates $\{ a^{2i} b^i | i \geq 0\}$,


  $S \to a S b$
  $S \to a a S b$
  $S \to $


generates $\{ a^i b^j \mid i \geq j \geq 0 \}$, and


  $S \to a S a$
  $S \to b S b$
  $S \to $


generates $\{ w w^R \mid w \in (a|b)^* \}$, or equivalently $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (where $p_1$ refers to the part captured by $(...)_1$).

The above examples can all be generated by adding indices ($a^i$), simple constraints on these indices ($i &gt; j$) and pattern matching to regular expressions. This makes me wonder whether all context-free languages can be generated by some extension of the regular expressions.


  Is there an extension of regular expressions that can generate all of or some significant subset of the context free languages?
Yes, there is. Define a context-free expression to be a term generated
by the following grammar:

$$
\begin{array}{lcll}
g &amp; ::= &amp; \epsilon &amp; \mbox{Empty string}\\ 
  &amp;  |  &amp; c        &amp; \mbox{Character $c$ in alphabet $\Sigma$} \\ 
  &amp;  |  &amp; g \cdot g &amp; \mbox{Concatenation} \\ 
  &amp;  |  &amp; \bot      &amp; \mbox{Failing pattern} \\  
  &amp;  |  &amp; g \vee g  &amp; \mbox{Disjunction}\\
  &amp;  |  &amp; \mu \alpha.\; g &amp; \mbox{Recursive grammar expression} \\
  &amp;  |  &amp; \alpha    &amp; \mbox{Variable expression}
\end{array}
$$

This is all of the constructors for regular languages except Kleene
star, which is replaced by a general fixed-point operator $\mu
\alpha.\;g$, and a variable reference mechanism. (The Kleene star is
not needed, since it can be defined as $g\ast \triangleq \mu
\alpha.\;\epsilon \vee g\cdot\alpha$.)

The interpretation of a context-free expression requires accounting
for the interpretation of free variables. So define an environment
$\rho$ to be a map from variables to languages (i.e., subsets of
$\Sigma^*$), and let $[\rho|\alpha:L]$ be the function that behaves
like $\rho$ on all inputs except $\alpha$, and which returns the
language $L$ for $\alpha$.

Now, define the interpretation of a context-free expression as follows:

$$
\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}}
\newcommand{\setof}[1]{\left\{#1\right\}}
\newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}}
\begin{array}{lcl}
\interp{\epsilon}{\rho} &amp; = &amp; \setof{\epsilon} \\ 
\interp{c}{\rho}        &amp; = &amp; \setof{c} \\ 
\interp{g_1\cdot g_2}{\rho} &amp; = &amp; \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\ 
\interp{\bot}{\rho} &amp; = &amp; \emptyset \\ 
\interp{g_1 \vee g_2}{\rho} &amp; = &amp; \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\ 
\interp{\alpha}{\rho} &amp; = &amp; \rho(\alpha) \\ 
\interp{\mu \alpha.\; g}{\rho} &amp; = &amp; \bigcup_{n \in \mathbb{N}} L_n \\ 
\mbox{where} &amp; &amp; \\ 
L_0 &amp; = &amp; \emptyset \\ 
L_{n+1} &amp; = &amp; L_n \cup \interp{g}{[\rho|\alpha:L_n]}
\end{array}
$$

Using the Knaster-Tarski theorem, it's easy to see that the
interpretation of $\mu \alpha.g$ is the least fixed of the expression.

It's straightforward (albeit not entirely trivial) to show that you
can give a context-free expression deriving the same language as any
context-free grammar, and vice-versa. The non-triviality arises from
the fact that context-free expressions have nested fixed points, and
context-free grammars give you a single fixed point over a tuple. This 
requires the use of Bekic's lemma, which says precisely that a nested 
fixed points can be converted to a single fixed point over a product (and
vice-versa). But that's the only subtlety. 

EDIT: No, I don't know a standard reference for this: I worked it out
for my own interest. However, it's an obvious enough construction that
I'm confident it's been invented before. Some casual Googling reveals
Joost Winter, Marcello Bonsangue and Jan Rutten's recent paper
Context-Free Languages, Coalgebraically, where they give a variant
of this definition (requiring all fixed points to be guarded) which
they also call context-free expressions.