794
Modeling Arithmetic, Computation, and Languages
Suppose that a context-free grammar G describes a programming language.
The programmer uses the rules of G to generate legitimate strings of symbols,
that is, words in the language. Here we may think of a word as corresponding to
a program instruction. Thus, a word consists of various subwords, for example,
identifiers, operators, and key words for the language. The program instructions
are fed into the compiler for the language so that the program can be translated
into machine language code for the computer. The compiler must decide whether
each program instruction is legitimate in the language. In a sense, the compiler
has to undo the process that the programmer used to construct the statement; that
is, the compiler must start with the statement and decompose it to see whether it
follows the rules of the language. This really entails two questions: Are the subwords themselves legitimate strings? Is the program instruction a legitimate way
of grouping the subwords together?
Usually the set of legitimate subwords of a language can be described by a
regular expression, and then a finite-state machine can be used to detect the subwords; the lexical analysis or scanner portion of the compiler handles this phase of
compilation. (See Exercise 32 of Section 9.3 for the lexical analysis of ScrubOak.)
If all goes well, the scanner then passes the program instruction, in the form of a
string of legitimate subwords, to the syntax analyzer. The syntax analyzer determines whether the string is correct by trying to parse it (construct its parse tree).
Various parsing techniques, which we won’t go into, have been devised.
Given a string to be tested, one approach is to construct a tree by beginning with
the start symbol, applying productions (keeping an eye on the “goal”—the given
string) and ending with the goal string. This procedure is called top-down parsing. The alternative is to begin with the string, see what productions were used
to create it, apply productions “backwards,” and end with the start symbol. This
process is called bottom-up parsing. The trick to either approach is to decide
exactly which productions should be used.
PrACtiCe 66 Draw a parse tree for the word m34s in the grammar of Example 54.
■
example 60
Consider the context-free grammar G given by G = (V, V T , S, P) where
V = 5a, b, c, A, B, C, S6, V T = 5a, b, c6, and the productions are
S S B
B S C
A S abc
S S A
B S ab
C S c
Suppose we want to test the string abc. A derivation for abc is S 1 A 1 abc.
If we try a top-down parse, we might begin with
S
B
Then we have to detect that this will not work and try something else. If we try a
bottom-up parse, we might begin with
Modeling Arithmetic, Computation, and Languages
Suppose that a context-free grammar G describes a programming language.
The programmer uses the rules of G to generate legitimate strings of symbols,
that is, words in the language. Here we may think of a word as corresponding to
a program instruction. Thus, a word consists of various subwords, for example,
identifiers, operators, and key words for the language. The program instructions
are fed into the compiler for the language so that the program can be translated
into machine language code for the computer. The compiler must decide whether
each program instruction is legitimate in the language. In a sense, the compiler
has to undo the process that the programmer used to construct the statement; that
is, the compiler must start with the statement and decompose it to see whether it
follows the rules of the language. This really entails two questions: Are the subwords themselves legitimate strings? Is the program instruction a legitimate way
of grouping the subwords together?
Usually the set of legitimate subwords of a language can be described by a
regular expression, and then a finite-state machine can be used to detect the subwords; the lexical analysis or scanner portion of the compiler handles this phase of
compilation. (See Exercise 32 of Section 9.3 for the lexical analysis of ScrubOak.)
If all goes well, the scanner then passes the program instruction, in the form of a
string of legitimate subwords, to the syntax analyzer. The syntax analyzer determines whether the string is correct by trying to parse it (construct its parse tree).
Various parsing techniques, which we won’t go into, have been devised.
Given a string to be tested, one approach is to construct a tree by beginning with
the start symbol, applying productions (keeping an eye on the “goal”—the given
string) and ending with the goal string. This procedure is called top-down parsing. The alternative is to begin with the string, see what productions were used
to create it, apply productions “backwards,” and end with the start symbol. This
process is called bottom-up parsing. The trick to either approach is to decide
exactly which productions should be used.
PrACtiCe 66 Draw a parse tree for the word m34s in the grammar of Example 54.
■
example 60
Consider the context-free grammar G given by G = (V, V T , S, P) where
V = 5a, b, c, A, B, C, S6, V T = 5a, b, c6, and the productions are
S S B
B S C
A S abc
S S A
B S ab
C S c
Suppose we want to test the string abc. A derivation for abc is S 1 A 1 abc.
If we try a top-down parse, we might begin with
S
B
Then we have to detect that this will not work and try something else. If we try a
bottom-up parse, we might begin with