2.6 Language Generation: Sentence Derivations

Consider the following a context-free grammar defined in BNF for simple English sentences:

As briefly shown here, grammars are used to generate sentences from the language they define. Beginning with the start symbol and repeatedly applying the production rules until the string contains no non-terminals results in a derivation— a sequence of applications of the production rules of a grammar beginning with the start symbol and ending with a sentence (i.e., a string of all terminals arranged according to the rules of the grammar). For example, consider deriving the sentence “the apple is there.” from the preceding grammar. The r_n parenthesized annotation on the right-hand side of each application indicates which production rule was used in the substitution:

The result (on the right-hand side of the ⇒ symbol) of each step is a string containing terminals and non-terminals that is called a sentential form. A sentence is a sentential form containing only terminals.

Peter Naur extended BNF for ALGOL 60 to make the definition of the production rules in a grammar more concise. While we discuss the details of the extension, called Extended Backus–Naur Form (EBNF), later (in Section 2.10), we cover one element of the extension, alternation, here since we use it in the following examples. Alternation allows us to consolidate various production rules whose left-hand sides match into a single rule whose right-hand side consists of the right-hand sides of each of the individual rules separated by the | symbol. Therefore, alternation is syntactic sugar, in that any grammar using it can be rewritten without it. Syntatic sugar is a term coined by Peter Landin that refers to special, typically terse syntax in a language that serves only as a convenient method for expressing syntactic structures that are traditionally represented in the language through uniform and often long-winded syntax. With alternation, we can define the preceding grammar, which contains 11 production rules with only 5 rules:

To differentiate non-terminals from terminals, especially when using grammars to describe programming languages, we place non-terminal symbols within the symbols < > by convention.⁴

Consider the following context-free grammar for arithmetic expressions for a simple four-function calculator with three available identifiers:

A derivation is called leftmost if the leftmost non-terminal is always replaced first in each step. The following is a leftmost derivation of 132:

A derivation is called rightmost if the rightmost non-terminal is always replaced first in each step. The following is a rightmost derivation of 132:

Some derivations, such as the next two derivations, are neither leftmost nor rightmost:

The following is a rightmost derivation of :

4. Interestingly, Chomsky and Backus/Naur developed their notion for defining grammars independently. Thus, the two notions have some minor differences: Chomsky used uppercase letters for non-terminals, the → symbol in production rules, and ∈ as the empty string; Backus/Naur used words in any case enclosed in <> symbols, ::=, and <empty>, respectively.