Hi Luis -

Since I'm currently implementing an LR(1) parser generator (similar to Menhir, but in F#), I think I may be able to shed a little more light on this.

First, I don't think that the involvement of the start symbol matters here, and the use of left recursion shouldn't be an issue, as it's problematic only in LL (or other top-down) parsers.

I believe that the problem here is the mutual definition of "start" and "expr" in your grammar, which introduces the possibility of multiple interpretations (i.e., multiple parse trees) for the same input.

Here's an example: let's assume that some input to the generated parser has started with an ID followed by an ARROW. Now, in accordance with rule containing ID and ARROW, the parser wants to see a "start" (which we'll call the "inner 'start'"). But if the next token seen by the parser is an LPAREN, bingo! - we're already in trouble.

Should the parser give ownership of that LPAREN to an "expr" underneath the inner "start" (the shift case), or should it use only the empty definition of "expr" to satisfy the requirement for a "start", and give ownership of the LPAREN to an "expr" at a higher level (the reduce case)? Both options make perfect sense, as far as an LALR(1) or LR(1) parser generator is concerned.

Using curly braces to enclose "start"s and square brackets to enclose "expr"s, alternate parse trees for input consisting of ID, ARROW, LPAREN, and RPAREN can be denoted as follows:

{ [ ID ARROW { [ [ ] LPAREN RPAREN ] } ] } (* shift *)
{ [ [ ID ARROW { [ ] } ] LPAREN RPAREN ] } (* reduce *)

Despite the age of this thread, hopefully someone out there will find this post helpful.

- Pete

I think I can explain the problem:

A parser is more or less just a stack-machine: you've got a stack with symbols, a transition table telling you for your look-ahead (normally the very next symbol in the input) and the topmost stack-symbol what you should do next:

- shift a new symbol on the stack
or
- reduce the stack (pop the topmost item)

Yacc produces the transition table and the conflict that it gives you means that for some stack-symbol if you see LPAREN next that it found two different actions - either shift a new symbol or reduce the current one.

Now you have to understand that the start - symbol is special - because reducing this means the compiler has completed parsing.

I don't know exactly how fsyacc is implementet but the "expr LPAREN RPAREN" gives you some headache because more or less you don't know if you should continue replacing expr or if you should continue parsing LPAREN (the rule is called to be left recursive) so normally a preprocessor takes this rule and removes this left-recursive rules by replacing them and adding new ones.

Now I guess this makes the problems in your case.

BTW: I don't think the grammar you gave us is complete - no matter what you do you never get to a point in a syntax-tree where the node is labled only with terminals

Interestingly, I just found out yacc has the same behavior.

I must be missing something really obvious... haven't used parser generators in a while.