<p>Are grammars programs? That is, are languages for grammar specification programming languages?</p>

<p>Update.</p>

<p><strong>Motivation</strong> for the question is follows:</p>

<ol>
<li>To know whether languages for grammars are programming languages.</li>
<li>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.</li>
<li>Which programs can and which can't be written as grammars? (idea by Rehno Lindeque) </li>
</ol>

<p>Update.</p>

<p><strong>Observation</strong> that caused a question was:</p>

<ul>
<li>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.</li>
<li>Grammar can be designed to carry out a computation on a computer -- actually a parser. </li>
</ul>

CC BY-SA 3.0
2011-05-06T14:01:16.657Z
Thanks for the minus! And don't bother explaining why, I'll try to figure out it myself.
Vag
CC BY-SA 3.0
2011-05-06T14:11:58.317Z
My explanation of my downvote was almost as long as your entire question. :)
Jukka Suomela
CC BY-SA 3.0
2011-05-06T14:26:29.340Z
And what it was?
Vag
CC BY-SA 3.0
2011-05-06T14:35:05.983Z
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?
Jukka Suomela
CC BY-SA 3.0
2011-05-06T14:39:03.877Z
programming languages syntax is specified by a grammar..like any formal language. but that's not very interesting or deep at all
Sasho Nikolov
CC BY-SA 3.0
2011-05-06T14:53:11.367Z
@Jukka Suomela: Could you please give a source of your "usual definitions of programming languages" that I could check it out too?
Vag
CC BY-SA 3.0
2011-05-06T15:05:52.897Z
@Vag clearly not all languages can be specified by finite grammars. but of course programming languages will be specified by finite grammars, because they need to be parsed and also need to be used by humans. so if this is your point, it's out of scope here. the burden is on you to motivate your question and show your definitions.
Sasho Nikolov
CC BY-SA 3.0
2011-05-06T15:25:31.450Z
@Sasho Nikolov: update: description of motivation added.
Vag
CC BY-SA 3.0
2011-05-06T15:29:13.350Z
Even if there's something of merit here, the question itself is too open-ended: "trying to come up with a definition of programming language" ? I vote to close.
Suresh Venkat
CC BY-SA 3.0
2011-05-06T15:31:36.093Z
@Suresh Venkat: The question is not "what is definition of programming language" but "are grammars programming languages". It allows only two argumented anwers Yes or No, is it really "open ended"?
Vag
CC BY-SA 3.0
2011-05-06T15:38:11.153Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-05-06T15:41:56.577Z
@Suresh Venkat: Even if motivation to know what programming languages are seems disgusting to you, a question may be good in spite of bad motivation behind it, no?
Vag
CC BY-SA 3.0
2011-05-06T16:01:42.307Z
From http://en.wikipedia.org/wiki/Programming_language: A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication.
Dave Clarke
CC BY-SA 3.0
2011-05-06T16:01:49.687Z
@Vag: Please calm down.  From Wikipedia:  "A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication."  That definition supports the points of both Jukka and Sasho.  No one is out to get you.  We are asking, in different ways, what you need from this site that the first hits in a google search could not give you.
Aaron Sterling
CC BY-SA 3.0
2011-05-06T16:02:00.467Z
From http://en.wikipedia.org/wiki/Formal_grammar: A formal grammar (sometimes simply called a grammar) is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form.
Dave Clarke
CC BY-SA 3.0
2011-05-06T16:02:27.347Z
Okay Dave, I'll buy you a Coke next time I'm over that way.  Or sooner, if you're going to be at FCRC.
Aaron Sterling
CC BY-SA 3.0
2011-05-06T16:04:39.700Z
Thanks @Aaron. Nice to know there'll be a coke waiting for me.
Dave Clarke
CC BY-SA 3.0
2011-05-06T16:13:37.210Z
Then why do not just say "No" as answer and place your wikipedia argument in it? Or "Yes", whatever.
Vag
CC BY-SA 3.0
2011-05-06T16:19:51.647Z
"designed to express computations that can be performed by a machine, particularly a computer." -- design purposes must not be part of definition. "Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication." usage patterns are not part of correct definition ditto. What is the rest? "programming languages are artifical languages". Bad stated and very incomplete. So what is the answer to my question?
Vag
CC BY-SA 3.0
2011-05-06T16:32:06.167Z
No. A grammar is not a programming language. Question should be closed.
Dave Clarke
CC BY-SA 3.0
2011-05-06T16:34:54.530Z
Please explain WHY?
Vag
CC BY-SA 3.0
2011-05-06T16:37:48.440Z
The reason the question should be closed is because it is not at the level of research-level theoretical computer science.
Dave Clarke
CC BY-SA 3.0
2011-05-06T16:38:15.573Z
Oops.. Great apologies, nasty mistake in wording. I meant to say "languages for grammars specification", not grammars per se. My bad... *becomes red*
Vag
CC BY-SA 3.0
2011-05-06T16:39:43.817Z
@Vag: I guess one of the problems here is that other people don't see why a grammar would be a programming language. It is a bit like asking on a cooking site "Are eggs microwave ovens?" It is difficult to see why someone would think that eggs would be microwave ovens, and therefore difficult to try to explain why they are not microwave ovens.
Jukka Suomela
CC BY-SA 3.0
2011-05-06T16:52:08.210Z
The new version of the question now makes a lot more sense; it is no longer apples and oranges. But I do not think that it is a particularly relevant question on this site. You can certainly think that grammar specification languages are programming languages, parser generators are compilers, and parsers are computer programs. But I do not think that this is a research-level question in theoretical computer science.
Jukka Suomela
CC BY-SA 3.0
2011-05-06T17:10:11.773Z
"No. A grammar is not a programming language. Question should be closed. – @Dave Clarke. "grammar specification languages are programming languages" -- @Jukka Suomela. Not research question and no consensus on it. Excellent.
Vag
CC BY-SA 3.0
2011-05-06T19:55:16.637Z
If you wish to continue this discussion, I'd suggest meta.cstheory.stackexchange.com. I'd also suggest less snark.
Suresh Venkat
CC BY-SA 3.0
2011-05-06T20:14:03.680Z
@Suresh Venkat: "I'd also suggest less snark" Sorry for that. I take programming/CS very much to heart and get boiling too often about it. I'll try to get things easier henceforth. "
"If you wish to continue this discussion, I'd suggest meta.cstheory." Yes, I wish. How to do that?
Vag
CC BY-SA 3.0
2011-05-06T20:23:25.820Z
go to meta.cstheory (from the meta link above) and create a question
Suresh Venkat
CC BY-SA 3.0
2011-05-06T20:32:10.537Z
@Suresh Venkat: done http://meta.cstheory.stackexchange.com/questions/1137/where-simple-but-important-questions-about-terminology-may-be-asked
Vag
CC BY-SA 3.0
2011-05-06T21:12:42.540Z
@Vag, although your question is not formulated very well I think I know where you might be headed. I've come to believe that there is a interesting connection between programming languages and grammars (unrelated to the actual parsing of programming language syntax). A simple grammar could have production rules like this one: 10 -> 8 + 2 which is effectively performing some computation with the result at the root of the syntax tree. I don't think it gets us any kind of "formal definition" of programming languages, but it is an interesting observation. Unfortunately I can't vote to open though.
Rehno Lindeque
CC BY-SA 3.0
2011-05-06T21:16:57.987Z
@Rehno Lindeque: Yes, it is very good motivation for the question also: what programs can be and what can not be written in grammars. Thanks for great idea. "I don't think it gets us any kind of "formal definition" of programming languages" I've already got alleged one: Programming language is a formal language having corresponding mathematical theory (semantics) with three placed relation R described. That relation must be subset of cartesian product of programs and two other sets (inputs and outputs). Any program P for which there exists I and O such that R P I O is well formed program.
Vag
CC BY-SA 3.0
2011-05-07T03:49:33.667Z
I think what you and @Rehno are talking about is called [operational semantics](http://en.wikipedia.org/wiki/Operational_semantics) of a PL.
Kaveh
CC BY-SA 3.0
2011-05-07T07:48:17.593Z
David Barbour wrote up some ideas about [Generative Grammar-based Computation](http://lambda-the-ultimate.org/node/4012) 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.
Charles Stewart
CC BY-SA 3.0
2011-05-07T07:50:05.483Z
@Kaveh, well any programming language has operational semantics obviously. I was just trying to say that it's feasible that you could perform arbitrary computations using a parser generated from a grammar definition in the same sense that you can perform turing complete computation with certain cellular automata and lambda calculus.
Rehno Lindeque
CC BY-SA 3.0
2011-05-07T08:00:07.223Z
@Vag By the way, I think from the title of the question people are getting "Are the languages generated by grammars, programming languages?" while what you really mean is "grammars are programs" thus "the language in which a grammar is expressed is a programming language".
Rehno Lindeque
CC BY-SA 3.0
2011-05-07T08:10:14.140Z
What you are probably trying to ask is _(How) can grammars be seen as specifying a model of computation?_
Dave Clarke
CC BY-SA 3.0
2011-05-07T08:12:43.140Z
@Dave Clarke: No. What I want to ask is exactly "are grammar specification languages are programming languages".
Vag
CC BY-SA 3.0
2011-05-07T08:15:28.410Z
@Vag: Given that the question has changed many many times, and that it is a yes/no question, and that you have already received plenty of input and suggestions, I think it's time to leave this question alone. Note that if you want to ask an improved version of the question, it is better to ask a new question. See http://meta.cstheory.stackexchange.com/questions/374/re-ask-vs-edit-reopen
Dave Clarke
CC BY-SA 3.0
2011-05-07T08:18:39.687Z
@Dave Clarke: I agreed with you, thanks. Strictly speaking, the question changed only once -- I've said "grammars" instead of "grammar specification languages" and fixed this. To avoid bad wording, let that other question be formulated by someone other than me.
Vag
CC BY-SA 3.0
2011-05-07T08:26:26.077Z
@Vag, I could reformulate the question for you, but are you sure you want to miss out on the credit? It's a good question in my opinion. I'd recommend going with Dave's suggestion of "How can grammars be seen as specifying a model of computation?" since it's the more interesting underlying question...
Rehno Lindeque
CC BY-SA 3.0
2011-05-07T08:37:26.083Z
@Rehno Lindeque: it would be perfect and fair if you do it yourself. I'll be pleasured to read answers.
Vag
CC BY-SA 3.0
2011-05-07T09:40:40.693Z
Perhaps best answer on my question will be "Grammars are programs if rewriting rules are, because grammars are instances of rewriting rules".
Vag
CC BY-SA 3.0
2013-11-30T19:38:13.010Z
***yes***. by [Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) there is a 1-1 relationship between TMs and grammars. every TM expresses a grammar. there are other deep links. unf the way this question is phrased worked against the instincts/biases of the TCS community....
vzn
<fl.formal-languages><terminology>
Are grammars programs?
Vag
# Are grammars programs?

(Asked by: username_0 on 2011-05-06)

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

Update.

**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)

Update.

**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.

**Tags:** fl.formal-languages, terminology
> **Comments:**
> **username_0**: Thanks for the minus! And don't bother explaining why, I'll try to figure out it myself.  
> **username_1**: My explanation of my downvote was almost as long as your entire question. :)  
> **username_0**: And what it was?  
> **username_1**: 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?  
> **username_2**: programming languages syntax is specified by a grammar..like any formal language. but that's not very interesting or deep at all  
> **username_0**: @Jukka Suomela: Could you please give a source of your "usual definitions of programming languages" that I could check it out too?  
> **username_2**: @Vag clearly not all languages can be specified by finite grammars. but of course programming languages will be specified by finite grammars, because they need to be parsed and also need to be used by humans. so if this is your point, it's out of scope here. the burden is on you to motivate your question and show your definitions.  
> **username_0**: @Sasho Nikolov: update: description of motivation added.  
> **username_3**: Even if there's something of merit here, the question itself is too open-ended: "trying to come up with a definition of programming language" ? I vote to close.  
> **username_0**: @Suresh Venkat: The question is not "what is definition of programming language" but "are grammars programming languages". It allows only two argumented anwers Yes or No, is it really "open ended"?  
> **username_3**: 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.  
> **username_0**: @Suresh Venkat: Even if motivation to know what programming languages are seems disgusting to you, a question may be good in spite of bad motivation behind it, no?  
> **username_4**: From http://en.wikipedia.org/wiki/Programming_language: A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication.  
> **username_5**: @Vag: Please calm down.  From Wikipedia:  "A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication."  That definition supports the points of both Jukka and Sasho.  No one is out to get you.  We are asking, in different ways, what you need from this site that the first hits in a google search could not give you.  
> **username_4**: From http://en.wikipedia.org/wiki/Formal_grammar: A formal grammar (sometimes simply called a grammar) is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form.  
> **username_5**: Okay Dave, I'll buy you a Coke next time I'm over that way.  Or sooner, if you're going to be at FCRC.  
> **username_4**: Thanks @Aaron. Nice to know there'll be a coke waiting for me.  
> **username_0**: Then why do not just say "No" as answer and place your wikipedia argument in it? Or "Yes", whatever.  
> **username_0**: "designed to express computations that can be performed by a machine, particularly a computer." -- design purposes must not be part of definition. "Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication." usage patterns are not part of correct definition ditto. What is the rest? "programming languages are artifical languages". Bad stated and very incomplete. So what is the answer to my question?  
> **username_4**: No. A grammar is not a programming language. Question should be closed.  
> **username_0**: Please explain WHY?  
> **username_4**: The reason the question should be closed is because it is not at the level of research-level theoretical computer science.  
> **username_0**: Oops.. Great apologies, nasty mistake in wording. I meant to say "languages for grammars specification", not grammars per se. My bad... *becomes red*  
> **username_1**: @Vag: I guess one of the problems here is that other people don't see why a grammar would be a programming language. It is a bit like asking on a cooking site "Are eggs microwave ovens?" It is difficult to see why someone would think that eggs would be microwave ovens, and therefore difficult to try to explain why they are not microwave ovens.  
> **username_1**: The new version of the question now makes a lot more sense; it is no longer apples and oranges. But I do not think that it is a particularly relevant question on this site. You can certainly think that grammar specification languages are programming languages, parser generators are compilers, and parsers are computer programs. But I do not think that this is a research-level question in theoretical computer science.  
> **username_0**: "No. A grammar is not a programming language. Question should be closed. – @Dave Clarke. "grammar specification languages are programming languages" -- @Jukka Suomela. Not research question and no consensus on it. Excellent.  
> **username_3**: If you wish to continue this discussion, I'd suggest meta.cstheory.stackexchange.com. I'd also suggest less snark.  
> **username_0**: @Suresh Venkat: "I'd also suggest less snark" Sorry for that. I take programming/CS very much to heart and get boiling too often about it. I'll try to get things easier henceforth. " "If you wish to continue this discussion, I'd suggest meta.cstheory." Yes, I wish. How to do that?  
> **username_3**: go to meta.cstheory (from the meta link above) and create a question  
> **username_0**: @Suresh Venkat: done http://meta.cstheory.stackexchange.com/questions/1137/where-simple-but-important-questions-about-terminology-may-be-asked  
> **username_6**: @Vag, although your question is not formulated very well I think I know where you might be headed. I've come to believe that there is a interesting connection between programming languages and grammars (unrelated to the actual parsing of programming language syntax). A simple grammar could have production rules like this one: 10 -> 8 + 2 which is effectively performing some computation with the result at the root of the syntax tree. I don't think it gets us any kind of "formal definition" of programming languages, but it is an interesting observation. Unfortunately I can't vote to open though.  
> **username_0**: @Rehno Lindeque: Yes, it is very good motivation for the question also: what programs can be and what can not be written in grammars. Thanks for great idea. "I don't think it gets us any kind of "formal definition" of programming languages" I've already got alleged one: Programming language is a formal language having corresponding mathematical theory (semantics) with three placed relation R described. That relation must be subset of cartesian product of programs and two other sets (inputs and outputs). Any program P for which there exists I and O such that R P I O is well formed program.  
> **username_7**: I think what you and @Rehno are talking about is called [operational semantics](http://en.wikipedia.org/wiki/Operational_semantics) of a PL.  
> **username_8**: David Barbour wrote up some ideas about [Generative Grammar-based Computation](http://lambda-the-ultimate.org/node/4012) 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.  
> **username_6**: @Kaveh, well any programming language has operational semantics obviously. I was just trying to say that it's feasible that you could perform arbitrary computations using a parser generated from a grammar definition in the same sense that you can perform turing complete computation with certain cellular automata and lambda calculus.  
> **username_6**: @Vag By the way, I think from the title of the question people are getting "Are the languages generated by grammars, programming languages?" while what you really mean is "grammars are programs" thus "the language in which a grammar is expressed is a programming language".  
> **username_4**: What you are probably trying to ask is _(How) can grammars be seen as specifying a model of computation?_  
> **username_0**: @Dave Clarke: No. What I want to ask is exactly "are grammar specification languages are programming languages".  
> **username_4**: @Vag: Given that the question has changed many many times, and that it is a yes/no question, and that you have already received plenty of input and suggestions, I think it's time to leave this question alone. Note that if you want to ask an improved version of the question, it is better to ask a new question. See http://meta.cstheory.stackexchange.com/questions/374/re-ask-vs-edit-reopen  
> **username_0**: @Dave Clarke: I agreed with you, thanks. Strictly speaking, the question changed only once -- I've said "grammars" instead of "grammar specification languages" and fixed this. To avoid bad wording, let that other question be formulated by someone other than me.  
> **username_6**: @Vag, I could reformulate the question for you, but are you sure you want to miss out on the credit? It's a good question in my opinion. I'd recommend going with Dave's suggestion of "How can grammars be seen as specifying a model of computation?" since it's the more interesting underlying question...  
> **username_0**: @Rehno Lindeque: it would be perfect and fair if you do it yourself. I'll be pleasured to read answers.  
> **username_0**: Perhaps best answer on my question will be "Grammars are programs if rewriting rules are, because grammars are instances of rewriting rules".  
> **username_9**: ***yes***. by [Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) there is a 1-1 relationship between TMs and grammars. every TM expresses a grammar. there are other deep links. unf the way this question is phrased worked against the instincts/biases of the TCS community....  

---

## 0 answers

