patternMinor
From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?
Viewed 0 times
canthededucelalrslralsoparsingthatandfrom
Problem
There is this question I read somewhere but could not answer myself.
Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a table for LALR and SLR?
Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a table for LALR and SLR?
Solution
Trivially, yes: the grammar is extractible from the items.
Probably more in the spirit of the question. LALR(1) is easily extracted from LR(1): merge LR(1) items which correspond to the same LR(0) one and the grammar isn't LALR(1) if that process results in conflicts. (BTW this can be considered as a definition of LALR(1)).
SLR(1) is not so easy; you need to compute the follow sets to find out if there are conflicts. (SLR(1) is based on the LR(0) items like LALR(1), but it has "unneeded" conflicts due to the use of follow sets instead of the computation of look ahead one to choose which production to reduce.)
Probably more in the spirit of the question. LALR(1) is easily extracted from LR(1): merge LR(1) items which correspond to the same LR(0) one and the grammar isn't LALR(1) if that process results in conflicts. (BTW this can be considered as a definition of LALR(1)).
SLR(1) is not so easy; you need to compute the follow sets to find out if there are conflicts. (SLR(1) is based on the LR(0) items like LALR(1), but it has "unneeded" conflicts due to the use of follow sets instead of the computation of look ahead one to choose which production to reduce.)
Context
StackExchange Computer Science Q#938, answer score: 5
Revisions (0)
No revisions yet.