perhaps the most widely used.
The grammars that describe a typical language like Pascal or C are very
extensive. For an example, let us take a smaller language that is part of a larger
one.
Example 1.15
The rules for variable identifiers in C are
1. An identifier is a sequence of letters, digits, and underscores.
2. An identifier must start with a letter oran underscore.
3. Identifiers allow upper-and lowercase letters.
Formally, these rules can be described by a grammar.
In this grammar, the variables are , , , , and
. The letters, digits, and the underscore are terminals. A derivation of a0 is
The definition of programming languages through grammars is common and
very useful. But there are alternatives that are often convenient. For example, we
can describe a language by an accepter, taking every string that is accepted as
part of the language. To talk about this in a precise way, we will need to give a
more formal definition of an automaton. We will do this shortly; for the moment,
let us proceed in a more intuitive way.
An automaton can be represented by a graph in which the vertices give the
internal states and the edges transitions. The labels on the edges show what