Consider the following grammar along with translation rules.

\begin{aligned} & 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}}\} \end{aligned}

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

View worked solution

Answer: 80

To find the computed value of $S_{\text{val}}$ for the expression $20 \# 10 \% 5 \# 8 \% 2 \% 2$ , we first analyze the precedence and associativity of the operators from the given grammar.

1. Operator Precedence and Associativity

Precedence: Since $S$ derives $T$ ( $S \rightarrow T$ ) and $T$ derives $R$ ( $T \rightarrow R$ ), the operator $\%$ (associated with $T$ ) has higher precedence than the operator $\#$ (associated with $S$ ).
Associativity:
- The production $S \rightarrow S_1 \# T$ is left-recursive, so $\#$ is left-associative.
- The production $T \rightarrow T_1 \% R$ is left-recursive, so $\%$ is left-associative.

2. Evaluation Steps

Given the expression: $\text{Expr} = 20 \# 10 \% 5 \# 8 \% 2 \% 2$

Due to the higher precedence of $\%$ , we first group and evaluate the sub-expressions containing $\%$ .

Step 1: Evaluate the $\%$ sub-expressions (left-to-right)

First sub-expression: $10 \% 5 = 10 \div 5 = 2$
Second sub-expression (left-associative): $8 \% 2 \% 2 = (8 \div 2) \div 2 = 4 \div 2 = 2$

Substituting these values back into the expression gives: $20 \# 2 \# 2$

Step 2: Evaluate the $\#$ operations (left-to-right)

Since $\#$ represents multiplication ( $*$ ) and is left-associative: $(20 \# 2) \# 2 = (20 \times 2) \times 2 = 40 \times 2 = 80$

Thus, the computed value of $S_{\text{val}}$ at the root of the parse tree is 80.

Free practice · Your answers on this page are not saved.

GATE CS 2022 Q55 — Syntax-directed Translation

1. Operator Precedence and Associativity

2. Evaluation Steps

Related questions