Syntax and Semantics of Programming Languages

Every language, whether spoken or written for a computer, follows patterns. Some arrangements of words are acceptable and others are not. A programming language has its own version of this idea: certain arrangements of keywords, symbols, and names count as legal programs, and others are rejected before they can run. Before reading any rules, try a small prediction. Imagine a tiny language whose only legal sentences have the shape of a noun phrase followed by a verb phrase. Is 'cat sleeps' legal? Is 'the cat sleeps' legal? Keep your answers in mind, because the rest of this article shows how a precise description settles these questions without guessing.

The set of patterns that decides legality is called the syntax of the language, sometimes also called its grammar. Once you accept that syntax is a set of patterns, a practical question follows: if you want to hand the rules of a language to a human reader, a tool, or a compiler, how do you write them down precisely? Prose descriptions tend to be vague, and vagueness is a serious problem when the reader is a program. One standard answer to this question is a notation called BNF.

The source also points to a parallel development. At about the same time, the linguist Noam Chomsky independently arrived at an equivalent system for describing the grammar of natural language. Two groups, working on very different kinds of language, reached systems that express the same underlying idea. This is worth remembering: BNF is not a rule invented only for computers, but a way of describing patterns in any language.

Think about the English words noun, transitive verb, and prepositional phrase. Each names a kind of building block that can appear inside a sentence, not one particular word. The same is true for code: words such as statement, number, and while loop name kinds of pieces that can appear inside a Java program. Terms like these are called syntactic categories.

A rule in BNF specifies the structure of an item in a given syntactic category. It does this in terms of other syntactic categories, basic symbols of the language, or both. A rule therefore has two jobs. It names the category being defined, and it describes what an item of that category looks like. The diagram below labels the parts of a small rule written for a toy grammar of English. This rule is a generated illustration of the form, not a rule taken from a real language. Note that one common notation uses the separator ::=, while other notations draw the separator differently.

Read the rule from left to right. On the left of the separator sits the category being defined. Everything to the right describes the arrangement of parts that a legal item of that category must have. Here, the category verb-phrase may be the basic symbol sleeps or the basic symbol runs. The vertical bar separates the alternatives, so either form is legal. The separator is the point where the definition begins.

A single rule is only a partial picture. A grammar is a collection of rules, and each category on the right side of one rule is usually defined by another rule. To check whether a piece of text is legal, you repeatedly replace a category with the structure its rule gives, until nothing in brackets remains. The following toy grammar is generated for teaching purposes. It has four rules, one for each category, and the last two rules end in basic symbols rather than further categories.

The tree is the same information as the list of replacements, arranged so that each rule application is visible. Each step changed only one bracketed category, while the other pieces waited their turn. A reader who understands this process can look at any legal sentence and ask which rule produced each part of it. That question is the heart of parsing, which is covered in later work on this topic.

BNF is powerful, but the source is clear about its limits. BNF cannot express all possible syntax rules. A useful example is the requirement that a variable must be defined before it is used. A BNF rule can describe the shape of an assignment or the shape of a use of a name, but it cannot state that the use must come after a matching definition somewhere earlier in the program. Rules like that belong to a different stage of checking.

These limits are a reason to pair BNF with other descriptions, not a reason to dismiss it. BNF does express the basic structure of a language, and it plays a central role in the design of compilers.

Return to the opening question. With the toy grammar, 'cat sleeps' is not legal, because no sequence of replacements produces it: the noun phrase must begin with the word the. 'The cat sleeps' is legal, because the derivation traced earlier produces it. Notice that the rules settled both answers without anyone running the sentence, which is the practical value of writing syntax down precisely.