3

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.
Vag
  • 443
  • 2
  • 10
  • Thanks for the minus! And don't bother explaining why, I'll try to figure out it myself. – Vag May 06 '11 at 14:01
  • 4
    My explanation of my downvote was almost as long as your entire question. :) – Jukka Suomela May 06 '11 at 14:11
  • And what it was? – Vag May 06 '11 at 14:26
  • 2
    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 May 06 '11 at 14:35
  • programming languages syntax is specified by a grammar..like any formal language. but that's not very interesting or deep at all – Sasho Nikolov May 06 '11 at 14:39
  • @Jukka Suomela: Could you please give a source of your "usual definitions of programming languages" that I could check it out too? – Vag May 06 '11 at 14:53
  • @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 May 06 '11 at 15:05
  • @Sasho Nikolov: update: description of motivation added. – Vag May 06 '11 at 15:25
  • 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 May 06 '11 at 15:29
  • @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 May 06 '11 at 15:31
  • 2
    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 May 06 '11 at 15:38
  • @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 May 06 '11 at 15:41
  • 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 May 06 '11 at 16:01
  • 2
    @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 May 06 '11 at 16:01
  • 1
    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 May 06 '11 at 16:02
  • 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 May 06 '11 at 16:02
  • Thanks @Aaron. Nice to know there'll be a coke waiting for me. – Dave Clarke May 06 '11 at 16:04
  • Then why do not just say "No" as answer and place your wikipedia argument in it? Or "Yes", whatever. – Vag May 06 '11 at 16:13
  • "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 May 06 '11 at 16:19
  • No. A grammar is not a programming language. Question should be closed. – Dave Clarke May 06 '11 at 16:32
  • Please explain WHY? – Vag May 06 '11 at 16:34
  • 3
    The reason the question should be closed is because it is not at the level of research-level theoretical computer science. – Dave Clarke May 06 '11 at 16:37
  • Oops.. Great apologies, nasty mistake in wording. I meant to say "languages for grammars specification", not grammars per se. My bad... becomes red – Vag May 06 '11 at 16:38
  • @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 May 06 '11 at 16:39
  • 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 May 06 '11 at 16:52
  • "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 May 06 '11 at 17:10
  • 1
    If you wish to continue this discussion, I'd suggest meta.cstheory.stackexchange.com. I'd also suggest less snark. – Suresh Venkat May 06 '11 at 19:55
  • @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 May 06 '11 at 20:14
  • 1
    go to meta.cstheory (from the meta link above) and create a question – Suresh Venkat May 06 '11 at 20:23
  • 2
    @Suresh Venkat: done http://meta.cstheory.stackexchange.com/questions/1137/where-simple-but-important-questions-about-terminology-may-be-asked – Vag May 06 '11 at 20:32
  • @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 May 06 '11 at 21:12
  • @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 May 06 '11 at 21:16
  • I think what you and @Rehno are talking about is called operational semantics of a PL. – Kaveh May 07 '11 at 03:49
  • 5
    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. – Charles Stewart May 07 '11 at 07:48
  • @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 May 07 '11 at 07:50
  • @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 May 07 '11 at 08:00
  • What you are probably trying to ask is (How) can grammars be seen as specifying a model of computation? – Dave Clarke May 07 '11 at 08:10
  • @Dave Clarke: No. What I want to ask is exactly "are grammar specification languages are programming languages". – Vag May 07 '11 at 08:12
  • @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 May 07 '11 at 08:15
  • @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 May 07 '11 at 08:18
  • 1
    @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 May 07 '11 at 08:26
  • 2
    @Rehno Lindeque: it would be perfect and fair if you do it yourself. I'll be pleasured to read answers. – Vag May 07 '11 at 08:37
  • Perhaps best answer on my question will be "Grammars are programs if rewriting rules are, because grammars are instances of rewriting rules". – Vag May 07 '11 at 09:40
  • *yes*. by 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 Nov 30 '13 at 19:38

0 Answers0