Grammars seem to be used for different purposes. In formal languages, they are u

Question

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

Explanation / Answer

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?MM

and things like LMN 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.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.