Section 9.5 Formal Languages
787
sentence 1 noun-phrase verb-phrase
1 article noun verb-phrase
1 a noun verb-phrase
1 a river verb-phrase
1 a river verb adverb
1 a river flows adverb
1 a river flows swiftly
A few other sentences making various degrees of sense, such as, “a walrus
flows loudly,” are also part of the language defined by this grammar. The difficulty
of specifying a grammar for English as a whole becomes more apparent when we
consider that a phrase such as, “time flies,” can be an instance of either a noun followed by a verb or of a verb followed by a noun. This phrase is “ambiguous” (see
Exercises 35 and 36 in this section).
Programming languages are less complex than natural languages, and their
syntax often can be described successfully using formal language notation.
example 54
A section of formal grammar to generate identifiers in some programming language could be presented as follows:
identifier S letter
identifier S identifier letter
identifier S identifier digit
letter S a
letter S b
(
letter S z
digit S 0
digit S 1
(
digit S 9
Here the set of terminals is 5a, b, … , z, 0, 1, … , 96 and identifier is the start
symbol.
example 55
A shorthand that can avoid a long listing of productions is called backus-naur
form (BNF). The productions of Example 54 can be given in BNF by three lines
(as in Example 7 of Chapter 3):
::= 0 0
::= a 0 b 0 c 0 … 0 z
::= 0 0 1 0 … 0 9