Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is there some standardized or widely accepted algorithm for picking up operators in shift/reduce conflicts in LALR parser? The question is naive, my problem is not with implementing my solution, but implementing the solution is already widely used.

For shift the operator is the next input token, for reduce, it depends -- I consider all already read symbols (for given production) declared as operators:

  • if there is one -- it is the operator
  • if there are more than one -- I report grammar error
  • if there is none I use the input token as operator

So for example:

E ::= E + E
E ::= E * E
E ::= num

in case of

E + E | * num

Considering first production I read +, and since it is the only one operator read I pick this one for reduce operator. * is the first token in input so it servers as shift operator.

But is my algorithm correct (i.e. the same as normally used for LALR parsers)? I am especially worried for the point when I have more than 1 operator in the read tokens.


Update

What I NOT am asking here

I don't ask how to resolve shift/reduce conflict once you have the operators. I don't ask how to set the precedence for operators.

What I am asking here

I ask how to extract operators from the "stream" of tokens. Let's say user set some precedence rules for +, - and *. The stack is: - E + E and input is E. Or the stack is E and input is *.

What is the operator for reduce in first case? And in the second? Why?

The stack is really entire right hand side of production.

share|improve this question
    
Although algorithms are defined as on-topic here, the design of languages and parsers tends to fall into the realm of computer science. You might get better answers on the Computer Science Stack Exchange. If you want this question moved, flag it for moderator review. Please do not cross-post it. –  Thomas Owens Dec 31 '12 at 22:36
1  
@ThomasOwens. thank you but no, for simple reason -- it would mean moving my question from published SE to hidden (beta) one. Once CS will be accepted, I will start using it. –  greenoldman Dec 31 '12 at 22:59
    
@ThomasOwens - I don't think this is really about the design of languages and parsers, I think it is about how to implement a basic LALR parser. I'm not even sure if it would be on topic on computer science (too basic, not really theoretical), but it seems clearly on topic here. –  psr Dec 31 '12 at 23:07
    
@psr, yes, exactly, I implemented all parts "by the book" with exception of this one, because I didn't find any description. –  greenoldman Jan 1 '13 at 10:59
    
Might you be asking the following: suppose we have a shift-reduce conflict, say between shifting '*' and reducing "E * E", how do I determine the 'operator' of "E * E" so that I can apply the priorities that the user defined? In other words, are you having trouble unifying that you only define priorities between operators, while shift-reduce conflicts are conflicts between operators on one hand and productions on the other hand? –  Alex ten Brink Feb 1 '13 at 11:29
show 3 more comments

2 Answers

up vote 1 down vote accepted

Converted from a comment, first, a rephrasing of your question:

Suppose we have the following ambiguous grammar:

E ::= E + E
E ::= E * E
E ::= num

In the LR automaton, we will have the following shift-reduce conflict (among others):

E ::= E * E •, +
E ::= E • + E

As is common knowledge, reducing here will make '*' bind more tightly as '+' (as normal), while shifting will make '+' bind more tightly.

Parser generators such as Yacc and Bison allow the user to mark tokens as binding more tightly than other tokens. As normal, we say that '* > +'.

However, there seems to be a mismatch somewhere: the '>' we use above is an operator between two tokens, but the shift-reduce conflict is a conflict between a token and a production.

In Yacc and Bison, not just tokens but productions also have a priority. The user can mark tokens with priorities (as is normally done), and productions (that have not been given an explicit priority) have their priority inferred. The priority of a production is equal to the priority of the rightmost token in the production.

In "E ::= E * E", the rightmost token is '*', so in the shift reduce conflict above the priority of the reduction is '*', and the priority of the shift is '+', and as the priority of '*' is higher than '+', we decide to reduce rather than shift. As another example, the rightmost token of "A ::= a b B c d C D E" is 'd' (with only capitalized letters being nonterminals).

Adding "A ::= a b B c d C D E %prec a" to a production in Yacc and Bison explicitly gives that production the priority of 'a', but this is not normally done. Note that some productions may not have a rightmost token, or the priority between tokens is not defined, in which cases Yacc and Bison fall back to always shifting to resolve conflicts (Yacc and Bison always create a fully deterministic table, unless in GLR mode).

For completeness: the action with higher priority wins, so if the production has a higher priority than the token, we reduce instead of shifting. If priorities are equal, we look at associativity: left associativity means reducing, right associativity means shifting. 'nonassoc' is the third type of 'associativity', and it means an error: the shift/reduce conflict is resolved by removing both entries in the table, so the parser rejects inputs entering that state with that lookahead.

share|improve this answer
    
Very complete answer, thank you :-). –  greenoldman Feb 10 '13 at 13:07
add comment

Well, let me grab the first parser I can find that tries to resolve this type of issue automatically and see what it does. According to http://www.haskell.org/happy/doc/html/sec-conflict-tips.html their default is to choose the shift over a reduce if there is a shift-reduce conflict, and to choose the first rule in the grammar file if there is a reduce-reduce conflict. (They consider reduce-reduce conflicts to be more serious problems.)

share|improve this answer
    
Thank you, but it is not I am asking for. I am not asking how to resolve shift/reduce conflict, but how to extract operators for reduce (in general way). Say you define * to have higher priority than + and it is pretty easy to point out those operators for given productions. But how they are really extracted? Especially what is the operator in case of E2 ::= E1 where both are non-terminals? I assume it is is next token from input, but is it assumed this way in majority of LALR parsers? –  greenoldman Jan 1 '13 at 16:38
1  
@greenoldman I'm not positive what you mean. Taking a random guess, the usual trick to get * to have higher precedence than + in a grammar is to have nonterminals of different precedence. For instance theory.stanford.edu/~amitp/yapps/yapps-doc/node2.html has a calculator example with a distinction between expr (can extend if you join with + or -) and factor (can extend if joined by * or /). The resulting parse tree is never ambiguous - multiplicative operators always bind more tightly in the parse tree than additive ones. –  btilly Jan 1 '13 at 22:10
    
I updated the question, you covered both ends of the problem, the remaining problem is how to tell "I will take this operator and not this one for resolving conflict". For example you have E+ on the stack and - as input. Do you take + twice for reduce and shift, or will you take + for reduce and - for shift? Why exactly? I described how I extract them but I am not sure if this is widely accepted. –  greenoldman Jan 2 '13 at 10:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.