Concepts of Programming Languages

114 Chapter 3 Describing Syntax and Semantics

T

his chapter covers the following topics. First, the terms syntax and seman-

tics are defined. Then, a detailed discussion of the most common method of

describing syntax, context-free grammars (also known as Backus-Naur Form),

is presented. Included in this discussion are derivations, parse trees, ambiguity,

descriptions of operator precedence and associativity, and extended Backus-Naur

Form. Attribute grammars, which can be used to describe both the syntax and static

semantics of programming languages, are discussed next. In the last section, three

formal methods of describing semantics—operational, axiomatic, and denotational

semantics—are introduced. Because of the inherent complexity of the semantics

description methods, our discussion of them is brief. One could easily write an

entire book on just one of the three (as several authors have).

3.1 Introduction

The task of providing a concise yet understandable description of a program-

ming language is difficult but essential to the language’s success. ALGOL 60

and ALGOL 68 were first presented using concise formal descriptions; in both

cases, however, the descriptions were not easily understandable, partly because

each used a new notation. The levels of acceptance of both languages suffered

as a result. On the other hand, some languages have suffered the problem of

having many slightly different dialects, a result of a simple but informal and

imprecise definition.

One of the problems in describing a language is the diversity of the peo-

ple who must understand the description. Among these are initial evaluators,

implementors, and users. Most new programming languages are subjected to a

period of scrutiny by potential users, often people within the organization that

employs the language’s designer, before their designs are completed. These are

the initial evaluators. The success of this feedback cycle depends heavily on the

clarity of the description.

Programming language implementors obviously must be able to deter-

mine how the expressions, statements, and program units of a language are

formed, and also their intended effect when executed. The difficulty of the

implementors’ job is, in part, determined by the completeness and precision of

the language description.

Finally, language users must be able to determine how to encode software

solutions by referring to a language reference manual. Textbooks and courses

enter into this process, but language manuals are usually the only authoritative

printed information source about a language.

The study of programming languages, like the study of natural languages,

can be divided into examinations of syntax and semantics. The syntax of a

programming language is the form of its expressions, statements, and program

units. Its semantics is the meaning of those expressions, statements, and pro-

gram units. For example, the syntax of a Java while statement is

while (boolean_expr) statement