0

I'm working on the parser component of my Tiger compiler in SML using ML-Yacc. I cannot find any glaring problems with my grammar file (I've used priority rules to resolve all shift-reduce conflicts) but it seems to never reduce using the second and third rules of lvalue, which I've specified as follows:

lvalue : ID                       ()
       | lvalue DOT ID            ()
       | lvalue LBRACK exp RBRACK ()

The grammar for exp is:

exp : lvalue                      ()
    | INT                         ()
    | ID LBRACK exp RBRACK OF exp ()
    | lvalue ASSIGN exp           ()
    ...

When trying to parse a[0] := 5, I expect it to reduce using the fourth exp rule (where the lvalue is lvalue LBRACK exp RBRACK). Instead, Yacc finds a syntax error and substitutes ASSIGN for OF and parses using the third exp rule.

Similar problems occur with lvalue DOT ID.

MattDs17
  • 401
  • 1
  • 4
  • 20

1 Answers1

0

I solved my problem as I was typing the question up, so I'll answer my question in case anybody else runs into this problem.

The issue (I think) is that the grammar for lvalue is left-recursive. I thought Yacc might throw a warning about it, but it didn't - maybe the precedence rules I set hid the problem. Left-factoring the grammar fixed the problem:

edit: Left-factoring just happened to resolve the problem, but left-recursion was not the issue. See comment below and a similar linked question.

lvalue : ID lvalue'                 ()

lvalue' :                           ()
        | DOT ID lvalue'            ()
        | LBRACK exp RBRACK lvalue' ()
MattDs17
  • 401
  • 1
  • 4
  • 20
  • 1
    Left recursion is not the problem, exactly. Left-recursion is not usually problematic for bottom-up parsers. The problem is the `ID` in `ID LBRACK exp RBRACK OF exp`. If it had been `lvalue LBRACK...`, there would have been no problem. But as written, the parser cannot know whether or not to reduce `ID` to `lvalue`. Appel notes this issue in his textbook (or at least one of the language versions of the textbook) and I discuss some possible solutions with `bison` [here](https://stackoverflow.com/a/26977277/1566221) (starting with the paragraph "The shift/reduce conflict in state 1...") – rici Sep 03 '17 at 05:38
  • @rici After making my response I started to doubt whether left recursion could actually be the problem. Thank you for the clarification - I considered editing the OP to ask about it but wasn't sure how much visibility it would get. – MattDs17 Sep 03 '17 at 06:17