15-312 Foundations of Programming Languages
Lecture 3: Abstract Syntax
In the previous lecture we discussed the definition of a
formal language by a grammar. We also saw how to represent
a grammar as a particular form of an inductive definition.
In this lecture we consider the representation of programming
language expressions, liberated from the particulars of the
concrete syntax of a language. Again, this will be given
in the form of an induction definition, but over a language
of terms rather than over a language of strings. We refer
to this term language as the abstract syntax of
a programming language, because it abstracts away from
concrete syntactic details.
One of the most critical aspects of abstract representation
of a programming language is the notion of a variable and its
scope. We discuss how to standardize these aspects of a language
description directly in the abstract syntax, leading to
the concept of higher-order abstract syntax. We also
investigate some properties of such a definition.