in Compiler Design retagged by
1,486 views
2 votes
2 votes
Consider the following grammar along with translation rules.

$S \rightarrow S_{1} \# T \qquad \{S._{\text{val}} =S_{1}. _{\text{val}} \; ^{\ast} T._{\text{val}}\}$

$S \rightarrow T \qquad \qquad \{S._{\text{val}} = T._{\text{val}}\}$

$T \rightarrow T_{1} \% R \qquad  \{T._{\text{val}} =T_{1}._{\text{val}} ÷ R._{\text{val}}\} $

$T \rightarrow R \qquad \qquad \{T._{\text{val}} = R._{\text{val}}\} $

$R \rightarrow \text{id} \qquad \qquad \{R._{\text{val}} = \text{id}._{\text{val}}\} $

Here $\#$ and $\%$ are operators and $\text{id}$ is a token that represents an integer and $\text{id}._{\text{val}}$ represents the corresponding integer value. The set of non-terminals is $\{\text{S, T, R, P}\}$ and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of $S._{\text{val}}$ for root of the parse tree for the expression $20 \# 10 \% 5 \# 8 \% 2 \% 2$ is ________________.
in Compiler Design retagged by
by
1.5k views

2 Comments

plz sir  in question also mention how much mark the given question
0
0

just simple rule 

which operator  is more away from start symbol  its  have high precedence 

and associtivity checked by  given production of the terminal if it is begining of  the RHS side of the  production  then it is left associativity  and end  side  of the  given RHS side production then it is  right associativity

According to given Question  

seeing grammer 

# operator come before % operator from the start symbol 

so precedence of % operator is > # operator 

and associativity of % is left and # is also left

given semantic action % equivalent to devision

and                           # equivalent to  product

lets  given string 

20#10%5#8%2%2

lets parenthesis according to precedence and associativity

[{20#(10%5)}#{((8%2)%2)}]

[{20#2}#{(4%2)}]

[{20#2}#2}]

80

0
0

3 Answers

5 votes
5 votes
Best answer

General rules – 

Operators which are  deeper in the parse tree, will have higher precedence, since they are tried by parser first.

Left-recursive rules indicates left associativity

Right-recursive rules indicates right associativity

---------

In the question – 

$\#$ has as corresponding operation: $*$

$\%$ has corresponding operation: $\div$

$*$ and $\div$ both are left associative and $\div$ is having higher precedence.

$20\#10\%5\#8\%2\%2 $  

$\equiv20∗(10÷5)∗((8÷2)÷2) $ 

$\equiv 20∗2∗2 \\
=  80$

selected by
2 votes
2 votes

Given that, 20#10%5#8%2%2

if we observe the grammar, we can understand the following points

  1. # has less priority than %
  2. % has left associative.
  3. # has left associative.

So we have to evaluate the given expression as : $\underbrace{\color{red}{(} \color{blue}{(}\underbrace{20\#(\underbrace{10\%5}}) \color{blue}{)} \# \underbrace{\color{green}{(} \color{cyan}{(}\underbrace{8\%2\color{cyan}{)}} \%2\color{green}{)}}\color{red}{)}}$

$= \underbrace{\color{red}{(} \underbrace{\color{blue}{(}20\#2\color{blue}{)}}\#2\color{red}{)}}=80$

1 comment

plz sir correct ur  given string in the question
1
1
0 votes
0 votes

just simple rule 

which operator  is more away from start symbol  its  have high precedence 

and associtivity checked by  given production of the terminal if it is begining of  the RHS side of the  production  then it is left associativity  and end  side  of the  given RHS side production then it is  right associativity

According to given Question  

seeing grammer 

# operator come before % operator from the start symbol 

so precedence of % operator is > # operator 

and associativity of % is left and # is also left

given semantic action % equivalent to devision

and                           # equivalent to  product

lets  given string 

20#10%5#8%2%2

lets parenthesis according to precedence and associativity

[{20#(10%5)}#{((8%2)%2)}]

[{20#2}#{(4%2)}]

[{20#2}#2}]

80

Answer:

Related questions