Are grammars programs? That is, are languages for grammar specification programming languages?


Motivation for the question is follows:

  1. To know whether languages for grammars are programming languages.
  2. Desire to know what words I use mean. Since no precise definition of term "programming language" exists we may bring it close to being by figuring out answers for such a tricky questions.
  3. Which programs can and which can't be written as grammars? (idea by Rehno Lindeque)


Observation that caused a question was:

  • Language of grammars has executable semantics like a programming language: every grammar relates input to output (sequence of characters of given alphabet to boolean or AST, depends on implementation), deterministically or not. For example, grammars written in PEG are deterministic "programs" while in BNF are not. CFGs are not Turing complete while unrestricted grammars are.
  • Grammar can be designed to carry out a computation on a computer -- actually a parser.
  • 4
    $\begingroup$ My explanation of my downvote was almost as long as your entire question. :) $\endgroup$ May 6, 2011 at 14:11
  • 2
    $\begingroup$ A downvote simply means "This question is unclear or not useful", and this is exactly what I thought here. The question in the current form does not seem to make any sense – even worse, I actually spent some time trying to figure out what you might mean with the question, double-checking the usual definitions of formal grammars and programming languages, and even after that it did not seem to make any sense. I believe that there is a very good reason for you to ask the question, but you have not revealed it. Why do you think that grammars might be programming languages? $\endgroup$ May 6, 2011 at 14:35
  • 2
    $\begingroup$ One of the aspects of asking a good question is motivation. Your motivation appears to be "how do we define programming languages", and personally that motivation is not compelling. I didn't actually vote to close since I'm a moderator and it would be binding, but as a community member that's my opinion. $\endgroup$ May 6, 2011 at 15:38
  • 3
    $\begingroup$ The reason the question should be closed is because it is not at the level of research-level theoretical computer science. $\endgroup$ May 6, 2011 at 16:37
  • 5
    $\begingroup$ David Barbour wrote up some ideas about Generative Grammar-based Computation on Lambda the Ultimate. I think the idea behind this, namely that describing grammars is programming and how far can this idea go, is a good theory B question, and deserves to be reopened. $\endgroup$ May 7, 2011 at 7:48


Browse other questions tagged or ask your own question.