4
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 1 '12 at 7:39

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

  • $\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$ – Raphael Apr 1 '12 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$ – user207421 Apr 11 '12 at 6:32
5
$\begingroup$

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

$\endgroup$
  • $\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$ – uli Apr 1 '12 at 8:21
  • $\begingroup$ @uli, I agree with your remark but I miss its purpose. $\endgroup$ – AProgrammer Apr 1 '12 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$ – uli Apr 1 '12 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$ – AProgrammer Apr 1 '12 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$ – uli Apr 1 '12 at 18:18

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.