The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
459 views
  1. Construct all the parse trees corresponding to $i + j * k$ for the grammar
       $E \rightarrow E+E$
       $E \rightarrow E*E$
       $E \rightarrow id$
  2. In this grammar, what is the precedence of the two operators $*$ and $+$?
  3. 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?
asked in Compiler Design by Veteran (69k points)
edited by | 459 views
$E\ ->\ idE'\\E'\ ->\ +EE'|*EE'|\ \epsilon$

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)?

1 Answer

+17 votes
Best answer
  1. two parse tree for i+j*k.
  2. $+$ and $*$ having same precedence..
  3. to make grammer LALR compatible give priority to $+$ over $*$ or vice versa.

following grammar is LALR(1)

$E \rightarrow  E + T$
           $| T$
$T \rightarrow T * F$
          $| F$
$F \rightarrow id$

 

answered by Veteran (53.7k points)
edited by
could you please explain, how giving priority to + over * and vice versa makes it LALR(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?
LALR parsers can parse left recursive grammar. no need to remove left recursion. Had it been LL(1) then you would have to remove..
for given grammar how to  construct LALR(1) grammar which is unambiguous


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

33,687 questions
40,230 answers
114,268 comments
38,794 users