Ambiguous grammar? Could the grammar be parsed by SLR parser?

Question

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).

Answer 1

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.