# Grammar in formal languages versus programming language theory

Grammars seem to be used for different purposes. In formal languages, they are used to describe sequences of symbols. In programming language theory, they are used to describe objects in a term algebra (possibly enriched with some implicit, extra structure such as variable scoping rules). My question is, are these two kinds of grammars the same notation reused for unrelated purposes, or are they describing the same things? If they are unrelated, then do we have nomenclature to distinguish them?

For instance, the grammar

e ::= 1 | e e


could be describing a set of strings that includes "1", "1 1", and "1 1 1", or it could be describing a set of terms that includes "1", "1 1", "(1 1) 1", and "1 (1 1)".

• No. You can't magically pull brackets out of nowhere. What you can do is say that your grammars generate trees rather than (as grammars normally do) strings. See e.g. regular tree grammars. Oct 6, 2014 at 16:32

Programming language theory usually does not care about parsing: it does not address this problem. So when you have this grammar in programming language theory:

e ::= 1 | e e


it does mean the same thing as in formal language theory but programming language theory really only talks about the generated syntax trees. However it is much better to have a non-ambiguous grammar. For example in the lambda-calculus, the grammar is written like this:

$$M ::= x ∣ λx.M ∣ M M$$

and things like $L M N$ have several meanings as you pointed out. Usually the author/context makes it non-ambiguous like this: he says the application case is left-associative, authorizes parentheses, or sometimes changes $MM$ into $(MM)$ and says "we omit parentheses when unnecessary" or several other ways.

In conclusion it may generates the same string for different trees but programming language theory only applies on the latter.

• When I went to college, programming language theory was all about parsing. I suppose it depends on what you mean by that term. Oct 6, 2014 at 16:33

Concrete syntax is the one the programmer uses and when dealing with it one generally wants an unambiguous grammar, so often spurious elements such as semi-colons and begin-end keywords and the like are added to help the parser out.