CSE 307 – Midterm Exam 2 Version 1 Stony Brook University CSE 307

CSE 307 – Midterm Exam 2 Version 1 Sample

Name: First Last

Student ID # _________________________________

Question # Points Points Earned
Available
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10
Total: 100

Directions: You have 80 minutes to complete this exam. Write all answers neatly in the space provided.
Please do not separate exam sheets.

Individual closed book exam. You are not allowed to use the textbook, lecture notes, cheat sheets or anything
else beside your brain during the exam.




CSE 307 –Midterm Exam 2 1

, Question 1
Write an attribute grammar to recognize the language L = anbncn (e.g., abc, aabbcc,
aaabbbccc,…) that associates a Boolean attribute ok with the root R of the parse
tree, such that R.ok=true if and only if the string corresponding to the tree is in L.

G -> As Bs Cs > G.ok := (As.val == Bs.val /\ Bs.val == Cs.val)
As1 -> a As2 > As1.val := As2.val + 1
As -> epsilon > As.val := 0
Bs1 -> b Bs2 > Bs1.val := Bs2.val + 1
Bs -> epsilon > Bs.val := 0
Cs1 -> c Cs2 > Cs1.val := Cs2.val + 1
Cs -> epsilon > Cs.val := 0

Show the attributed trees for 2 strings:

aabbcc

aabcc




CSE 307 –Midterm Exam 2 2