For this homework you will define a syntax-directed translation for the CFG given below, which defines a very simple programming language.

funclist  funclist func | epsilon func  ID LPAREN RPAREN LCURLY stmtlist RCULY stmtlist  stmtlist stmt | epsilon stmt  ID ASSIGN exp SEMICOLON | WHILE LPAREN exp RPAREN stmt | ID LPAREN RPAREN SEMICOLON exp  exp TIMES exp | exp DIVIDE exp | exp PLUS exp | exp LESS exp | exp EQUALS exp | LPAREN exp RPAREN | ID | BOOLLITERAL | INTLITERAL 

Question 1:

Write a syntax-directed translation for the CFG given above to extract all the bool literals and IDs.

Your translation rules should use the following notation:

{ } is an empty set

{ BOOLLITERAL.value } is a set containing the value of the BOOLLITERAL token

{ ID.value } is a set containing the value of the ID token

S1 S2 is the intersection of sets S1 and S2

S1 S2 is the union of sets S1 and S2

S1 - S2 is the set of all items that are in S1 but not in S2

Note that you should not try to use something like "{ a, b }" to mean a set with two elements; instead, use set union to combine two sets that each contain one element.

Use the notation that was used in class and in the on-line readings; i.e., use nonterminal.trans to mean the translation of a nonterminal, and terminal.value to mean the value of a terminal. Assume that ID.value is a String (the name of the identifier). Use subscripts for translation rules that include the same nonterminal or the same terminal more than once.

Question 2:

Draw a parse tree for the program given below and annotate each nonterminal in the tree with its translation.

fun() { a = b + 1; } main() { d = True; while (d) fun(); }