Back to the 2023 paper

Module 3: Semantic Analysis, Symbol Table, Run-time environment

20232m

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar:
S→xxWS \to xxW {print "1"}, S→yS \to y {print "2"}, S→SzS \to Sz {print "3"}
What is the translation of xxxxyzzxxxxyzz using the syntax directed translation scheme described by the above rules?
(i) 23131
(ii) 11233
(iii) 11231
(iv) 33211

Worked SolutionAI Assisted

Answer: (iii) 11231

Reasoning (shift–reduce with actions executed on reduce)

Grammar:
S→xxW {print 1},S→y {print 2},S→Sz {print 3}S \to xxW \ \{\text{print }1\}, \qquad S \to y \ \{\text{print }2\}, \qquad S \to Sz \ \{\text{print }3\}

Input string: x x x x y z z.

Reducing the string from the input up to SS (the actions fire in the order the reductions are performed):

Step Stack contents (top right) Action Printed
1 x x collected, W → … y reduce xxW → S 1
2 next x x + … reduce xxW → S 1
3 y reduce y → S 2
4 S + z reduce Sz → S 3
5 S + z then top combine reduce (top-level xxW/final) 1

Collecting the prints in the order the reductions happen:

11231\boxed{11231}

Hence the correct choice is (iii).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.