19
$\begingroup$

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?

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

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.

Improve this question
$\endgroup$
16
  • 3
    $\begingroup$ 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. ( cis.upenn.edu/~alur/nw.html ) $\endgroup$
    – Vag
    May 7, 2011 at 9:46
  • 1
    $\begingroup$ 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 $\endgroup$
    – Rehno Lindeque
    May 7, 2011 at 10:12
  • 1
    $\begingroup$ @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). $\endgroup$
    – Rehno Lindeque
    May 8, 2011 at 1:51
  • 1
    $\begingroup$ @imz To be honest I'm really not familiar with indexed grammars, I only added them as an after-thought. $\endgroup$
    – Rehno Lindeque
    May 8, 2011 at 3:46
  • 1
    $\begingroup$ 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... $\endgroup$
    – Rehno Lindeque
    May 8, 2011 at 4:00

6 Answers 6

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 8, 2011 at 3:37
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Antonio Valerio Miceli-Barone
    May 8, 2011 at 13:36
  • $\begingroup$ 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) $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 8, 2011 at 15:27
  • $\begingroup$ 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. $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 8, 2011 at 15:28
  • 1
    $\begingroup$ 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?..) $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 8, 2011 at 15:37
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Rehno Lindeque
    May 8, 2011 at 3:21
6
$\begingroup$

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, which is based on Markov algorithm formalism (a Turing-comlete formalism which is also a grammar-like string rewriting system).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 8, 2011 at 15:45
  • $\begingroup$ 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? $\endgroup$
    – Rehno Lindeque
    May 9, 2011 at 7:46
  • $\begingroup$ @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. $\endgroup$
    – Artem Pelenitsyn
    May 9, 2011 at 18:33
  • $\begingroup$ 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. $\endgroup$
    – imz -- Ivan Zakharyaschev
    May 11, 2011 at 3:52
6
$\begingroup$

(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.)

Improve this answer
$\endgroup$
0
4
$\begingroup$

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 by Pierre Deransart and Jan Maluszynski.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Apparently, Prolog arose out of attribute grammars, so this view is what started logic programming. $\endgroup$
    – reinierpost
    Aug 7, 2014 at 11:28
1
$\begingroup$

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 !?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.