<p>There is a one-to-one correspondence between <a href="http://en.wikipedia.org/wiki/Unrestricted_grammar" rel="noreferrer">Chomsky Type-0 grammars</a> and Turing machines.</p>

<p>This is exploied in the <a href="http://en.wikipedia.org/wiki/Thue_%28programming_language%29" rel="noreferrer">Thue programing language</a> which allows you to write Turing-complete programs specified by an initial string and a set of string-rewriting rules (a <a href="http://en.wikipedia.org/wiki/Semi-Thue_grammar" rel="noreferrer">semi-Thue grammar</a>, which is equivalent to a type-0 grammar).</p>

<p>UPDATE:</p>

<p>Other than esoteric "Turing tar-pit" languages like Thue, various general purpose languages that allow the programmer to extend their own syntax can be used to perform Turing-complete computation during the parsing-compilation stage.</p>

<p>Languages in the <a href="http://en.wikipedia.org/wiki/Lisp_%28programming_language%29" rel="noreferrer">Lisp</a> family, in particular <a href="http://en.wikipedia.org/wiki/Common_Lisp" rel="noreferrer">Common Lisp</a>, are probably the most obvious examples, but also, broadly speaking, languages with static type checking that doesn't always need to halt, such as <a href="http://en.wikipedia.org/wiki/Template_metaprogramming" rel="noreferrer">C++ with templates</a>, <a href="http://en.wikipedia.org/wiki/Scala_%28programming_language%29" rel="noreferrer">Scala</a> and <a href="http://en.wikipedia.org/wiki/Qi_%28programming_language%29" rel="noreferrer">Qi</a>.</p>

CC BY-SA 3.0
2011-05-08T03:37:06.040Z
But the question is about things that work the other way round: one should arrive at the result not by rewriting an initial sequence of symbols according to the rules, but the "result" of the computation defined by a grammar in this question is an initial symbol that can produce the "input" sequence according to the rules of the grammar.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T13:36:06.887Z
But, if I understand correctly, the two things are essentially equivalent: If and only if, starting from a fixed initial symbol, the grammar can generate the input sequence, then the correspoding Turing machine accepts on that sequence.
If you want to consider computations that return a result other than accept/reject, but still in a finite set, you have to add a nondeterministic choiche of the initial symbol (actually, that's just an additional rule). To allow results in an infinite set, you can define a grammar that generates the string $concat(quote(in), out)$ iff $TM(in) = out$.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-05-08T15:27:46.600Z
I agree that the correspondence between Type0 grammars and TMs is a valid answer to the question (especially, if restricted to computing yes/no-functions). The further suggestion to model an arbitrary TM with a grammar by introducing some convention how to represent the input-output pairs seems to me not to match the intended interest of the original question: (to be cont'd)
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T15:28:28.487Z
I understand it as a question for exploiting exactly the existing grammar frameworks and the corresponding parsers for performing computations, i.e., the allowed form of the translation between a function f and a grammar can only be: an input I was parsed as S means f(I)=S.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T15:37:01.317Z
Superficially, the Thue programming language doesn't seem to fall into this kind of using a grammar framework: although it has rewriting rules like a grammar, the computation of a result from an input goes in the direction of the rules, not in the reverse direction, as Rehno wants. (But perhaps it's only a matter of changing the direction of the arrows in productions: to translate a "computation as a parser" grammar in the sense of this Q into Thue could only be to change the directions of the rules, then the Thue program will arrive at the starting symbols as the results indeed, won't it?..)
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-09T07:53:31.823Z
Yes I agree, I think it's just a matter of which direction the arrow points in. Thanks for the two languages Thue and Refal suggested by Artem, I think that at least answers the question of whether context-sensitive grammars are turing complete with respect to their rewriting rules
Rehno Lindeque
CC BY-SA 3.0
2011-05-09T12:52:35.100Z
@imz: I think that reversing the direction of the rules does work for Thue, as long as you allow true nondeterminism in execution.
If you want to obtain the result of the computation from the parse tree you need to specify some sort of encoding. There are a few possibilities for both finite and infite result sets, however in general there will be a many-to-one correspondence between the parse tree and the result, since the parse tree is a representation of the execution trace of the corresponding Turing machine.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-05-07T20:12:43.930Z
2011-05-08T13:56:51.707Z
2011-05-08T13:56:51.707Z
Antonio Valerio Miceli-Barone
<blockquote>
  <p>Furthermore, could we build Turing-complete programs by specifying grammars…?</p>
</blockquote>

<p>I'm not sure if I correctly understood your question, but if you're looking for a programming language based on a kind of string rewriting system, you probably would be intersted in <a href="http://en.wikipedia.org/wiki/Refal">Refal</a>, which is based on <a href="http://en.wikipedia.org/wiki/Markov_algorithm">Markov algorithm</a> formalism (a Turing-comlete formalism which is also a grammar-like string rewriting system).</p>

CC BY-SA 3.0
2011-05-08T15:45:56.860Z
I understood the question in the following way: Rehno is interested in the bootom-up parsing process (defined by a grammar) to be viewed as a computation of the result. The computation should build the result from the parts going in the direction opposite to the production rules of the grammar. Refal's rewriting rules (IIUC, similarly to the Thue programming language mentioned above) would be going in the other direction (from input to the result).
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-09T07:46:15.247Z
Now that I think about it though, context-sensitive grammars have more than one symbol on the LHS of production rules. So I think there's no real practical difference. A parser for a context-sensitive language would be a string rewriting system no matter how you look at it right?
Rehno Lindeque
CC BY-SA 3.0
2011-05-09T18:33:58.743Z
@imz thank you for the clarification on Rehno's question.

@Rehno “A parser for a context-sensitive language would be a string rewriting system no matter how you look at it right?” — it probably make sense, yes.
Artem Pelenitsyn
CC BY-SA 3.0
2011-05-11T03:52:55.597Z
But are Refal's rewriting rules treated non-deterministically? (Or put differently: will Refal do backtracking in the search for a working rewriting path?) If we want to model this "parsing as computation" approach with rewriting rules in the reversed direction, we need non-deterministic rules; consider a grammar like `S -> A a; S -> B b; A -> 0; B -> 0`. If we program this by reversing the rules, we'll need to choose different rules for processing `0` at run time in order to evaluate "0a" or "0b" to `S`.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T15:28:50.033Z
2011-05-08T15:28:50.033Z
Artem Pelenitsyn
<p>My answer is not intented to be formal, precise and absolutely in-topic. I think Marc Hamman's answer is rock solid, but your question made me think of a related topic.</p>

<p>Grammars may be considered special cases of deductive systems: the input is a judgement, and the parse tree is a <em>derivation</em> of the judgement, or <em>proof</em> that the judgement is valid according to the (grammatical) rules.</p>

<p>In that sense, your question could be related to the approach of some part of the logic programming / proof search community (I'm thinking of <a href="http://www.lix.polytechnique.fr/~dale/">Dale Miller</a> for example), which is that proof <em>search</em> has computational content, as opposed to the more classic type/proof theory point of view where computation is proof <em>normalization</em>.</p>

<p>Remark: re-reading my answer, I think the idea that "parse-tree construction is proof search" is a bit far-fetched here. Proof search rather flows in the other direction: one start from a given, rather complex judgement and, by the repeated use of inference rules working on the structure of the proof, one hopefully attain simpler axioms that do not need to be proved further. So it would be more natural to see, in grammar terms, complex judgements as non-terminals, atoms as terminals, and the proof search as a word generation problem, or non-emptiness test.</p>

CC BY-SA 3.0
2011-05-08T03:21:13.277Z
Very interesting remarks though. My brain's a bit too tired to give a good response right now, however in my example the branches of the tree essentially represent sub-computations that are composed together according to the parsing rules...
Rehno Lindeque
CC BY-SA 3.0
2011-05-07T17:57:33.910Z
2011-05-07T19:36:27.980Z
2011-05-07T19:36:27.980Z
gasche
<p>(Just some trivial considerations. Could be a comment, but too long.)</p>

<p>In fact, <strong>what you describe looks in effect as the very natural view on what a language is</strong> (in the human understanding of "language", its purpose) and how a grammar defines a language.</p>

<p>A language comprises (infinitely many) correct syntactic forms which are <strong>interpreted to give the semantic values</strong>.</p>

<p>If the interpretation is computable, then the syntactic forms of a language can be viewed as programs that compute the semantic values.</p>

<p>If we assume that a language is implemented as a finite device, we can call this finite representation of a language a "grammar". According to this understanding, a grammar cares about syntax, but also about the semantics, i.e., how to compute the semantic value of a whole expression from the values of its parts (the atomic parts and their values are stored in a "lexicon").</p>

<p>Some theories of natural language have such a form (the form that is consistent with the above considerations; it was already mentioned in @gasche's answer here): a <strong>deductive system</strong> that searches for a derivation of the input (coupled with the computation of the semantic value, or the building of the proof term; cf. Curry-Horward correspondence). So, if we look at systems like that and consider them grammars, <strong>then your question is trivial</strong>: these systems are exactly devised to perform computations in the manner you describe.</p>

<p><strong>But what traditionally is called "formal languages" and "formal grammars" lack the semantic side</strong> of this view on languages and grammars. So, your question becomes interesting: to what extent can the semantic side (computation) be "simulated" in the syntax? What are the computational powers of each of the known classes of formal grammars (if the computation is to be understood as the bottom-up parsing: <strong>a function $f$ is computed by a grammar $G$ in the sense of your question if</strong> for any valid input $I$ $f(I)=S$ iff $I$ is parsed as the symbol $S$ according to $G$)?</p>

<p>(In fact, the real compilers for programming languages look more like a system with both syntax and semantics: they transform the syntactic form of a program into an executable, which is the semantic meaning of the program, and rather not merely to a starting symbol of the grammar.)</p>

CC BY-SA 3.0
2011-05-08T16:28:57.993Z
2011-05-10T22:00:00.783Z
2011-05-10T22:00:00.783Z
imz -- Ivan Zakharyaschev
<p>Just to add:</p>
<blockquote>
A pure logic program has declarative reading and procedural reading. This report discusses the idea that these can be complemented by a grammatical reading, where the clauses are considered to be rewrite rules of a grammar. The objective is to show that this point of view facilitates transfer of expertise from logic programming to other research on programming languages and vice versa. Some examples such a transfer are discussed. On the other hand the grammatical view presented justifies some ad hoc extensions to pure logic programming and facilitates development of theoretical foundations for such extensions.
</blockquote>
<p><a href="http://hal.archives-ouvertes.fr/docs/00/07/56/71/PDF/RR-0883.pdf" rel="nofollow noreferrer">A Grammatical View of Logic Programming</a> by Pierre Deransart and Jan Maluszynski.</p>

CC BY-SA 3.0
2014-08-07T11:28:56.657Z
Apparently, Prolog arose out of attribute grammars, so this view is what started logic programming.
reinierpost
CC BY-SA 3.0
2011-05-25T11:12:46.517Z
2011-05-25T11:12:46.517Z
2020-06-17T09:38:08.363Z
Vag
<p>What about something like Peano numbers :</p>

<pre><code>S    -&gt; int
int  -&gt; zero
int  -&gt; succ
zero -&gt; "0"
succ -&gt; "#" int
</code></pre>

<p>it will recognize any string ( number ) of this form :</p>

<pre><code>0   // zero
#0  // one
##0 // two
</code></pre>

<p>and it should return a nested structure, with the deepness being the number.</p>

<p>But it starts getting complicated when one wants to implements just say addition :</p>

<pre><code>S    -&gt; int
int  -&gt; sum
int  -&gt; zero
int  -&gt; succ
zero -&gt; "0"
succ -&gt; "#" int
sum  -&gt; int "+" int
</code></pre>

<p>It makes perfectly sense in that it will only recognize well formed ints like this :</p>

<pre><code>#####0 + ####0
</code></pre>

<p>But this grammar introduce a split in the parse tree whenever there is a sum, so instead of having a nice one-branched tree, that directly maps to a number, we have the structure of the expression, still a few computations away from the effective value. So no computation is done, only recognition. The trouble may not be the grammar but the parser. One may instead use something else, idk...
Another point that comes to mind is the adequacy of grammar formalism to express computation. When you look a Peano's axiom ( in Haskell-like notation ) :</p>

<pre><code>1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X
</code></pre>

<p>The third rule explicitly states a transformation. Could anyone imagine to carry to same amount of meaning in a context-free grammar rule. And if so, how !?</p>

CC BY-SA 3.0
2014-09-23T13:26:34.523Z
2014-09-23T13:26:34.523Z
dader
<p>This is a reformulation of <a href="https://cstheory.stackexchange.com/questions/6420/are-grammars-programs">Are grammars programs?</a> previous asked by <a href="https://cstheory.stackexchange.com/users/491/vag">Vag</a> and with many suggestions from the commenters.</p>

<p>In what way can a grammar be seen as specifying a model of computation?
If, for example, we take a simple context-free grammar such as</p>

<pre><code>G ::= '1' -&gt; '0' '+' '1'
      '1' -&gt; '1' '+' '0'
      '2' -&gt; '2' '+' '0'
      '2' -&gt; '1' '+' '1'
      '2' -&gt; '0' '+' '2'
      '3' -&gt; '3' '+' '0'
      '3' -&gt; '2' '+' '1'
      '3' -&gt; '1' '+' '2'
      '3' -&gt; '1' '+' '2'
</code></pre>

<p>Assuming that the parser does not differentiate between <em>terminal</em> and <em>nonterminal</em> symbols as I've demonstrated here, then it is possible to perform simple arithmetic for numbers up to 3.</p>

<p>For example, take the string </p>

<pre><code>"2 + 0 + 1"
</code></pre>

<p>Running a LR(1) parser on this string should give us the following <em>concrete syntax tree</em> where the result of the computation is stored at the root of the tree:</p>

<pre><code>           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0' 
</code></pre>

<p>Thus, if we take a grammar to be a <em>program</em> and a parser generator to be a <em>compiler</em>, could we see the grammar specification language as a <em>programming language</em>?</p>

<p>Furthermore, could we build Turing-complete programs by specifying grammars similar to how you could build turing complete programs with <a href="http://en.wikipedia.org/wiki/Rule_110" rel="nofollow noreferrer">celullar automata</a> or the <a href="http://en.wikipedia.org/wiki/Lambda_calculus" rel="nofollow noreferrer">lambda calculus</a>?</p>

<p>In other words, it is known that in the sense of <strong>recognizing</strong> a language, <em>regular languages</em> correspond to <em>finite state automata</em>, <em>context-free languages</em> correspond to <em>push down automata</em>, and <em>context-sensitive languages</em> correspond to <em>linear bounded automata</em>. However, if we look at grammars as <em>computational devices</em> (i.e. <em>programs</em> in the sense of the example above), then how do we classify the <strong>computational strength</strong> of each class of grammars in the Chomsky hierarchy?</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Regular_grammar" rel="nofollow noreferrer">Regular grammars</a></li>
<li><a href="http://en.wikipedia.org/wiki/Context-free_grammar" rel="nofollow noreferrer">Context-free grammars</a></li>
<li><a href="http://en.wikipedia.org/wiki/Context-sensitive_grammar" rel="nofollow noreferrer">Context-sensitive grammars</a></li>
<li><a href="http://en.wikipedia.org/wiki/Unrestricted_grammar" rel="nofollow noreferrer">Unrestricted grammars</a> (for <a href="http://en.wikipedia.org/wiki/Recursively_enumerable_language" rel="nofollow noreferrer">recursively enumerable languages</a>)</li>
</ul>

<p>Also, how about the lesser known subclasses of grammars such as </p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Deterministic_context-free_grammar" rel="nofollow noreferrer">Deterministic context-free grammars</a> (also <a href="http://en.wikipedia.org/wiki/LR_parser" rel="nofollow noreferrer">LR(k)</a>/<a href="http://en.wikipedia.org/wiki/LL_parsing" rel="nofollow noreferrer">LL(k)</a>/<a href="http://en.wikipedia.org/wiki/Simple_LR_parser" rel="nofollow noreferrer">SLR</a>/<a href="http://en.wikipedia.org/wiki/LALR_parser" rel="nofollow noreferrer">LALR</a> etc)</li>
<li><a href="http://en.wikipedia.org/wiki/Nested_word" rel="nofollow noreferrer">Nested word grammars</a></li>
<li><a href="http://en.wikipedia.org/wiki/Tree-adjoining_grammar" rel="nofollow noreferrer">Tree adjoining grammars</a></li>
<li><a href="http://en.wikipedia.org/wiki/Indexed_grammar" rel="nofollow noreferrer">Indexed grammars</a></li>
</ul>

<p><strong>EDIT:</strong> By the way, this is a nitpick on my own question but I didn't mention that I gave no starting symbol for the example grammar and hand-waved at the need to distinguish between terminals and nonterminals. Technically or traditionally I think the grammar would probably have to be written in a more complicated form like this one (where S is the starting symbol and the \$ represents the end-of-stream terminal):</p>

<pre><code>G ::= S -&gt; R0 '$'
      S -&gt; R1 '$'
      S -&gt; R2 '$'
      R0 -&gt; '0'
      R0 -&gt; R0 '+' '0'
      R1 -&gt; '1'
      R1 -&gt; R0 '+' '1'
      R1 -&gt; '1' '+' R0
      R1 -&gt; R0 '+' '1' '+' R0
      R2 -&gt; '2'
      R2 -&gt; R0 '+' '2'
      R2 -&gt; '2' '+' R0
      R2 -&gt; R0 '+' '2' '+' R0
      R2 -&gt; R1 '+' '1'
      R2 -&gt; R1 '+' '1' '+' R0
</code></pre>

<p>...not that it really changes anything, but I thought I should mention it.</p>

<p><strong>EDIT:</strong> Something else that came to mind when I read gasche's answer is that each branch in the tree in my example represents a sub-computation. If you look at each production rule as a function where the LHS represents the result and the RHS represents its arguments, then the structure of the grammar determines how functions are composed.</p>

<p>In other words the context of the parser together with its lookahead mechanism helps to determine not only which functions to apply ('kinda' like parametric polymorphism) but how they should be composed together to form new functions.</p>

<p>At least, I guess you could look at it this way for unambiguous CFG's, for other grammars the mental gymnastics is a little bit too much for me right now.</p>

CC BY-SA 3.0
2011-05-07T09:46:50.157Z
You forgot to mention the Visibly Pushdown Automaton (Nested Words), such a lovely and promising appliance! It is important because it seems to be minimal improvement over regexps to be able to parse programs written in popular programming languages. ( http://www.cis.upenn.edu/~alur/nw.html )
Vag
CC BY-SA 3.0
2011-05-07T10:12:10.027Z
Thanks, that's very interesting, I haven't looked it up! There's a couple of others I also skipped like deterministic context-free, tree-adjoining, indexed and so on, I just thought it might be a little bit much for one question... But maybe I'll add them
Rehno Lindeque
CC BY-SA 3.0
2011-05-07T10:24:44.273Z
@Rehno Lindeque: "There's a couple of others I also skipped" yes, I know, I do not propose clutterize the question but only (1) promote cool neat technology and (2) it will be astonishingly surprising if minimal automaton to parse popular PLs has also some distinguishing properties in computation land.
Vag
CC BY-SA 3.0
2011-05-07T20:55:11.357Z
It is not clear for me what is meant by a "computational devices". Do mean computing a function? I.e. are you asking about defining computation for functions in place of deciding membership in languages using grammars?
Kaveh
CC BY-SA 3.0
2011-05-07T21:00:34.253Z
There are other things in your question that confuse me. Are you using "programming language" and "compiler" in their standard meanings?
Kaveh
CC BY-SA 3.0
2011-05-07T22:22:24.837Z
But what would you call a "grammar"? What's the difference between any program and a "grammar" in your question? (If one simply has a program (in any programming language) that given an input produces an "interesting" output or says "not parsable", can it be said that this program is the grammar that defines the language of parsable inputs?)
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T01:29:52.190Z
@Kaveh, so yes I thought "computational device" was a bit shaky myself. Looking for something like "program" but I wanted to make clear that it's not necessarily turing complete.
Rehno Lindeque
CC BY-SA 3.0
2011-05-08T01:36:53.623Z
@Kaveh, wrt "program" / "compiler", yes more-or-less the standard meaning I'd say. Perhaps I should say that a grammar is source code for a program since I make the analogy between parser generator & compiler. Just glossed over it since I didn't think it would be controversial.
Rehno Lindeque
CC BY-SA 3.0
2011-05-08T01:51:48.793Z
@imz I mean grammars as they are formally defined in the chomsky hierarchy (I.e. as sets of productions). Since I'm claiming exactly what you're saying: that grammars are programs, it just means the class of programs representable by grammars (which is the question).
Rehno Lindeque
CC BY-SA 3.0
2011-05-08T03:24:47.127Z
Good, but you also mentioned TAGs, so I felt that you were ready to depart from the definition with production rules that have a sequence of symbols on the rhs and on the lhs. So, you do not suppose any freedom in what a "grammar" is, do you? That isn't very clear from your question.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T03:44:11.840Z
Indexed grammars--although mentioned in the question--also don't conform to the definition of a "grammar" you give here in comments.
imz -- Ivan Zakharyaschev
CC BY-SA 3.0
2011-05-08T03:46:31.023Z
@imz To be honest I'm really not familiar with indexed grammars, I only added them as an after-thought.
Rehno Lindeque
CC BY-SA 3.0
2011-05-08T04:00:58.043Z
I'm starting to think it might have been a good idea to post this question to the LtU forum instead looking at the cool discussions :P. Btw @imz, perhaps it would be best to read the question as "which classes of grammars correspond with which classes of programs in the 'functional' sense described by Jukka in Marc Hamman's answer". Perhaps I should make this more clear though...
Rehno Lindeque
CC BY-SA 3.0
2011-05-09T07:56:08.027Z
I'm a little disappointed that Marc Hamman deleted his answer. It wasn't strictly answering the question directly, but it was valuable for the discussion.
Rehno Lindeque
CC BY-SA 3.0
2011-05-11T01:47:31.147Z
@Rehno, cstheory is a Q&A site, it is not for discussions. LtU or chat might be a better place for such discussions. Argumentative/subjective questions  on cstheory may get closed, and I will vote (as a user) to close the question as argumentative if I feel that the question is too open ended and cannot be answered objectively.
Kaveh
CC BY-SA 3.0
2011-05-11T10:02:05.830Z
Thanks, Kaveh, yes I understand. I only realized after I posted the question that this is better suited for LtU. Never-the-less I think people can still answer the question "which class of grammars corresponds with which class of programs" objectively.
Rehno Lindeque
<fl.formal-languages><pl.programming-languages><grammars><universal-computation>
Which models of computation can be expressed through grammars?
Rehno Lindeque
# Which models of computation can be expressed through grammars?

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

This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.
In what way can a grammar be seen as specifying a model of computation?
If, for example, we take a simple context-free grammar such as
G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Assuming that the parser does not differentiate between terminal and nonterminal symbols as I've demonstrated here, then it is possible to perform simple arithmetic for numbers up to 3.
For example, take the string 
"2 + 0 + 1"

Running a LR(1) parser on this string should give us the following concrete syntax tree where the result of the computation is stored at the root of the tree:
           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0' 

Thus, if we take a grammar to be a program and a parser generator to be a compiler, could we see the grammar specification language as a programming language?
Furthermore, could we build Turing-complete programs by specifying grammars similar to how you could build turing complete programs with celullar automata or the lambda calculus?
In other words, it is known that in the sense of recognizing a language, regular languages correspond to finite state automata, context-free languages correspond to push down automata, and context-sensitive languages correspond to linear bounded automata. However, if we look at grammars as computational devices (i.e. programs in the sense of the example above), then how do we classify the computational strength of each class of grammars in the Chomsky hierarchy?

Regular grammars
Context-free grammars
Context-sensitive grammars
Unrestricted grammars (for recursively enumerable languages)

Also, how about the lesser known subclasses of grammars such as 

Deterministic context-free grammars (also LR(k)/LL(k)/SLR/LALR etc)
Nested word grammars
Tree adjoining grammars
Indexed grammars

EDIT: By the way, this is a nitpick on my own question but I didn't mention that I gave no starting symbol for the example grammar and hand-waved at the need to distinguish between terminals and nonterminals. Technically or traditionally I think the grammar would probably have to be written in a more complicated form like this one (where S is the starting symbol and the \$ represents the end-of-stream terminal):
G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

...not that it really changes anything, but I thought I should mention it.
EDIT: Something else that came to mind when I read gasche's answer is that each branch in the tree in my example represents a sub-computation. If you look at each production rule as a function where the LHS represents the result and the RHS represents its arguments, then the structure of the grammar determines how functions are composed.
In other words the context of the parser together with its lookahead mechanism helps to determine not only which functions to apply ('kinda' like parametric polymorphism) but how they should be composed together to form new functions.
At least, I guess you could look at it this way for unambiguous CFG's, for other grammars the mental gymnastics is a little bit too much for me right now.

**Tags:** fl.formal-languages, pl.programming-languages, grammars, universal-computation
> **Comments:**
> **username_1**: You forgot to mention the Visibly Pushdown Automaton (Nested Words), such a lovely and promising appliance! It is important because it seems to be minimal improvement over regexps to be able to parse programs written in popular programming languages. ( http://www.cis.upenn.edu/~alur/nw.html )  
> **username_0**: Thanks, that's very interesting, I haven't looked it up! There's a couple of others I also skipped like deterministic context-free, tree-adjoining, indexed and so on, I just thought it might be a little bit much for one question... But maybe I'll add them  
> **username_1**: @Rehno Lindeque: "There's a couple of others I also skipped" yes, I know, I do not propose clutterize the question but only (1) promote cool neat technology and (2) it will be astonishingly surprising if minimal automaton to parse popular PLs has also some distinguishing properties in computation land.  
> **username_2**: It is not clear for me what is meant by a "computational devices". Do mean computing a function? I.e. are you asking about defining computation for functions in place of deciding membership in languages using grammars?  
> **username_2**: There are other things in your question that confuse me. Are you using "programming language" and "compiler" in their standard meanings?  
> **username_3**: But what would you call a "grammar"? What's the difference between any program and a "grammar" in your question? (If one simply has a program (in any programming language) that given an input produces an "interesting" output or says "not parsable", can it be said that this program is the grammar that defines the language of parsable inputs?)  
> **username_0**: @Kaveh, so yes I thought "computational device" was a bit shaky myself. Looking for something like "program" but I wanted to make clear that it's not necessarily turing complete.  
> **username_0**: @Kaveh, wrt "program" / "compiler", yes more-or-less the standard meaning I'd say. Perhaps I should say that a grammar is source code for a program since I make the analogy between parser generator & compiler. Just glossed over it since I didn't think it would be controversial.  
> **username_0**: @imz I mean grammars as they are formally defined in the chomsky hierarchy (I.e. as sets of productions). Since I'm claiming exactly what you're saying: that grammars are programs, it just means the class of programs representable by grammars (which is the question).  
> **username_3**: Good, but you also mentioned TAGs, so I felt that you were ready to depart from the definition with production rules that have a sequence of symbols on the rhs and on the lhs. So, you do not suppose any freedom in what a "grammar" is, do you? That isn't very clear from your question.  
> **username_3**: Indexed grammars--although mentioned in the question--also don't conform to the definition of a "grammar" you give here in comments.  
> **username_0**: @imz To be honest I'm really not familiar with indexed grammars, I only added them as an after-thought.  
> **username_0**: I'm starting to think it might have been a good idea to post this question to the LtU forum instead looking at the cool discussions :P. Btw @imz, perhaps it would be best to read the question as "which classes of grammars correspond with which classes of programs in the 'functional' sense described by Jukka in Marc Hamman's answer". Perhaps I should make this more clear though...  
> **username_0**: I'm a little disappointed that Marc Hamman deleted his answer. It wasn't strictly answering the question directly, but it was valuable for the discussion.  
> **username_2**: @Rehno, cstheory is a Q&A site, it is not for discussions. LtU or chat might be a better place for such discussions. Argumentative/subjective questions  on cstheory may get closed, and I will vote (as a user) to close the question as argumentative if I feel that the question is too open ended and cannot be answered objectively.  
> **username_0**: Thanks, Kaveh, yes I understand. I only realized after I posted the question that this is better suited for LtU. Never-the-less I think people can still answer the question "which class of grammars corresponds with which class of programs" objectively.  

---

## 6 answers

### Answer by username_4 on 2011-05-07. Score: 13

There is a one-to-one correspondence between [Chomsky Type-0 grammars](http://en.wikipedia.org/wiki/Unrestricted_grammar) and Turing machines.

This is exploied in the [Thue programing language](http://en.wikipedia.org/wiki/Thue_%28programming_language%29) which allows you to write Turing-complete programs specified by an initial string and a set of string-rewriting rules (a [semi-Thue grammar](http://en.wikipedia.org/wiki/Semi-Thue_grammar), which is equivalent to a type-0 grammar).

UPDATE:

Other than esoteric "Turing tar-pit" languages like Thue, various general purpose languages that allow the programmer to extend their own syntax can be used to perform Turing-complete computation during the parsing-compilation stage.

Languages in the [Lisp](http://en.wikipedia.org/wiki/Lisp_%28programming_language%29) family, in particular [Common Lisp](http://en.wikipedia.org/wiki/Common_Lisp), are probably the most obvious examples, but also, broadly speaking, languages with static type checking that doesn't always need to halt, such as [C++ with templates](http://en.wikipedia.org/wiki/Template_metaprogramming), [Scala](http://en.wikipedia.org/wiki/Scala_%28programming_language%29) and [Qi](http://en.wikipedia.org/wiki/Qi_%28programming_language%29).

> **Comments:**
> **username_3**: But the question is about things that work the other way round: one should arrive at the result not by rewriting an initial sequence of symbols according to the rules, but the "result" of the computation defined by a grammar in this question is an initial symbol that can produce the "input" sequence according to the rules of the grammar.  
> **username_4**: But, if I understand correctly, the two things are essentially equivalent: If and only if, starting from a fixed initial symbol, the grammar can generate the input sequence, then the correspoding Turing machine accepts on that sequence. If you want to consider computations that return a result other than accept/reject, but still in a finite set, you have to add a nondeterministic choiche of the initial symbol (actually, that's just an additional rule). To allow results in an infinite set, you can define a grammar that generates the string $concat(quote(in), out)$ iff $TM(in) = out$.  
> **username_3**: I agree that the correspondence between Type0 grammars and TMs is a valid answer to the question (especially, if restricted to computing yes/no-functions). The further suggestion to model an arbitrary TM with a grammar by introducing some convention how to represent the input-output pairs seems to me not to match the intended interest of the original question: (to be cont'd)  
> **username_3**: I understand it as a question for exploiting exactly the existing grammar frameworks and the corresponding parsers for performing computations, i.e., the allowed form of the translation between a function f and a grammar can only be: an input I was parsed as S means f(I)=S.  
> **username_3**: Superficially, the Thue programming language doesn't seem to fall into this kind of using a grammar framework: although it has rewriting rules like a grammar, the computation of a result from an input goes in the direction of the rules, not in the reverse direction, as Rehno wants. (But perhaps it's only a matter of changing the direction of the arrows in productions: to translate a "computation as a parser" grammar in the sense of this Q into Thue could only be to change the directions of the rules, then the Thue program will arrive at the starting symbols as the results indeed, won't it?..)  
> **username_0**: Yes I agree, I think it's just a matter of which direction the arrow points in. Thanks for the two languages Thue and Refal suggested by Artem, I think that at least answers the question of whether context-sensitive grammars are turing complete with respect to their rewriting rules  
> **username_4**: @imz: I think that reversing the direction of the rules does work for Thue, as long as you allow true nondeterminism in execution. If you want to obtain the result of the computation from the parse tree you need to specify some sort of encoding. There are a few possibilities for both finite and infite result sets, however in general there will be a many-to-one correspondence between the parse tree and the result, since the parse tree is a representation of the execution trace of the corresponding Turing machine.  

---

### Answer by username_5 on 2011-05-08. Score: 6

> Furthermore, could we build Turing-complete programs by specifying grammars…?

I'm not sure if I correctly understood your question, but if you're looking for a programming language based on a kind of string rewriting system, you probably would be intersted in [Refal](http://en.wikipedia.org/wiki/Refal), which is based on [Markov algorithm](http://en.wikipedia.org/wiki/Markov_algorithm) formalism (a Turing-comlete formalism which is also a grammar-like string rewriting system).

> **Comments:**
> **username_3**: I understood the question in the following way: Rehno is interested in the bootom-up parsing process (defined by a grammar) to be viewed as a computation of the result. The computation should build the result from the parts going in the direction opposite to the production rules of the grammar. Refal's rewriting rules (IIUC, similarly to the Thue programming language mentioned above) would be going in the other direction (from input to the result).  
> **username_0**: Now that I think about it though, context-sensitive grammars have more than one symbol on the LHS of production rules. So I think there's no real practical difference. A parser for a context-sensitive language would be a string rewriting system no matter how you look at it right?  
> **username_5**: @imz thank you for the clarification on Rehno's question.  @Rehno “A parser for a context-sensitive language would be a string rewriting system no matter how you look at it right?” — it probably make sense, yes.  
> **username_3**: But are Refal's rewriting rules treated non-deterministically? (Or put differently: will Refal do backtracking in the search for a working rewriting path?) If we want to model this "parsing as computation" approach with rewriting rules in the reversed direction, we need non-deterministic rules; consider a grammar like `S -> A a; S -> B b; A -> 0; B -> 0`. If we program this by reversing the rules, we'll need to choose different rules for processing `0` at run time in order to evaluate "0a" or "0b" to `S`.  

---

### Answer by username_6 on 2011-05-07. Score: 6

My answer is not intented to be formal, precise and absolutely in-topic. I think Marc Hamman's answer is rock solid, but your question made me think of a related topic.

Grammars may be considered special cases of deductive systems: the input is a judgement, and the parse tree is a *derivation* of the judgement, or *proof* that the judgement is valid according to the (grammatical) rules.

In that sense, your question could be related to the approach of some part of the logic programming / proof search community (I'm thinking of [Dale Miller](http://www.lix.polytechnique.fr/~dale/) for example), which is that proof *search* has computational content, as opposed to the more classic type/proof theory point of view where computation is proof *normalization*.

Remark: re-reading my answer, I think the idea that "parse-tree construction is proof search" is a bit far-fetched here. Proof search rather flows in the other direction: one start from a given, rather complex judgement and, by the repeated use of inference rules working on the structure of the proof, one hopefully attain simpler axioms that do not need to be proved further. So it would be more natural to see, in grammar terms, complex judgements as non-terminals, atoms as terminals, and the proof search as a word generation problem, or non-emptiness test.

> **Comments:**
> **username_0**: Very interesting remarks though. My brain's a bit too tired to give a good response right now, however in my example the branches of the tree essentially represent sub-computations that are composed together according to the parsing rules...  

---

### Answer by username_3 on 2011-05-08. Score: 6

(Just some trivial considerations. Could be a comment, but too long.)

In fact, **what you describe looks in effect as the very natural view on what a language is** (in the human understanding of "language", its purpose) and how a grammar defines a language.

A language comprises (infinitely many) correct syntactic forms which are **interpreted to give the semantic values**.

If the interpretation is computable, then the syntactic forms of a language can be viewed as programs that compute the semantic values.

If we assume that a language is implemented as a finite device, we can call this finite representation of a language a "grammar". According to this understanding, a grammar cares about syntax, but also about the semantics, i.e., how to compute the semantic value of a whole expression from the values of its parts (the atomic parts and their values are stored in a "lexicon").

Some theories of natural language have such a form (the form that is consistent with the above considerations; it was already mentioned in @gasche's answer here): a **deductive system** that searches for a derivation of the input (coupled with the computation of the semantic value, or the building of the proof term; cf. Curry-Horward correspondence). So, if we look at systems like that and consider them grammars, **then your question is trivial**: these systems are exactly devised to perform computations in the manner you describe.

**But what traditionally is called "formal languages" and "formal grammars" lack the semantic side** of this view on languages and grammars. So, your question becomes interesting: to what extent can the semantic side (computation) be "simulated" in the syntax? What are the computational powers of each of the known classes of formal grammars (if the computation is to be understood as the bottom-up parsing: **a function $f$ is computed by a grammar $G$ in the sense of your question if** for any valid input $I$ $f(I)=S$ iff $I$ is parsed as the symbol $S$ according to $G$)?

(In fact, the real compilers for programming languages look more like a system with both syntax and semantics: they transform the syntactic form of a program into an executable, which is the semantic meaning of the program, and rather not merely to a starting symbol of the grammar.)


---

### Answer by username_1 on 2011-05-25. Score: 4

Just to add:

> A pure logic program has declarative reading and procedural reading. This report discusses the idea that these can be complemented by a grammatical reading, where the clauses are considered to be rewrite rules of a grammar. The objective is to show that this point of view facilitates transfer of expertise from logic programming to other research on programming languages and vice versa. Some examples such a transfer are discussed. On the other hand the grammatical view presented justifies some ad hoc extensions to pure logic programming and facilitates development of theoretical foundations for such extensions.

[A Grammatical View of Logic Programming](http://hal.archives-ouvertes.fr/docs/00/07/56/71/PDF/RR-0883.pdf) by Pierre Deransart and Jan Maluszynski.

> **Comments:**
> **username_7**: Apparently, Prolog arose out of attribute grammars, so this view is what started logic programming.  

---

### Answer by username_8 on 2014-09-23. Score: 1

What about something like Peano numbers :
S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

it will recognize any string ( number ) of this form :
0   // zero
#0  // one
##0 // two

and it should return a nested structure, with the deepness being the number.
But it starts getting complicated when one wants to implements just say addition :
S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

It makes perfectly sense in that it will only recognize well formed ints like this :
#####0 + ####0

But this grammar introduce a split in the parse tree whenever there is a sum, so instead of having a nice one-branched tree, that directly maps to a number, we have the structure of the expression, still a few computations away from the effective value. So no computation is done, only recognition. The trouble may not be the grammar but the parser. One may instead use something else, idk...
Another point that comes to mind is the adequacy of grammar formalism to express computation. When you look a Peano's axiom ( in Haskell-like notation ) :
1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

The third rule explicitly states a transformation. Could anyone imagine to carry to same amount of meaning in a context-free grammar rule. And if so, how !?


---

