Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am resuming syntax rules for a small language:

\begin{eqnarray*} e_C &::=& \epsilon \mid constant \\ \textit{prefix-op} &::=& - \\ \textit{infix-op} &::=& + \mid - \mid * \\ e_E &::=& e_C \mid \textit{prefix-op} \; e_E \mid e_E \; \textit{infix-op} \; e_E \mid \textit{function}_E (e_{E,0}, e_{E,1},\ldots) \mid \textit{specialE} \\ e_V &::=& e_C \mid \textit{prefix-op} \; e_V \mid e_V \; \textit{infix-op} \; e_V \mid \textit{function}_V (e_{V,0}, e_{V,1}, \ldots) \mid \textit{specialV} \end{eqnarray*}

The expressions $e_E$ and $e_V$ have something common: $e_C$. Some of their operators look same: $\textit{prefix-op}$ and $\textit{infix-op}$. Their functions $\textit{function}_E$ and $\textit{function}_V$ are 2 different sets, and $\textit{specialE}$ and $\textit{specialV}$ are totally different.

I am wondering if it is still possible to present this syntax more succinct, more compact in a conventional way... Could anyone help?

share|cite|improve this question

migrated from Dec 10 '12 at 10:26

This question came from our site for theoretical computer scientists and researchers in related fields.

up vote 0 down vote accepted

Van Wijngaarden grammars are a way to handle this problem. It would be something like:

KIND : e ; v .

e KIND : e c ; prefix-op, e KIND ; e KIND, infix-op, e e; function KIND (e KIND, ",", e KIND, "," ... ) ; special KIND .

(There is no "..." in the formalism, so you'd have either to extend the grammar syntax or express it in another way).

share|cite|improve this answer

One direct way of solving this problem is to make the syntax rules parameterised, as follows:

\begin{eqnarray*} e_{X,Y} &::=& e_C \mid \textit{prefix-op} \; e_{X,Y} \mid e_{X,Y} \; \textit{infix-op} \; e_{X,Y} \mid Y (e_{X,Y}, e_{X,Y},\ldots) \mid X \\ \end{eqnarray*}

And then to set \begin{eqnarray*} e_E &::=& E_{\mathit{specialE},~\mathit{function}_E} \\ e_V &::=& E_{\mathit{specialV},~\mathit{function}_V} \\ \end{eqnarray*}

This is using notation I just invented, and it could probably be reworked, but you get the idea, I hope.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.