7
$\begingroup$

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^[]

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.

$\endgroup$

migrated from cstheory.stackexchange.com Apr 4 '12 at 8:51

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

  • $\begingroup$ 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). $\endgroup$ – vonbrand Feb 27 '13 at 2:18
4
$\begingroup$

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 ']'
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – zidarsk8 Apr 4 '12 at 14:40
  • $\begingroup$ 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 . $\endgroup$ – zidarsk8 Apr 4 '12 at 15:24
  • $\begingroup$ @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? $\endgroup$ – AProgrammer Apr 4 '12 at 15:33
  • $\begingroup$ 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. $\endgroup$ – zidarsk8 Apr 4 '12 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.