Consider the following syntax-directed definition (SDD).
| \({S \to DHTU}\) | \(\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}\) |
| \({D \to \text{``M''}D_{1}}\) | \(\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}\) |
| \({D \to \epsilon}\) | \(\{\ D.\mathit{val} = -5;\ \}\) |
| \({H \to \text{``L''}H_{1}}\) | \(\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}\) |
| \({H \to \epsilon}\) | \(\{\ H.\mathit{val} = -10;\ \}\) |
| \({T \to \text{``C''}T_{1}}\) | \(\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}\) |
| \({T \to \epsilon}\) | \(\{\ T.\mathit{val} = -5;\ \}\) |
| \({U \to \text{``K''}}\) | \(\{\ U.\mathit{val} = 5;\ \}\) |
Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute \(S.\mathit{val}\))?
Answer
(A)
Explanation
For "MMLK", the rule \(S \to DHTU\) uses \(D\) for "MM", \(H\) for "L", \(T\) for the empty string and \(U\) for "K". Evaluating the attributes bottom-up:
- \(D\): the innermost \(D \to \epsilon\) gives \(-5\), then \(5 + (-5) = 0\), then \(5 + 0 = 5\).
- \(H\): \(H \to \epsilon\) gives \(-10\), then \(5 * 10 + (-10) = 40\).
- \(T \to \epsilon\) gives \(-5\), and \(U\) gives 5.
So \(S.\mathit{val} = 5 + 40 + (-5) + 5 = 45\). Ignoring the negative values of some of the \(\epsilon\)-productions leads to the other options, 50, 55 or 65.
Answer: A