1

Language $L$ is specyfied by grammar : $(\{S,A,B\},\{c,d\},S,\{S \rightarrow SA, A \rightarrow Bc | \epsilon, B \rightarrow d\})$.

My task is to construct LR(1) parsing table for language $L^R$ (with, as far as I understand, is a reverse of language L). I know very well how to construct LR(1) parsing table, what I request for is that somebody explain to me how to deal with $L^R$ in this case.

Ariel Grabijas
  • 117

1 Answers1

1

I assume you ask for the meaning of $L^R$. $$ L^R = \{ w^R \mid w \in L \} $$ where the word reversal might be defined like \begin{align} \epsilon^R &= \epsilon \\ a^R &= a \quad (a \in \Sigma) \\ (a w)^R &= w^R a \quad (a \in \Sigma, w \in L) \end{align} The RHS reversed production rules should do the job: \begin{align} S &\to A S\\ A &\to cB \mid \epsilon \\ B &\to d \end{align}

mvw
  • 34,562
  • OK, but how that affect on constructing parsing table process? Does it change the productions some way, or anything else in grammar? – Ariel Grabijas Feb 06 '16 at 23:47
  • OK, now I understand. So I change the productions the way you made it and everything else stays the same. Thanks a lot, that's the answer I was looking for. – Ariel Grabijas Feb 06 '16 at 23:56
  • 1
    Like this the grammar for $L$ seems to produce words $w = S(dc)^$ and the modified grammar words $w = (cd)^S$. That is why I wonder how to replace $S$ with some terminal symbol. – mvw Feb 06 '16 at 23:59