Consider the syntax-directed translation schema (SDTS) shown below: E -> E + T { print "+" } E -> E . T { print "." } E -> id { print id.name } T -> id { print id.name } An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence (a + b . c).

GATE 1996 · Compiler Design · Syntax Directed Translation · medium

Answer: The translation (postfix output) for (a + b . c) is: a b . c +

1. Determine the parse structure: The expression (a + b . c) is parsed as (a + (b . c)) if . binds tighter, or ((a + b) . c) depends on grammar precedence. Looking at the grammar: E -> E+T and E -> E.T — both have E on the left, T on the right. T -> id only (T cannot derive E.T), so . has higher precedence than +. Thus: a + (b . c) where b.c is the left-associative sub-expression. Parse tree root: E -> E + T, left E -> E . T (but wait — E.T means left E and right T; b is id->T->... let's trace exactly). Actually E -> E . T: left E must reduce from something; here a is id->E (via E->id), b is id->T (via T->id), c is id->T. So the parse is: E(a) . T(b) -> E, then E + T(c) -> E.
2. Trace LR reductions and print actions: Step-by-step: 1. Shift 'a', reduce id->E: print 'a' 2. Shift '.' 3. Shift 'b', reduce id->T: print 'b' 4. Reduce E . T -> E: print '.' 5. Shift '+' 6. Shift 'c', reduce id->T: print 'c' 7. Reduce E + T -> E: print '+' Printed sequence: a b . c +