Exam 1 Practice Problems
Problem 1 Consider the context-free grammar that generates arithmetic expressions (over digits and plus and times) in infix notation.
S¡úE E¡úE+T E¡úT
T ¡ú T*digit T ¡ú digit
(1) Construct an attribute grammar that translates the expressions into prefix notation. For example,9 + 5 * 2translatesinto+ 9 * 5 2.
(2) Construct an attribute grammar that associates an attribute count to the root of the tree S such that count contains the number of digits in the expression. For example, S.countfor9 + 5 * 2 * 8is4.
Problem 2 Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on input 101.101, S.val = 5.625.
S ¡ú L.L|L L ¡ú LB|B B¡ú0|1
Use synthesized attributes to determine S.val.
1