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.