Dark Mode

1,428 views

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 ________________.

$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 ________________.

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

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}]

0

4 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$

2 votes

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

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

- # has less priority than %
- % has left associative.
- # 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$

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

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}]