Although I know there is no need of removing left recursion in case LALR parser but can the above be also the answer to part c)?

The Gateway to Computer Science Excellence

+22 votes

- Construct all the parse trees corresponding to $i + j * k$ for the grammar

$E \rightarrow E+E$

$E \rightarrow E*E$

$E \rightarrow id$ - In this grammar, what is the precedence of the two operators $*$ and $+$?
- If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is unambiguous?

+28 votes

Best answer

+1

why hadn't you make the grammar non-left recursive? Since priority has to be given to someone, we can give it to + or *. Is this the reason?

+16

LALR parsers can parse left recursive grammar. no need to remove left recursion. Had it been LL(1) then you would have to remove..

+2

1.how giving priority to + over * and vice versa makes it LALR(1)

for given grammar how to construct LALR(1) grammar

Here there is no point removing left recursion. It is asking

If only one parse tree is desired for any string in the same language

In this particular grammar ambiguity arises because there is no precedence or associativity defined for any non terminal. Therefore changes we will have to make is

1. Decide the precedence of + and *.

2. Decide the associativity of + and *.

These 2 points are taken care by @Digvijay Pandey sir's answer.

0

@tusharp i understood that for making grammar unambiguous..precedence and associativity are given but how to decide which operator should be left associative which is right and same the case of precedence??

- 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,384 answers

198,538 comments

105,333 users