# 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):

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

Now let's say that an expression is:

1. Any id.
2. Any expression with the Postfix ^ operator.
3. Any expression with the Prefix ^ operator.
4. Any expression with . followed by id.
5. 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^[]

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.

## migrated from cstheory.stackexchange.comApr 4 '12 at 8:51

This question came from our site for theoretical computer scientists and researchers in related fields.

• I don't remember prefix ^ at all from my Pascal days. And constructions with ^^ definitely not. Pascal was carefully designed to be parsable by recursive descent, and LL(1) is a strict subset of LR(0). – vonbrand Feb 27 '13 at 2:18

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 '^'.

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 ']'

• The first grammar does not have any conflicts, but it's wrong since it does not produce a.b^.c . I just added it to show where i started from. – zidarsk8 Apr 4 '12 at 14:40
• There are two things wrong with your solution. First is that it does not produce all the good examples i have listed in my question, like a.b^.c second think is that it does not take the priorities into consideration, and so it would make a wrong expression tree . – zidarsk8 Apr 4 '12 at 15:24
• @zidarsk8, derivation of a.b^.c from the first grammar: EXP -> POST -> POST . id -> POST ^ . id -> POST . id ^ . id -> id . id ^ . id. Could you give an example of problematic expression showing the priority problem? – AProgrammer Apr 4 '12 at 15:33
• Your first version: postfix ^ has higher priority than the prefix ^ operator (that's not good). second version: prefix ^ has higher priority than the dot operator (also not good). the combined verions is the one that can't produce a.b^.c . The problem with priority is then how will it get parsed a.b^.c should be ((a.b)^).c ... and not (a.(b^)).c ... and ^b^ should be parsed (^b)^. Thank you for trying and sorry I keep turning down your solutions, but they don't work. – zidarsk8 Apr 4 '12 at 20:14