CODEWITHSUNDEEP
yacccontext-free-grammar
A_Pumpkin
A_Pumpkin

Reputation: 51

Does association and precedence declarations in yacc solve the issues of an ambiguous grammar?

Let's say for example we have the following ambiguous grammar:

expr -> expr OP expr

expr -> ( expr )

expr -> NUM

OP -> +

OP -> -

OP -> *

OP -> /

What exactly will the declarations

%left + -

%left * /

do in yacc? Will they help the parser solve the ambiguity problem without having to change the grammar?

Upvotes: 0

Views: 111

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126418

The yacc precedence directives allow a programmer to specify in a limited way how to resolve shift/reduce conflicts in the grammar. Understanding precisely how they work (and how they implement "normal" precedence rules) requires a fairly good knowledge of how shift/reduce parsing works.

At a high level, shift/reduce parsing works by recognizing patterns that correspond to the RHS of rules in the input and "replacing" those patterns with a symbol denoting the LHS of the rule. The goal being to ultimately replace the entire input with a single symbol matching the top-level symbol of the grammar. In more detail, as it sees each symbol of input, it either shifts that symbol (reading it and pushing it on th stack) or it reduces a rule -- taking symbols that match the RHS of the rule off the stack and replacing them with a single symbol for the LHS. At any step of the way, if the symbols on the top of the stack match the RHS of any rule, the parser could either shift or reduce -- deciding which to do is essentially the whole job of parser construction that yacc does. When it can't decide (from the grammar), it reports a shift/reduce conflict. (there are also reduce/reduce conflicts which occur when the top of the stack matches the RHS of two different rules).

The way that precedence rules work is to provide a programmatic way of resolving these shift reduce conflicts -- the programmer can supply "precedence levels" for tokens and rules and whenever a shift/reduce conflict occurs, if both the token and the rule involved have a precedence level, the conflict will be resolved in favor of the rule with higher precedence.

When you use %left/%right directives, that sets the precedence levels for tokens. Rules get their precedence either from the first token in the RHS of the rule or from an explicit %prec directive.

With your grammar above, the tokens can have a precedence just fine, but there's a problem with the expr: expr OP expr rule. As it has no token on the RHS (just non-terminals) it can't get a precedence that way, so you would need to give a precedenc with %prec but that doesn't work either because there is no single precedence to give to this rule.

If you split the rule into mulitple rules (get rid of OP and have a separate rule for each operator) then things work, as each rule can have a different precedence.

Upvotes: 3

Related Questions