How can someone find what type of grammar for a given programming language?
Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.
How can someone find what type of grammar for a given programming language?
Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.
Programming languages are typically defined in several stages. A language in formal language theory is a set of strings, but that isn't a very useful concept to explain programming languages. The meaning of a source program is defined by several stages of translation; here are typical stages in the compilation of a translation unit:
There's no grammar type that describes valid programs in typical programming languages (unless you go for a formalism that can describe all decidable languages or more, such as unrestricted grammars). Many languages can be described by a context-free grammar up to stage 2, but there are exceptions (for example, C has feedback from variable binding to parsing because something like f(); foo * bar;
is valid in C89 if foo
is a variable but not if foo
is a type defined by typedef
). When you reach the binding stage, there has been work on general models for binding, but I'm not aware of any name for the kind of languages and transducers that correspond to context-free-grammars-plus-bindings. For typechecking, the sky's the limit: there are languages with Turing-complete type systems, and even the ones that aren't are typically very ad hoc and don't particularly fit any interesting category other than decidable.
Since the development of ALGOL60 one realised that a systematic approach to define the language was necessary. Backus-Naur-form was developed, meaning that most programming languages are basically context-free.
I say basically, because some parts of the language cannot be defined in that way. As an example, the declaration of a variable before it is used. On the nonexistence of a phrase structure grammar for ALGOL 60, Robert W. Floyd, Communications of The ACM - CACM , vol. 5, no. 9, pp. 483-484, 1962