Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
They are context-free grammars. –  Andrej Bauer Dec 28 '12 at 8:43

2 Answers 2

up vote 5 down vote accepted

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:

  1. Lexical analysis, i.e. splitting the program into tokens. Token recognition is often performed by finite automata, but not always (e.g. languages with nested comments need a stack at this stage).
  2. Parsing. This stage is usually described by a context-free grammar. Although lexical analysis could be described by that same context-free grammar, this would typically result in an extremely complex and slow-to-parse grammar, which is why the two stages are separate.
  3. Variable binding, i.e. associating the different uses of the same name to mean the same variable. In particular, in most languages, variables need to be declared before use. This cannot be described by a context-free grammar.
  4. Typechecking, if the language has a static type system. There is a lot of variability here.
  5. After that point, subsequent compilation stages tend not to have failure cases. There are exceptions, for example some languages regulate recursive definitions at a late stage.

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.

share|improve this answer
    
"There is no grammar type that describes valid programs in typical PL". AFAIK, unrestricted grammars could, but they are not convenient to use (you need to describe long distance relationships as combination of local one). Then you have other formalisms, like two-level grammars (aka W-grammar, used for Algol68, which is an extension of the rewriting system) or attribute grammars which have the power needed. –  AProgrammer Jan 1 '13 at 9:46
    
@AProgrammer Ok, I should have said “no grammar type that can describe less than decidable languages”. –  Gilles Jan 1 '13 at 14:05

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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