4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – reinierpost
    Oct 6, 2014 at 16:32

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ When I went to college, programming language theory was all about parsing. I suppose it depends on what you mean by that term. $\endgroup$
    – reinierpost
    Oct 6, 2014 at 16:33
5
$\begingroup$

On top of jmad's answer I'll add that when talking about programming languages one usually distinguishes between concrete syntax and abstract syntax.

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.

Abstract syntax is the one a language theoretician is more concerned with. (It is also interesting inside the compiler internals.) The grammar rules are used more or less directly to express the abstract syntax trees, which means that parentheses are added implicitly to disambiguate whenever terms are written linearly.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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