search
Log In
22 votes
1.4k 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?
in Compiler Design
edited by
1.4k views
2
$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)?
0
Same doubt.. Somebody please answer

1 Answer

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

following grammar is LALR(1)

$E \rightarrow  E + T$
$\qquad \mid T$
$T \rightarrow T * F$
$\qquad \mid F$
$F \rightarrow id$


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

0
Doesn't matter but we always go with the normal conventions that we follow.
0
normal conventions like?
0
Like the conventions we use in C language.

Related questions

23 votes
5 answers
1
5.8k views
In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on the size of the blocks, and the size of the address of the blocks. the number of blocks used for the index, and the size of the blocks. the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks. None of the above
asked Sep 16, 2014 in Databases Kathleen 5.8k views
5 votes
3 answers
2
1k views
The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function int TEST-AND-SET (int *x) { int y; A1: y=*x; A2: *x=1; A3: return y; } Complete the following C functions for implementing code for entering and ... and starvation-free? For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic?
asked Feb 28, 2018 in Operating System jothee 1k views
19 votes
1 answer
3
1.4k views
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$ Give an NFA for this purpose Give a DFA for this purpose
asked Sep 16, 2014 in Theory of Computation Kathleen 1.4k views
20 votes
3 answers
4
2.5k views
The following solution to the single producer single consumer problem uses semaphores for synchronization. #define BUFFSIZE 100 buffer buf[BUFFSIZE]; int first = last = 0; semaphore b_full = 0; semaphore b_empty = BUFFSIZE void producer() { while(1) { produce an ... $p2$, immediately after $c1$ and immediately before $c2$ so that the program works correctly for multiple producers and consumers.
asked Sep 16, 2014 in Operating System Kathleen 2.5k views
...