3
$\begingroup$

Consider the family of grammars $G_n,~n\geq2$. $$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$ $$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$

where multiple alternative right sides result from different values of $i,j$ while the terminal symbols $a_i$ and $b_i$ are not necessarily different from each other.

  1. Show that $G_n$ has exactly $n*2^{n-1}+n^2+1$ sets of LR(0) items.

  2. Examine if $G_n$ is LR(k) for some k.

The above exercise is similar to Exercise 4.6.7 (page 258) from the "Compilers: Principles, Techniques & Tools", 2nd Edition (a.k.a.Dragonbook) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.

I gave it much thought and also read chapter 4 of the book that is about Syntax Analysis but I still can't figure out how to prove this. Especially for question 2. I have no clue how to draw a conclusion about if this family of grammars can be parsed by an LR(k) parser.

For part 1., I think it could be suitable to use induction to prove that this is the exact number of states for any $n \geq 2$. At first, you have to construct the LR(0) states for $G_2,~n = 2$ and prove that the states correspond to the formula we have to prove. And it happens that way, as there are 9 LR(0) states which means that $\Rightarrow n*2^{n-1}+n^2+1=2*2^{2-1}+2^2+1=4+4+1=9$. If it is helpful, I could post the state diagram for $n=2$. Also, I don't know if this would help, but I proved that the productions for any $n$ is exactly $2n^2-n$.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You say you thought about it; care to share some of your thoughts? $\endgroup$ – Raphael♦ Dec 6 '12 at 6:08
  • $\begingroup$ Yes of course Raphael, and it was something I missed while writing the question. For (1), I thought about using induction and it seems it could work. Although I have trouble proofing the last step of the induction. For (2) as I said currently have no clue from where to start. Maybe, I could use the definition of LR(k) parser and see if the Gn family of grammars lives up to it. But I'm not sure that this is what is expected of me. $\endgroup$ – Ethan Dec 6 '12 at 10:16
  • 1
    $\begingroup$ Then for (1), you should give the proof as far as you have it. (Note that you can edit your question to do so.) $\endgroup$ – Raphael♦ Dec 6 '12 at 10:18
  • $\begingroup$ Do you understand the 'idea' behind this grammar, that is, why it causes the exponential blowup in the parse table? I for example see that your grammars are all $SLR(1)$ (but none are $LR(0)$), and I also see why you get exactly that many $LR(0)$ items. I suggest you have a close look at your $G_2$ automaton, and try to see what happens there - knowing why something is true is the first step towards proving it. $\endgroup$ – Alex ten Brink Dec 7 '12 at 19:54
  • $\begingroup$ @Alex by saying that you see why there are exactly that many $LR(0)$ items you mean that you can mathematically prove that? The family is $LR(1)$ and probably I could claim by that that they are consequently $LR(k)$. $\endgroup$ – Ethan Dec 15 '12 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.