Concepts of Programming Languages

196 Chapter 4 Lexical and Syntax Analysis

The parser actions are informally defined as follows:

1. The Shift process is simple: The next symbol of input is pushed onto the
   stack, along with the state symbol that is part of the Shift specification
   in the ACTION table.


2. For a Reduce action, the handle must be removed from the stack.
   Because for every grammar symbol on the stack there is a state symbol,
   the number of symbols removed from the stack is twice the number
   of symbols in the handle. After removing the handle and its associated
   state symbols, the LHS of the rule is pushed onto the stack. Finally,
   the GOTO table is used, with the row label being the symbol that was
   exposed when the handle and its state symbols were removed from the
   stack, and the column label being the nonterminal that is the LHS of
   the rule used in the reduction.


3. When the action is Accept, the parse is complete and no errors were
   found.


4. When the action is Error, the parser calls an error-handling routine.

Although there are many parsing algorithms based on the LR concept, they

differ only in the construction of the parsing table. All LR parsers use this same

parsing algorithm.

Perhaps the best way to become familiar with the LR parsing process is

through an example. Initially, the parse stack has the single symbol 0, which

Figure 4.5

The LR parsing table
for an arithmetic
expression grammar

Action Goto

id + *

S5

S5

S5

S5

S4

S4

S4

S4

0 1 2 3 4 5 6 7 8 9

10

11

S6

R2 S7

R4 R4

State ()$ ETF

R6 R6

S6

R1

R3

R5

R2

R4

R6

S11

R1

R3

R5

R4

R6

R1

R3

R5

R3

R5

accept

R2

S7

(^123)
(^23)
3
8
9
10