Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Shift reduce and reduce reduce conflicts

I'm having a hard time wrapping my head around this and need some help understanding shift reduce and reduce reduce conflicts. I have a grammar which I can't seem to understand why it's problematic. I could attach the grammar, but I want to learn how this really works.

First question, what type of parser does MGrammer create? As I understand it, shift reduce and reduce reduce conflicts depends on the kind of parser.

Second question, what signifies a reduce reduce conflict and what signifies a shift reduce conflict?

I know the basics of lexical analysis, and formal grammar but it's been a while since I worked with language design so any help here is much appropriated.

Update:

I'm working with a whitespace significant language and I'm wondering about the possibilities of doing this in MGrammar, will I need look-a-head to resolve ambiguities?

like image 373
John Leidegren Avatar asked Mar 24 '09 09:03

John Leidegren


1 Answers

Simple example:

if cond
    if cond2
        cmd
    else
        cmd2

Question: Where does the else belong to? For the human eye, the indentation says "to the second if" but that means nothing to a computer (except when using Python ;)). This is a shift/reduce conflict.

A elegant solution is to treat the else as a left-binding operator of the highest precedence (which makes it "hang" to the closest if).

A reduce/reduce conflict is an ambiguity. I have no good example handy but it means that there are paths in the grammar where one token could cause two rules to reduce at the same time and there is no additional information to decide which rule should take precedence.

[EDIT] The bison docs have an example for reduce/reduce.

like image 66
Aaron Digulla Avatar answered Nov 16 '22 22:11

Aaron Digulla