116 Chapter 3 Describing Syntax and Semantics
* mult_op
count identifier
+ plus_op
17 int_literal
; semicolonThe example language descriptions in this chapter are very simple, and most
include lexeme descriptions.3.2.1 Language Recognizers
In general, languages can be formally defined in two distinct ways: by recognition
and by generation (although neither provides a definition that is practical by itself
for people trying to learn or use a programming language). Suppose we have a
language L that uses an alphabet of characters. To define L formally using the
recognition method, we would need to construct a mechanism R, called a recogni-
tion device, capable of reading strings of characters from the alphabet . R would
indicate whether a given input string was or was not in L. In effect, R would either
accept or reject the given string. Such devices are like filters, separating legal
sentences from those that are incorrectly formed. If R, when fed any string of
characters over , accepts it only if it is in L, then R is a description of L. Because
most useful languages are, for all practical purposes, infinite, this might seem like
a lengthy and ineffective process. Recognition devices, however, are not used to
enumerate all of the sentences of a language—they have a different purpose.
The syntax analysis part of a compiler is a recognizer for the language the
compiler translates. In this role, the recognizer need not test all possible strings
of characters from some set to determine whether each is in the language. Rather,
it need only determine whether given programs are in the language. In effect
then, the syntax analyzer determines whether the given programs are syntactically
correct. The structure of syntax analyzers, also known as parsers, is discussed in
Chapter 4.3.2.2 Language Generators
A language generator is a device that can be used to generate the sentences of
a language. We can think of the generator as having a button that produces a
sentence of the language every time it is pushed. Because the particular sentence
that is produced by a generator when its button is pushed is unpredictable, a
generator seems to be a device of limited usefulness as a language descriptor.
However, people prefer certain forms of generators over recognizers because
they can more easily read and understand them. By contrast, the syntax-checking
portion of a compiler (a language recognizer) is not as useful a language descrip-
tion for a programmer because it can be used only in trial-and-error mode. For
example, to determine the correct syntax of a particular statement using a com-
piler, the programmer can only submit a speculated version and note whether