CS 3723/3721 -- Shift-Reduce Parser

CS 3723/3721 Programming Languages
Shift-Reduce Parser

Overview: Parsers are algorithms and programs that will unravel the syntax of a sentence described by a formal grammar. Most parsers will not handle an arbitrary grammar, but place limitations on the form of grammar allowed. These parsers go through the motions of building a parse tree without actually generating the tree. While the parse is going on, extra code can carry a variety of tasks related to translating the source into some other form.

Initial Recitation work:

Consider the following grammar:


        S  --->  E                      ("S" is the start symbol)
        E  --->  E "+" T  |  T
        T  --->  T "*" F  |  F
        F  --->  "(" E ")"  |  id

Use the following shift-reduce table for this grammar:


     |  id |  *  |  +  |  (  |  )  |  $  |
-----+-----+-----+-----+-----+-----+-----+
  S  |     |     |     |     |     | acc |  ( "s" means "shift")
  E  |     |     |  s  |     |  s  |  r  |
  T  |     |  s  |  r  |     |  r  |  r  |  ( "r" means "reduce")
  F  |     |  r  |  r  |     |  r  |  r  |
  id |     |  r  |  r  |     |  r  |  r  |  ( "acc" means "accept")
  *  |  s  |     |     |  s  |     |     |
  +  |  s  |     |     |  s  |     |     |    
  (  |  s  |     |     |  s  |     |     |
  )  |     |  r  |  r  |     |  r  |  r  |
  $  |  s  |     |     |  s  |     |     |
-----+-----+-----+-----+-----+-----+-----+

In the table above, what do the blank entries mean?
Carry out the shift-reduce parse of the following sentence, showing the stack, current symbol, remaining symbols, and next action to take at each stage. (This sentence has the extra artifical symbol $ stuck in at the beginning and the end.)
```
     $ ( id + id ) * id $
```
(Remember that you should initially shift the starting $.)
What would happen if you started processing the following input string? $ id * + id $

Partial Answers:

These represent error entries (an error condition).


Stack (top at right)      Curr    Rest of Input       Action
                          Sym
--------------------------------------------------------------------------
$                         (       id + id ) * id $    shift
$  (                      id      + id ) * id $       shift
$  ( id                   +       id ) * id $         reduce: F ---> id
$  ( F                    +       id ) * id $         reduce: T ---> F
$  ( T                    +       id ) * id $         reduce: E ---> T
$  ( E                    +       id ) * id $         shift
$  ( E  +                 id      ) * id $            shift
$  ( E  +  id             )       * id $              reduce: F ---> id
$  ( E  +  F              )       * id $              reduce: T ---> F
$  ( E  +  T              )       * id $              reduce: E ---> E + T
$  ( E                    )       * id $              shift
$  ( E )                  *       id $                reduce: F ---> ( E )
$  F                      *       id $                reduce: T ---> F
$  T                      *       id $                shift
$  T  *                   id      $                   shift
$  T  *  id               $                           reduce: F ---> id
$  T  *  F                $                           reduce: T ---> T * F
$  T                      $                           reduce: E ---> T
$  E                      $                           reduce: S ---> E
$  S                      $                           accept

In this case the parse would get to a * on the top of the stack and a + as the current symbol. The corresponding entry in the table is blank (an error entry).

New example without an answer:


        S ---> b M b              ("S" is the start symbol)
        M ---> ( L
        M ---> a
        L ---> M a )


           |  b  |  a  |  (  |  )  |  $   |
      -----+-----+-----+-----+-----+------+
        S  |     |     |     |     |  acc |     ( "s" means "shift")
        M  |  s  |  s  |     |     |      |
        L  |  r  |  r  |     |     |      |     ( "r" means "reduce")
        b  |     |  s  |  s  |     |  r   |
        a  |  r  |  r  |     |  s  |      |     ( "acc" means "accept")
        (  |  s  |  s  |  s  |     |      |
        )  |  r  |  r  |     |     |      |

Carry out the shift-reduce parse of the following sentence, showing the stack, current symbol, remaining symbols, and next action to take at each stage. (This sentence has the extra artifical symbol $ stuck in at the beginning and the end.)
```
     $ b ( ( a a ) a ) b $
```
(Remember that you should initially shift the starting $ and then shift the next symbol.)
Give the resulting parse tree.

What to turn in to the recitation instructor: Turn in answers to the last two a and b items above (those without answers provided).

Key ideas: The shift-reduce parser using a stack is a common strategy. The version shown here is relatively simple, but there are much more sophisticated versions called LR parsers (text, pages 170-174), and LALR parsers (beyond the scope of the course). These parsers are the most capable and are the ones usually employed for real compilers. An LR parser handles the most complex grammar possible using a simple left-to-right scan, and it can determine a syntax error at the earliest possible point.

Revision date: 2003-09-12. (Use ISO 8601, an International Standard.)

CS 3723/3721 Programming Languages Shift-Reduce Parser

CS 3723/3721 Programming Languages
Shift-Reduce Parser