CODEWITHSUNDEEP
grammaryacclr-grammarlalrassociativity
user2373145
user2373145

Reputation: 363

Effect of yacc operator associativity declaration on expressions that have just a few tokens

When you have a grammar like this one:

B:  'a' A 'a'
|   'b' A 'b'
A:  'a' 'a'
|   'a'

The %right 'a' declaration causes aa.a not to be accepted because a shift happens instead of a reduce at '.', and %left 'a' doesn't accept neither aa.aa nor ba.ab because the parse always reduces at the dot.

It is not quite clear to me how to figure out what effect do associativity declarations have in such cases where the token ('a') is not being used as an operator straightforwardly.

Upvotes: 0

Views: 256

Answers (1)

rici
rici

Reputation: 241881

Why do you think LR(1) would be more intuitive? The grammar is not LR(1) so any LR(1) parser generator should report a shift/reduce conflict, just as an LALR(1) parser generator would.

Of course, yacc/bison is not a pure LALR(1) parser generator. If it resolves shift/reduce conflicts using a precedence/associativity declaration, then it suppresses the warning. That doesn't make the grammar unambiguous, though. One of the (many) issues with using precedence declarations is that it is no longer clear what language you are parsing. Silently ignoring a shift/reduce and statically resolving it in favour of one or the other action will produce a parser which recognizes some context-free language, but it is not the language described by the grammar.

None of that has to do with the LALR algorithm, though.

To answer your question: the algorithm bison/yacc uses to resolve shift/reduce conflicts is really simple.

  1. Every terminal mentioned in a precedence declaration is assigned a precedence value. All terminals mentioned in the same declaration have the same precedence, and have a higher precedence than any terminal mentioned in a previous declaration.

  2. Every production whose last terminal has a precedence value is assigned the same precedence value. (If the production includes a %prec TERMINAL modifier, that terminal is used instead of the last terminal in the production.

  3. If there is a shift-reduce conflict for a production with some lookahead symbol, and both the production and the lookahead symbol have precedence values, then the reduction is applied if the production's precedence is higher or if the precedences are equal and the precedence was assigned by a %left declaration. The shift is applied if the lookahead symbol's precedence is higher or if the precedences are equal and the precedence was assigned by a %right declaration.

That's it. Note that in the above algorithm, there is no mention of operators, which is actually not a concept in any form of LR parsing.

Upvotes: 1

Related Questions