say, we add the option of allowing let expressions to context free grammars:

let defines a variable that defines an expression from a specific Symbol of the grammar, and every instance of the variable has to be the exact same expression


T := (let ((z -> U) z + z)
U := x | y | Const | U +U | U ∗U | T

In the above example, T:= U + U, except that the two occurrences of U have to be identical.

So, this grammar only allows expressions which are a sum of 2 identical expressions.

I think this grammar is strictly more powerful than context free grammar, but can anyone tell me if they are equivalent to any other known type of grammar.

  • 1
    $\begingroup$ Oops, sorry. Misread the site. So, formally speaking, what is Int in your example? Also, you might want to take a glance at en.m.wikipedia.org/wiki/Van_Wijngaarden_grammar $\endgroup$ – rici Apr 7 '17 at 16:03
  • 1
    $\begingroup$ By the way, your T with U := {a,b}* proves that your model is strictly more powerful than CFL. It's probably not equivalent to CSL, though. So it falls in the class of "mildly context-sensitive" models, of which there are many. I suggest you start with that list and a Google Scholar query. $\endgroup$ – Raphael Apr 7 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.