Syntax of programming languages

In this section, we will try to explain what syntax means and how it is important to programming.

Possible definitions of syntax

The definition of syntax is not as clear as one might think.

For instance, one possible definition of syntax would be ``the rules that create valid programs.'' That definition would cover a large part of what is usually considered semantics as well. In addition, syntax rules with this definition would be undecidable, making it impossible for the compiler to verify syntax. Usually when we think of syntax, we mean something that can be statically verified by the compiler.

Another possible definition of syntax would be ``the context-free grammar that generates potentially valid programs.'' This is the usual definition of syntax in traditional languages such as C and Java. As we shall see, this definition is not adequate for Common Lisp.

Usually, in traditional languages, each special form has its own rule or rules within the grammar of the language. For instance, a while statement in C would have the following grammar rule:

  < while-statement> ::= while ( < expression> ) < statement> ;
which means that in order to write a while statement in C, you have to write the word while followed by an opening parenthesis, followed by an expression, followed by a closing parenthesis, followed by a statement followed by a semicolon.

Syntax in Common Lisp

It is important to realize that Common Lisp has a two-level syntax. The lowest level corresponds to the second definition above, but in Common Lisp, it is trivial. In fact, it is so trivial that we can state the essence of it here: This syntax is so general that it allows programs that are obviously statically incorrect. In particular, it does not prevent numerous illegal versions of special forms.

The low-level syntax of Common Lisp is implemented by a function called read. That function is the parser for Common Lisp. Its only purpose is to verify the low-level syntax, and transform the text of the program into an internal representation. That internal representation uses standard Common Lisp data types such as symbols, numbers, and lists. In particular, a sequence of forms surrounded by parentheses is transformed into a Common Lisp list of the transformed elements of the sequence.

Not only does the read function use standard Common Lisp types for its internal representation. That internal representation is standardized by the language definition and available to the programmer. This is so important that every Common Lisp programmer, when looking at some code, thinks about lists and atoms, rather than about sequences of tokens or characters.

The second-level syntax of Common Lisp has rules about the format of the internal representation. For instance, the if special form has the following format:

  (if < test-form> < then-form> < else-form>)
or
  (if < test-form> < then-form>)
where test-form, then-form, and else-form are forms. But one should not think of this rule as being stated as sequences of tokens. Rather, one should think: ``An if special form is a list with three or four elements. The first element is the symbol if, the second, third and optionally the forth are all forms.''

The second-level syntax rules are checked by the compiler after the read function has transformed the program into the internal form. That part of the compiler is not restricted to context-free grammars or any other restrictions on sequences of symbols. It is free to traverse the internal representation in any order it needs, and as many times as necessary in order to verify syntax and generate code.

Perhaps the greatest advantage of the two-level syntax, and in particular of the standardized internal representation for programs, is that it makes it possible to have a powerful macro facility.

In ordinary programming languages such as C, the macro facility is very primitive, in that it replaces text by other text. This fact makes it possible for errors in definitions and uses of macros to generate mysterious defects that are extremely hard to find and debug.

In Common Lisp, on the other hand, the macro facility replaces forms by other forms. This fact makes it possible for the macro facility to be a useful mechanism for extending the syntax (i.e. the second-level syntax) of the language. Extending the syntax of the language is necessary in order to build an application-specific language on top of the base language.

In fact, large parts of a typical Common Lisp implementation are implemented as macros that translate special forms to simpler special forms.