The Gateway to Computer Science Excellence
+3 votes

Consider the following grammar:

  • $S \rightarrow S$
  • $S \rightarrow SS \mid a \mid \epsilon$

Construct the collection of sets of LR (0) items for this grammar and draw its goto graph.

in Compiler Design by Veteran (106k points)
edited by | 424 views
i think this is ambigous grammer try to gererate string "a" you will gate 2 LMD
It is ambiguous grammar and we can't parse it by LR(0) parser. right na?

Here  S→  ϵ will take as reduce/ shift action or not effect on LR(0) DFA??

So we cannot write LR(0) items if grammar is ambiguous?
afaik, LR(0) items can be constructed if the grammar is ambiguous.

2 Answers

+4 votes
Best answer

The augmented production is $S^{'} \rightarrow S$.

$\textbf{GOTO Graph:}$

Here, each of $I_0$, $I_1$, $I_2$, $I_3$ is a set of $LR(0)$ items. And hence $I_0$, $I_1$, $I_2$, $I_3$ are the collection of sets of $LR(0)$ items.

by Boss (15.4k points)
selected by
+1 vote

Augmented production S'-->S


by Boss (13.3k points)
reshown by
Sir we can write LR(0) items..

But there will be conflicts in dfa (of canonical collection of LR(0) items).. so the grammar will not be LR(0)
Thats all is asked in the question rt?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,395 answers
105,446 users