CS 3723
 Programming Languages 
   if-else & Ambiguity

Handling an Ambiguous if-else Grammar: This page is using simple Shift-Reduce Parsing. Here is the grammar and the corresponding shift-reduce parse table. (This table and the subsequent material was prepared by hand, and may contain mistakes.)

Grammar S-R Parse Table
P  −−>  L
L  −−>  L A   |  A
A  −−>  id = E ;  |
         if ( E ) A  |
         if ( E ) A  else A
E  −−>  E + T  |   E - T  |  T
T  −−>  T * S  |   T / S  |  S
S  −−>  F ^ S  |   F
F  −−>  ( E )  |  id

    |  id |  =  |  ;  | if  |else |  ^  | * / | + - |  (  |  )  |  $  |
----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 P  |     |     |     |     |     |     |     |     |     |     | acc |
 L  |  s  |     |     |     |     |     |     |     |     |     |  r  |
 A  |  s  |     |     |     | s/r |     |     |     |     |     |  r  |
 E  |     |     |  s  |     |     |     |     |  s  |     |  s  |  r  |
 T  |     |     |  r  |     |     |     |  s  |  r  |     |  r  |  r  |
 S  |     |     |  r  |     |     |  r  |  r  |  r  |     |  r  |  r  |
 F  |     |     |  r  |     |     |  s  |  r  |  r  |     |  r  |  r  |
 id |     |  s  |  r  |     |     |  r  |  r  |  r  |     |  r  |  r  |
 =  |  s  |     |     |     |     |     |     |     |     |     |     |
 ;  |  r  |     |     |  r  |  r  |     |     |     |     |     |  r  |
 if |     |     |     |     |     |     |     |     |  s  |     |     |
else|  s  |     |     |  s  |     |     |     |     |     |     |     |
 ^  |  s  |     |     |     |     |     |     |     |  s  |     |     |
* / |  s  |     |     |     |     |     |     |     |  s  |     |     |
+ - |  s  |     |     |     |     |     |     |     |  s  |     |     |
 (  |  s  |     |     |     |     |     |     |     |  s  |     |     |
 )  |  s  |     |     |  s  |     |  r  |  r  |  r  |     |  r  |  r  |
 $  |  s  |     |     |  s  |     |     |     |     |  s  |     |     |
----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

The following sentence gives the simplest example of the ambiguity of a simple grammar for it-then with optional else, as our grammar has.

The Sentence
if ( id ) if ( id - id ) id = id ; else id = id + id ;

Here is a trace of the S-R parse showing a fork at the point of the shift-reduce conflict. ("Conflict" meaning that it says "maybe shift", "maybe reduce".

The S-R Parse
Stack                                    Curr  Rest of Input                                    Action
(top at right)                           Sym
------------------------------------------------------------------------------------------------------
$                                        if    ( id ) if ( id - id ) id = id ; else id = id + id ; $ s
$ if                                     (     id ) if ( id - id ) id = id ; else id = id + id ; $   s
$ if (                                   id    ) if ( id - id ) id = id ; else id = id + id ; $      s
$ if ( id                                )     if ( id - id ) id = id ; else id = id + id ; $        r
$ if ( F                                 )     if ( id - id ) id = id ; else id = id + id ; $        r
$ if ( S                                 )     if ( id - id ) id = id ; else id = id + id ; $        r
$ if ( T                                 )     if ( id - id ) id = id ; else id = id + id ; $        r
$ if ( E                                 )     if ( id - id ) id = id ; else id = id + id ; $        s
$ if ( E )                               if    ( id - id ) id = id ; else id = id + id ; $           s
$ if ( E ) if                            (     id - id ) id = id ; else id = id + id ; $             s
$ if ( E ) if (                          id    - id ) id = id ; else id = id + id ; $                s
$ if ( E ) if ( id                       -     id ) id = id ; else id = id + id ; $                  r
$ if ( E ) if ( F                        -     id ) id = id ; else id = id + id ; $                  r
$ if ( E ) if ( S                        -     id ) id = id ; else id = id + id ; $                  r
$ if ( E ) if ( T                        -     id ) id = id ; else id = id + id ; $                  r
$ if ( E ) if ( E                        -     id ) id = id ; else id = id + id ; $                  s
$ if ( E ) if ( E -                      id    ) id = id ; else id = id + id ; $                     s
$ if ( E ) if ( E - id                   )     id = id ; else id = id + id ; $                       r
$ if ( E ) if ( E - F                    )     id = id ; else id = id + id ; $                       r
$ if ( E ) if ( E - S                    )     id = id ; else id = id + id ; $                       r
$ if ( E ) if ( E - T                    )     id = id ; else id = id + id ; $                       r
$ if ( E ) if ( E                        )     id = id ; else id = id + id ; $                       s
$ if ( E ) if ( E )                      id    = id ; else id = id + id ; $                          s
$ if ( E ) if ( E ) id                   =     id ; else id = id + id ; $                            s
$ if ( E ) if ( E ) id =                 id    ; else id = id + id ; $                               s
$ if ( E ) if ( E ) id = id              ;     else id = id + id ; $                                 r
$ if ( E ) if ( E ) id = F               ;     else id = id + id ; $                                 r
$ if ( E ) if ( E ) id = S               ;     else id = id + id ; $                                 r
$ if ( E ) if ( E ) id = T               ;     else id = id + id ; $                                 r
$ if ( E ) if ( E ) id = E               ;     else id = id + id ; $                                 s
$ if ( E ) if ( E ) id = E ;             else  id = id + id ; $                                      r
$ if ( E ) if ( E ) A                    else  id = id + id ; $         +-------------(fork!)   r or s
                                                                        |
                                                                        |
$ if ( E ) if ( E ) A else               id    = id + id ; $            +------->(s first choice)    s
$ if ( E ) if ( E ) A else id            =     id + id ; $              |                            s
$ if ( E ) if ( E ) A else id =          id    + id ; $                 |                            s
$ if ( E ) if ( E ) A else id = id       +     id ; $                   |                            r
$ if ( E ) if ( E ) A else id = F        +     id ; $                   |                            r
$ if ( E ) if ( E ) A else id = S        +     id ; $                   |                            r
$ if ( E ) if ( E ) A else id = T        +     id ; $                   |                            r
$ if ( E ) if ( E ) A else id = E        +     id ; $                   |                            s
$ if ( E ) if ( E ) A else id = E +      id    ; $                      |                            s
$ if ( E ) if ( E ) A else id = E + id   ;     $                        |                            r
$ if ( E ) if ( E ) A else id = E + F    ;     $                        |                            r
$ if ( E ) if ( E ) A else id = E + S    ;     $                        |                            r
$ if ( E ) if ( E ) A else id = E + T    ;     $                        |                            r
$ if ( E ) if ( E ) A else id = E        ;     $                        |                            s
$ if ( E ) if ( E ) A else id = E ;      $                              |                            r
$ if ( E ) if ( E ) A else A             $                              |                            r
$ if ( E ) A                             $                              |                            r
$ A                                      $                              |                            r
$ L                                      $                              |                            r
$ P                                      $                              |                          acc
                                                                        |
                                                                        |
$ if ( E ) if ( E ) A                    else  id = id + id ; $         +------>(r second choice)    r
$ if ( E ) A else                        id    = id + id ; $                                         s
$ if ( E ) A else id                     =     id + id ; $                                           s
$ if ( E ) A else id =                   id    + id ; $                                              s
$ if ( E ) A else id = id                +     id ; $                                                r
$ if ( E ) A else id = F                 +     id ; $                                                r
$ if ( E ) A else id = S                 +     id ; $                                                r
$ if ( E ) A else id = T                 +     id ; $                                                r
$ if ( E ) A else id = E                 +     id ; $                                                s
$ if ( E ) A else id = E +               id    ; $                                                   s
$ if ( E ) A else id = E + id            ;     $                                                     r
$ if ( E ) A else id = E + F             ;     $                                                     r
$ if ( E ) A else id = E + S             ;     $                                                     r
$ if ( E ) A else id = E + T             ;     $                                                     r
$ if ( E ) A else id = E                 ;     $                                                     s
$ if ( E ) A else id = E ;               $                                                           r
$ if ( E ) A else A                      $                                                           r
$ A                                      $                                                           r
$ L                                      $                                                           r
$ P                                      $                                                         acc

Here are the two parse trees corresponding to the two choices made during the parse. Which one is the "correct" one?

The Two Parse Trees
Using Shift at Choice Using Reduce at Choice
               P
               |
               L
               |
+--+-+--+---------------------+
|  | |  |                     A
|  | |  |                     |               
|  | |  | +--+----+----+----+------+-----------+
|  | |  | |  |    |    |    |      |           A
|  | |  | |  |    |    |    |      |           |      
|  | |  | |  |    |    |    |      |    +--+----+----+
|  | |  | |  |    E    |    A      |    |  |    E    |
|  | |  | |  |    |    |    |      |    |  |    |    |
|  | |  | |  | +--+-+  | +--+-+--+ |    |  | +--+-+  |
|  | E  | |  | E  | |  | |  | E  | |    |  | E  | |  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | T  | |  | T  | T  | |  | T  | |    |  | T  | T  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | S  | |  | S  | S  | |  | S  | |    |  | S  | S  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | F  | |  | F  | F  | |  | F  | |    |  | F  | F  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
if ( id ) if ( id - id ) id = id ; else id = id + id ;

               P
               |
               L
               |
+--+-+--+-----------+--------------+-----------+
|  | |  |           A              |           |
|  | |  |           |              |           | 
|  | |  | +--+----+----+----+      +           |
|  | |  | |  |    |    |    |      |           A
|  | |  | |  |    |    |    |      |           |      
|  | |  | |  |    |    |    |      |    +--+----+----+
|  | |  | |  |    E    |    A      |    |  |    E    |
|  | |  | |  |    |    |    |      |    |  |    |    |
|  | |  | |  | +--+-+  | +--+-+--+ |    |  | +--+-+  |
|  | E  | |  | E  | |  | |  | E  | |    |  | E  | |  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | T  | |  | T  | T  | |  | T  | |    |  | T  | T  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | S  | |  | S  | S  | |  | S  | |    |  | S  | S  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
|  | F  | |  | F  | F  | |  | F  | |    |  | F  | F  |
|  | |  | |  | |  | |  | |  | |  | |    |  | |  | |  |
if ( id ) if ( id - id ) id = id ; else id = id + id ;

Revision date: 2014-01-24. (Please use ISO 8601, the International Standard Date and Time Notation.)