Top Down Parsing

Question

Since it is a Bottom Up Parser do we need to evaluate expressions following Right Hand Derivations or Left Hand Derivations,i.e. should we evaluate D -> d first or B -> B first?

Consider the following grammar and associated semantic actions :-
\[
\begin{array}{lr}
\mathrm{S} \rightarrow \mathrm{ABCD} & \{\mathrm{x}=2 \mathrm{x}+1\} \\
\mathrm{D} \rightarrow \mathrm{~d} & \{\mathrm{x}=2 \mathrm{x}-1\} \\
\mathrm{C} \rightarrow \mathrm{cc} & \{\mathrm{x}=5 \mathrm{x}+7\} \\
\mathrm{B} \rightarrow \mathrm{Bb} & \{\mathrm{x}=5 \mathrm{x}-7\} \\
\mathrm{B} \rightarrow \mathrm{~b} & \{\mathrm{x}=\mathrm{x}+1\} \\
\mathrm{A} \rightarrow \mathrm{gBa} & \{\mathrm{x}=2 * \mathrm{x}-1\}
\end{array}
\]

The variable x is a global. Assume x is initialized with " 0 " before parsing. What is the final value of $x$ in a bottom up passing of the following input "g b a b c c d"?

Comments

i think it is...$67$

---

Yes. I also initially calculated the value as 67. But then changed my answer by evaluating using Right Hand Derivations. Since in question it's specified "Bottom Up Parser" shouldn't we evaluate starting from d -> D?

Answer 1

A bottom up parser works by scanning the string from left to right and performing reduction when the stack top has a handle. So, the answer is 67.

The reductions are in the order as

B->b, A->gBa, B->b, C->cc, D->d and then S->ABCD

Comments

simply for derivation follow Right most derivation and for evaluation of expression move in reverse order of  Right most derivated string till u get start symbol