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.

Please note, I am asking about writing LALR parser, not writing rules for LALR parser.

What I need is...

...to mimic YACC precedence definitions. I don't know how it is implemented, and below I describe what I've done and read so far.


For now I have basic LALR parser written. Next step -- adding precedence, so 2+3*4 could be parsed as 2+(3*4).

I've read about precedence parsers, however I don't see how to fit such model into LALR. I don't understand two points:

  • how to compute when insert parenthesis generator

  • how to compute how many parenthesis the generator should create

I insert generators when the symbols is taken from input and put at the stack, right? So let's say I have something like this (| denotes boundary between stack and input):

  1. ID = 5 | + ..., at this point I add open, so it gives
  2. ID = < 5 | + ..., then I read more input
  3. ID = < 5 + | 5 ... and more
  4. ID = < 5 + 5 | ; ... and more
  5. ID = < 5 + 5 ; | ...

At this point I should have several reduce moves in normal LALR, but the open parenthesis does not match so I continue reading more input. Which does not make sense.

So this was when problem.

And about count, let's say I have such data < 2 + < 3 * 4 >. As human I can see that the last generator should create 2 parenthesis, but how to compute this? After all there could be two scenarios:

  • ( 2 + ( 3 *4 )) -- parenthesis is used to show the outcome of generator

  • or (2 + (( 3 * 4 ) ^ 5) because there was more input

Please note that in both cases before 3 was open generator, and after 4 there was close generator. However in both cases, after reading 4 I have to reduce, so I have to know what generator "creates".

share|improve this question
1  
I know that you emphasized that you are writing an LALR parser, but the problem is that operator precedence is handled by the way in which you write the rules. It happens by specifying how shift/reduce conflicts should be resolved (common with YACC), or by designing the rules in such a way that precedence is handled automatically (common when writing a custom parser). If you create a correct and working LALR parser, then precedence will be handled trivially by your rule definitions. –  Stargazer712 Dec 3 '12 at 21:33
    
@Stargazer712, the thing is, you can always rewrite the rules, but not always such grammar is nice to read. If I could add precedence (as in YACC) then later, as user of my parser, I could choose between "flat" grammar and precedence or rewriting rules. This is why I would like to mimic YACC and handle precedence not by rules, but by stating the priorities (as in YACC). –  greenoldman Dec 3 '12 at 22:00
1  
Right--and you're going about that the wrong way. Precedence is handled in YACC by defining a set of rules for how to handle shift/reduce conflicts. It has nothing to do with inserting parenthesis. –  Stargazer712 Dec 3 '12 at 22:43
    
@Stargazer712, I am asking exactly about that -- I need precedence as in YACC. I know it is defined by by precedence rules (not by grammar rules), I do not know how it is implemented. This is why I asked. Btw. those are not parenthesis for real, they are just internal markers. –  greenoldman Dec 3 '12 at 22:51

1 Answer 1

up vote 4 down vote accepted

Consider the following rules:

[1] E -> E + E
[2] E -> E * E
[3] E -> num

Without precedence, it would produce a shift/reduce error when encountering the second operator. The table looks something like this:

    num     +       *       $       E
0   S2      ---     ---     ---     1
1   ---     S3      S4      Accept  ---
2   ---     R3      R3      R3      ---
3   S2      ---     ---     ---     5
4   S2      ---     ---     ---     6
5   ---     R1/S3   R1/S4   R1      ---
6   ---     R2/S3   R2/S4   R2      ---

With precedence, you are saying which of "shift" and "reduce" you want in the case of conflicts.

  1. If the first operator has a lower precedence, you shift.
  2. If the first operator has a higher precedence, you reduce.
  3. If the operators have equal precedences, and both are
    • left associative, you reduce.
    • right associative, you shift.
    • otherwise, you fail.

Cleaning up the errors in the table, you get something like this:

    num     +       *       $       E
0   S2      ---     ---     ---     1
1   ---     S3      S4      Accept  ---
2   ---     R3      R3      R3      ---
3   S2      ---     ---     ---     5
4   S2      ---     ---     ---     6
5   ---     R1      S4      R1      ---
6   ---     R2      R2      R2      ---
share|improve this answer
    
OMG! This is solved so beautifully, I was already petrified by precedence parser, I thought I have to combine it with LALR :-). Thank you for explanation. –  greenoldman Dec 4 '12 at 8:55

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.