Which models of computation can be expressed through grammars? 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' -&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'


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 -&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


...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.
There is a one-to-one correspondence between Chomsky Type-0 grammars and Turing machines.

This is exploied in the Thue programing language which allows you to write Turing-complete programs specified by an initial string and a set of string-rewriting rules (a 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 family, in particular 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, Scala and Qi.