Shift reduce and reduce reduce conflicts

Question

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?

Durning

Answer 1

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.

Cuda

OK, but what about white space and Markdown? I'm worried that Markdown is not possible to parse properly with mgrammar. There this mismatch of what's formal language and what's not. – Durning

In this case, you must turn whitespace into a token (instead of "ignoring" it). – Cuda

OK, it took me a while to figure this out, so a plain/text description of why shift/reduce and reduce/reduce conflicts happen is necessary. My problem was that I was looking at my grammar as if it was okay that it produced ambiguities. In reality those ambiguities produced parsing constructs that would leave the parser in a situation where it was unable continue by itself. This lead me to conclude that the reason why programming languages contains certain characters is to resolve these ambiguities in exactly one way. In my grammar, the white-space simply meant to many different things. – Durning