2
$\begingroup$

I got one grammar:

re2: re1 $

re1: expr == expr | expr != expr | expr < expr | expr <= expr | expr >= expr | expr > expr | expr

expr: expr + term | expr - term | term

term: term * factor | term / factor | factor

factor: (expr) | num | id

num: (0|1|2|3|4|5|6|7|8|9)num | ε

id: (a|b|....|z|A|B|....|Z|)id | ε

Here are the FOLLOW sets:

FOLLOW(r2) = {}
FOLLOW(r1) = {$}
FOLLOW(expr) = {=,!,<,>,+,-,)}
FOLLOW(term) = FOLLOW(factor) = FOLLOW (id) = FOLLOW (num) = {=,!,<,>,+,-,),*,/}

Now this grammar clearly got reduce-reduce conflict from num: ε and id: ε because FOLLOW(num) ∩ FOLLOW(id) != empty set

Now let's say I fix the grammar by doing the following (I assume it is mistake in the grammar because (ε == ε) makes no sense):

num: (0|1|2|3|4|5|6|7|8|9)num | (0|1|2|3|4|5|6|7|8|9)
id: (a|b|....|z|A|B|....|Z|)id | (a|b|....|z|A|B|....|Z|) 

Now my question is, is this grammar SLR i.e can it be parsed by SLR parser? I know by building the parser I can find out but on exam I can not make the whole parser and then determine (I would lose lot of time).

$\endgroup$

migrated from stackoverflow.com Aug 25 '12 at 1:38

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ You seem to have a criterion for conflicts at hand. Why not use it on the modified grammar? I would also not discount the possibility that building the parsing table is the fastest approach (with enough practice) as it is purely mechanical and gives you a proof for the answer in either case. $\endgroup$ – Raphael Aug 27 '12 at 10:04
1
$\begingroup$

Your grammar indeed is ambiguous as it currently is, but not because the follow sets of two nonterminals have common elements. The ambiguity I see is that both re2 -> re1 -> expr -> term -> factor -> num -> ε and re2 -> re1 -> expr -> term -> factor -> id -> ε derive the empty word. If you require that num and id are both nonempty, then your grammar is SLR(1) (unless you do weird things to make num and id nonempty).

As an example where your 'follow test' does not work is the following:

S -> A c
S -> B c
A -> a
B -> b

The follow sets of A and B both contain c, but the grammar is SLR(1).

Unfortunately, the only three options I know to test whether a grammar is SLR(1) all have downsides: generating the table and doing the polynomial time test both take quite some time for an exam, and the third method, visual inspection of the grammar, is not very accurate. Finally, 'quickly' writing down the LR(0) automaton (by omitting the items in the states of the automaton) is possible but requires a lot of practice and is still somewhat inaccurate.

$\endgroup$

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.