[Y-Indology] Ashtadyayi and Backus/Naur grammars

[Guest guest]

BNF, or Backus Normal Form, is one standardized way of writing

context-free grammars.

Context-free grammars recognize context-free, or algebraic languages,

the second

level of Chomsky's hierarchy of formal languages (the first level is

regular or rational

languages, recognized by finite-state automata; the third level is

context-sensitive

languages). Context free languages are enough to represent the

recursive structure

of well-parenthesized formulae such as computer programs. They are

sufficient to describe

the syntax of natural languages as well, except for special constructs

like "respectively"

or the so-called hippopotamus sentences in Dutch, for which mildly

context-sensitive

grammars must be used.

 

Backus invented BNF for describing the syntax of FORTRAN. Later, it was

recognized that

Naur invented a similar notation, and BNF now means "Backus-Naur form".

 

Paa.nini did not just give a formal grammar for Sanskrit syntax, he

invented a

syntactic meta-notation which is of the same power as context-free

grammars. A few

years before Chomsky :-)

 

Actually, it has been advocated that BNF should be called

"Panini-Backus form".

See Ingerman P. Z. "Panini-Backus form suggested", Comm. ACM 10:3

(1967) p. 137.

 

GH