Skip to content
GATETECH
Official PYQ · 1995Q2.10Syntax-directed TranslationMCQ1 mark

GATE CS 1995 Q2.10 — Syntax-directed Translation

Explain with AI

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar

  • S→xxW  print“1"S \rightarrow xxW \;\text{{print“1"}}
  • S→y  print“2"S \rightarrow y \;\text{{print“2"}}
  • W→Sz  print“3"W \rightarrow Sz\; \text{{print“3"}}

What is the translation of xxxxyzzxxxxyzz using the syntax directed translation scheme described by the above rules?

Choose one option
View worked solution

Answer: A

A shift-reduce parser processes the input from left to right, shifting symbols onto the stack and executing semantic actions immediately after a reduction is performed. Let us trace the parsing of the input string xxxxyzzxxxxyzz step-by-step:

Stack Remaining Input Action / Reduction Rule Output
\)</td> <td>\(xxxxyzz Shift x,x,x,x,yx, x, x, x, y -
xxxxyxxxx y zzzz Reduce S→yS \rightarrow y 2
xxxxSxxxx S zzzz Shift zz -
xxxxSzxxxx Sz zz Reduce W→SzW \rightarrow Sz 3
xx(xxW)xx(xxW) zz Reduce S→xxWS \rightarrow xxW 1
xxSxx S zz Shift zz -
xxSzxx Sz \)</td> <td>Reduce \(W \rightarrow Sz 3
xxWxxW \)</td> <td>Reduce \(S \rightarrow xxW 1
SS \(\) Accept -

Collecting the outputs in order of execution gives 23131.

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

Published
Report a correction
Keep exploringMore Syntax-directed Translation questions