The Gateway to Computer Science Excellence

+35 votes

Best answer

Both LALR(1) and LR(1) parser uses LR(1) set of items to form their parsing tables. And LALR(1) states can be find by merging LR(1) states of LR(1) parser that have the same set of first components of their items.

i.e. if LR(1) parser has $2$ states I and J with items $A \rightarrow a.bP$,$x$ and $A \rightarrow a.bP$,$y$ respectively, where $x$ and $y$ are look ahead symbols, then as these items are same with respect to their first component, they can be merged together and form one single state, let’s say $K$. Here we have to take union of look ahead symbols. After merging, State $K$ will have one single item as $A \rightarrow a.bP$,$x$,$y$ . This way LALR(1) states are formed ( i.e. after merging the states of LR(1) ).

Now, $S-R$ conflict in LR(1) items can be there whenever a state has items of the form :

A-> a.bB , p C-> d. , b i.e. it is getting both shift and reduce at symbol b, hence a conflict.

Now, as LALR(1) have items similar to LR(1) in terms of their first component, shift-reduce form will only take place if it is already there in LR(1) states. If there is no S-R conflict in LR(1) state it will never be reflected in the LALR(1) state obtained by combining LR(1) states.

Correct Answer: $B$

0

Same thing happens for RR conflict also.rt?

means

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if The LR(1) parser for G has S-R conflicts

means

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if The LR(1) parser for G has S-R conflicts

0

what if the question is

SLR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if?

SLR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if?

0

can we merge the two states of LR(1) if state I has one more item,other than the common one,which is not present in another state J?

0

@meghna, No.

2 states can be merged only if they are identical.

These two states are virtually identical if they have the same number of items, the core of each item is identical, and they differ only in their lookahead sets.

0

Let there are two states to be merged

1st state -

A->K.b, m

B->c. , a

2nd state-

A->K.b, n

B->c. ,b

None of these have any conflict but if you will merge them both

A->K.b, m/n

B->c. ,a/b

Now shift on b will clash with reduce move of B as in lookaheads a and b , B->c. will be placed ?

1st state -

A->K.b, m

B->c. , a

2nd state-

A->K.b, n

B->c. ,b

None of these have any conflict but if you will merge them both

A->K.b, m/n

B->c. ,a/b

Now shift on b will clash with reduce move of B as in lookaheads a and b , B->c. will be placed ?

0

+13 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,313 answers

198,349 comments

105,052 users