D.2 Problems for Chapter 5: Syntax-directed Translation
D.2.1 Syntax-directed Definition (SDD)
Problem 2.1.15 Given below the syntax-directed definition (SDD), construct the annotated parse tree for the input expression: “int a, b”.
D –> T L L.inh = T.type
T –> int T.type = integer
T –> float T.type = float
L –> L1, id L1.inh = L.inh
addType(id.entry,L.inh)
L –> id addType(id.entry,L.inh)
The annotated parse tree is:
Problem 2.1.16 Given below the SDD with the synthesized attribute val, draw the annotated parse tree for the expression (3+4)*(5+6).
L –> E L.val = E.val
E –> T E.val = T.val
E –> E1 + T E.val = E1.val + T.val
T –> F T.val = F.val
T –> T1 * F T.val = T1.val * F.val
F –> ( E ) F.val = E.val
F –> digit F.val = digit.lexval
The annotated parse tree is:
D.2.2 Syntax-directed Translation (SDT)
Problem 2.2.17 Prepare an SDT scheme that translates arithmetic expressions from infix into postfix notation. The solution should include the CFG, the semantic attributes for each of the grammar symbols and semantic rules. Show the application of your scheme to the input “3*4 + 5*2”.
Solution: We define a synthesized attribute string and the string concatenation operator ‘:’. We also define a simple grammar as shown below with start symbol E and with Terminal symbol num, which also has a string attribute set by the lexical analyzer as the string with the numeric value representation of num.
E1 –> E2 + T E1.str = E2.str : T.str : ‘+’
E1 –> T E1.str = T.str
T1 –> T2 * F T1.str = T2.str : F.str : ‘*’
T –> F T.str = F.str
F –> ( E ) F.str = E.str
F –> num F.str = num.str
For the input string “3*4+5*6”, we would have the annotated parse tree shown below.
Problem 2.2.18 Consider the following grammar for expressions and lists of statements (stmtlist) using assignment statements (assgn) and basic expressions (expr) using the productions presented below.
stmtlist –> stmt ; stmtlist
stmtlist –> stmt
stmt –> assgn
expr –> expr + expr
expr –> int
expr –> id
assgn –> id= expr
assgn –> id += expr
Using a stack-based machine, write a syntax-directed definition to generate code for stmtlist, assgn and expr.
Solution: Remember that in a stack-based machine you need to push the operands of the expressions first onto the stack and then execute the operations with the topmost element/s of the stack.
A possible solution is to have only synthesized attributes such as “str” for identifiers and “val” for integers. The non-terminal expr also has a synthesized attribute that holds the variable name when defined by an identifier. When defined by an integer this attribute value is null.
A possible syntax-directed translation definition using the yacc-like assignment of non-terminal symbols in a production is shown below.
stmtlist -> stmt ; stmtlist { }
stmtlist –> stmt { }
stmt –> assgn { }
expr –> expr + expr { emit(″add″); }
expr –> int { emit(″push int.val″); $$.val = nil; }
expr –> id { emit(″push id.str″); $$.val = id.str; }
assgn –> id= expr { emit(″pop $1.val″); }
assgn –> id += expr { emit(″add″); emit(″push $1.val″);
emit(″pop $1.val″);}