edited by
12,726 views
40 votes
40 votes

The grammar $ S \to aSa \mid bS \mid c$ is 

  1. LL(1) but not LR(1)
  2. LR(1) but not LL(1)
  3. Both LL(1) and LR(1)
  4. Neither LL(1) nor LR(1)
edited by

2 Answers

Best answer
8 votes
8 votes
The $\textsf{LL(1)}$ parsing table for the given grammar is:

$\begin{array}{|c|c|c|} \hline
& a&b&c \\ \hline
S& S\to aSa & S\to b & S \to c \\ \hline
\end{array}$

For any given input symbol $a,b$ or $c,$ the parser has a unique move from the start and the only state – so no conflicts.

As there is no conflict in $\text{LL(1)}$ parsing table, the given grammar is $\textsf{LL(1)}$ and since every $\textsf{LL(1)}$ is also $\textsf{LR(1)},$ the given grammar is $\textsf{LL(1)}$ as well as $\textsf{LR(1)}.$
selected by
46 votes
46 votes

Correct Option: C

For LL(1) take First(S). and do intersection between the result. if intersection is Phi then LL(1) else not.

Making a parsing table and checking if there are two or more entries under any terminal. If yes then neither LL(1) nor LR(1).

edited by
Answer:

Related questions

24 votes
24 votes
3 answers
2
go_editor asked Sep 29, 2014
8,318 views
Which languages necessarily need heap allocation in the runtime environment?Those that support recursion.Those that use dynamic scoping.Those that allow dynamic data stru...
28 votes
28 votes
5 answers
3
go_editor asked Sep 29, 2014
14,087 views
Which data structure in a compiler is used for managing information about variables and their attributes?Abstract syntax treeSymbol tableSemantic stackParse table