Description
Question 1 – Syntax Directed Translation
For this question you will define a syntax-directed translation for the CFG given below, which defines a very
simple programming language.
program → MAIN LPAREN RPAREN LCURLY list RCURLY
list → list oneItem
| epsilon
oneItem → decl
| stmt
decl → BOOL ID SEMICOLON
| INT ID SEMICOLON
stmt → ID ASSIGN exp SEMICOLON
| IF LPAREN exp RPAREN stmt
| WHILE LPAREN exp RPAREN stmt
| LCURLY list RCURLY
exp → exp TIMES exp
| exp DIVIDE exp
| exp PLUS exp
| exp LESS exp
| exp EQUALS exp
| LPAREN exp RPAREN
| ID
| BOOLLITERAL
| INTLITERAL
Write a syntax-directed translation for the CFG given above to extract all the int literals. The translations
should be sets that contain the intliterals. For example, the statement int i = 0 will have the translation {0}
Your translation rules should use the following notation:
{ } is an empty set
{ INTLITERAL.value } is a set containing the value of the INTLITERAL 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
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. If no translation is necessary for a CFG production, either use { } or say
no translation is necessary.
Question 2 – CYK Algorithm
Consider the following grammar
S → DA | EB
A → BF | ED
B → EH | DE
F → DD
H → AA
D → a
E → b
Use the CYK algorithm to determine if the string aabaa can be generated by this grammar. You must use this
PDF to answer this question.