Heapster: Resolve shift/reduce conflict warnings in parser

[RyanGlScott]

One unfortunate consequence of #1792 (which wasn't noticed until after it landed) is that it introduced a new warning when compiling Verifier.SAW.Heapster.CruUtil:

shift/reduce conflicts:  9

This is because of the new '-' expr production. To see where exactly the shift/reduce conflicts lie, you can run the following command:

$ cabal run happy -- -agc --strict heapster-saw/src/Verifier/SAW/Heapster/Parser.y -idetailed-info.txt

I've attached the generated detailed-info.txt file. The relevant bits are this at the top:

state 90 contains 9 shift/reduce conflicts.

Here is state 90:

State 90

    expr -> expr . '+' expr                             (rule 24)
    expr -> '-' expr .                                  (rule 25)
    expr -> expr . '*' expr                             (rule 26)
    expr -> expr . 'orsh' expr                          (rule 37)
    expr -> expr . ';' expr                             (rule 38)
    expr -> expr . 'or' expr                            (rule 49)
    expr -> expr . '==' expr                            (rule 60)
    expr -> expr . '/=' expr                            (rule 61)
    expr -> expr . '<u' expr                            (rule 62)
    expr -> expr . '<=u' expr                           (rule 63)

    ')'            reduce using rule 25
    ']'            reduce using rule 25
    '}'            reduce using rule 25
    '>'            reduce using rule 25
    ':'            reduce using rule 25
    ';'            shift, and enter state 98
            (reduce using rule 25)

    ','            reduce using rule 25
    '+'            shift, and enter state 99
            (reduce using rule 25)

    '*'            shift, and enter state 100
            (reduce using rule 25)

    '-o'           reduce using rule 25
    '=='           shift, and enter state 101
            (reduce using rule 25)

    '/='           shift, and enter state 102
            (reduce using rule 25)

    '<u'           shift, and enter state 103
            (reduce using rule 25)

    '<=u'          shift, and enter state 104
            (reduce using rule 25)

    'or'           shift, and enter state 105
            (reduce using rule 25)

    'orsh'         shift, and enter state 106
            (reduce using rule 25)

    %eof           reduce using rule 25

Where rule 25 is:

expr -> '-' . expr                                  (rule 25)

An example of the ambiguity is:

- 42 + 27

There are two possible ways to parse this:

• Scenario A: (- 42) + 27
• Scenario B: - (42 + 27)

How is this determined? At some point, the parser gets to the following state:

• Parse stack: - 42
• Next tokens: + 27 ...

Scenario A:

1. REDUCE - 42 to exp:
   • Parse stack: exp
   • Next tokens: + 27 ...
2. SHIFT:
   • Parse stack: exp +
   • Next tokens: 27 ...
3. SHIFT:
   • Parse stack: exp + 27
   • Next tokens: ...
4. REDUCE exp + 27 to exp:
   • Parse stack: exp
   • Next tokens: ...

Scenario B:

1. SHIFT:
   • Parse stack: - 42 +
   • Next tokens: 27 ...
2. SHIFT:
   • Parse stack: - 42 + 27
   • Next tokens: ...
3. REDUCE 42 + 27 to exp:
   • Parse stack: - exp
   • Next tokens: ...
4. REDUCE - exp to exp:
   • Parse stack: exp
   • Next tokens: ...

Whenever there is a shift/reduce conflict, happy defaults to shifting. As a result, happy picks Scenario B. This is arguably not what we want, as we would like - to bind more tightly than other operators.

One way to fix this would be to use happy's precedence pragmas. An example of how to do this can be found here.

[eddywestbrook]

I agree that scenario A seems like the correct answer, and using precedence pragmas seem like a good way to affect this answer