Project ForgeSign up free
Compiler Design
Lexical Analysis & Parsing
GATE 2016
Hard

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,A} and terminals {a,b}.

S → aA {print 1}
S → a {print 2}
A → Sb {print 3}

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

  • A1 3 2
  • B2 2 3
  • 2 3 1
  • Dsyntax error

Explanation

Parsing 'aab' bottom-up: shift a1, shift a2, REDUCE a2 via S→a (print 2), shift b, REDUCE (S b) via A→Sb (print 3), REDUCE (a1 A) via S→aA (print 1). Output order: 2, 3, 1.

Source: GATE CS 2016 (Session 1 / Set A) (2016)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free