Summary 197
represents state 0 of the parser. The input contains the input string with an
end marker, in this case a dollar sign, attached to its right end. At each step,
the parser actions are dictated by the top (rightmost in Figure 4.4) symbol of
the parse stack and the next (leftmost in Figure 4.4) token of input. The cor-
rect action is chosen from the corresponding cell of the ACTION part of the
parse table. The GOTO part of the parse table is used after a reduction action.
Recall that GOTO is used to determine which state symbol is placed on the
parse stack after a reduction.
Following is a trace of a parse of the string id + id * id, using the LR pars-
ing algorithm and the parsing table shown in Figure 4.5.
The algorithms to generate LR parsing tables from given grammars, which
are described in Aho et al. (2006), are not overly complex but are beyond
the scope of a book on programming languages. As stated previously, there
are a number of different software systems available to generate LR pars-
ing tables.
SUMMARY
Syntax analysis is a common part of language implementation, regardless of the
implementation approach used. Syntax analysis is normally based on a formal
syntax description of the language being implemented. A context-free gram-
mar, which is also called BNF, is the most common approach for describing
syntax. The task of syntax analysis is usually divided into two parts: lexical
analysis and syntax analysis. There are several reasons for separating lexical
analysis—namely, simplicity, efficiency, and portability.
Stack Input Action
0 id + id * id $ Shift 5
0id5 + id * id $ Reduce 6 (use GOTO[0, F])
0F3 + id * id $ Reduce 4 (use GOTO[0, T])
0T2 + id * id $ Reduce 2 (use GOTO[0, E])
0E1 + id * id $ Shift 6
0E1+6 id * id $ Shift 5
0E1+6id5 * id $ Reduce 6 (use GOTO[6, F])
0E1+6F3 * id $ Reduce 4 (use GOTO[6, T])
0E1+6T9 * id $ Shift 7
0E1+6T9*7 id $ Shift 5
0E1+6T9*7id5 $ Reduce 6 (use GOTO[7, F])
0E1+6T9*7F10 $ Reduce 3 (use GOTO[6, T])
0E1+6T9 $ Reduce 1 (use GOTO[0, E])
0E1 $ Accept
