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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Is the question wether this table is an LALR/SLR table or wether there is an LALR/SLR table for the same language? $\endgroup$– RaphaelCommented Apr 1, 2012 at 8:54
-
$\begingroup$ The question is 'can I deduce that it is also a table for LALR and SLR'. Seems perfectly clear to me. $\endgroup$– user207421Commented Apr 11, 2012 at 6:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.)
-
$\begingroup$ SLR(k) and LALR(k) are proper subsets of LR(k). Thus there are grammars that are LR(k) but not SLR(k) or LALR(k). $\endgroup$– uliCommented Apr 1, 2012 at 8:21
-
$\begingroup$ @uli, I agree with your remark but I miss its purpose. $\endgroup$ Commented Apr 1, 2012 at 8:29
-
$\begingroup$ 5min edit time for comments is too short, I was interrupted. Anyway, what I wanted to say is, that I am not convinced that just by glancing (or “just looking at” as the OP wrote) at the LR(1) table, without doing heavy computations I can tell that the grammar is not SLR(1) or LALR(1). So I was inclined to answer with “no”. $\endgroup$– uliCommented Apr 1, 2012 at 9:29
-
$\begingroup$ @uli, we agree for SLR(1) -- as long as we put "computing follow sets" in the heavy computation class -- but not for LALR(1). LALR(1) can be considered as LR(1) after merging states which share their items sets. $\endgroup$ Commented Apr 1, 2012 at 16:43
-
$\begingroup$ While “merging states” is not a heavy computation, it is certainly more than “just looking at the table”. For example when a dynamic programming algorithm has filled in its table. I can tell by looking at it what the value of the solution is. While recovering the whole solution from the table is little more than reading of certain entries, I woudn’t consider it “just look at the table”. $\endgroup$– uliCommented Apr 1, 2012 at 18:18