reduce reduce and shift reduce error in LALR grammar I have to write a grammar for Pascal, and there is just one thing that is causing problems. 

Lets say we have operators (sorted by priority from low to high):


Postfix ^.
Prefix ^.
[ ], and ., (same priority and left associative).
The only terminal is id, which is any lowercase letter.


Now let's say that an expression is:


Any id.
Any expression with the Postfix ^ operator.
Any expression with the Prefix ^ operator.
Any expression with . followed by id.
Any expression with [ and another expression and ].


Now I would like to know how can I make a LALR grammar without shift-reduce and reduce-reduce conflicts, OR if that can't be done how can I prove that it can't be done.

Some examples:

good:
a.b.c.d               
a.b^.c
^a.b^
a.b^^[c]^^.d.e        
^^a.b^.d.e^[]

bad:
a.^b.c


Without the prefix ^, this problem is easy to solve, but the prefix sign keeps getting me. Can anyone help? My solutions so far:

// this works without the prefix but it does not produce a.b^.c which is wrong.
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] | C . id;


So I thought that the prefix can only occur before the first dot, and between dots, there can only be a postfix ^ and brackets. So I came up with this:

A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] |id D;
D ::= id E;
F ::= E | F ^;
E ::= id | F . id;


But this causes 3 conflicts.
I don't see any problem with your first grammar and bison doesn't complain on the rendering I've done of it.

I (and bison) see one conflict in your second grammar (which doesn't describe the same language as the first BTW). After having seen id id id with a pending ^, you don't know if your last id and the ^ should be an F, or if you should keep together the three id forming an A which will be gathered with the '^'.



Edit after your comment:

A direct rendering of your rules:

EXP ::= id | EXP ^ | ^ EXP | EXP . id | EXP [ EXP ]


will be ambigous — and thus have conflict(s) — because you don't state if the prefix version of ^ has priority over the other (postfix) operators. I don't remember how it was in Pascal, but you can get both effects with

EXP ::= POST | ^ EXP
POST ::= id | POST ^ | POST . id | POST [ EXP ]


and

EXP ::= PRE | EXP ^ | EXP . id | EXP [ EXP ]
PRE ::= id | ^ PRE


Edit again: a mixed version corresponding to my understanding of what you ask in the comment (I continue to find this confusing and I consider the complexity of the grammar — with post operators given twice — as a hint it is so :-) )

EXP ::= PRE | POST2
POST2 ::= PRE '^' | POST2 '^' | POST2 '.' id | POST2 '[' EXP ']'
PRE ::= POST | '^' PRE
POST ::= id | POST '.' id | POST '[' EXP ']'