PLI Tutorial 6 Semantic analysis (Lm.n refers to Louden, Exercise m.n.) 1. (L6.1) Write an attribute grammar for the integer value of a number given by the following grammar: number -> digit number | digit digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 9 2. (L6.2) Write an attribute grammar for the floating point value of a decimal number given by the following grammar. (Hint: Use a count attribute to count the number of digits to the right of the decimal point.) dnum - num.num num -> num digit | digit digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 9 3. (L6.4) Consider an expresion grammar as it might be written for a recursive descent parser with left recursion removed: exp -> term exp' exp' -> empty | + term exp' | - term exp' term -> factor term' term' -> empty | * factor term' | / factor term' factor -> number | ( exp ) Write an attribute grammar for the value of an expression given by this grammar. 4. (L6.5) Rewrite the attribute grammar of Table 6.2 (an attribute grammar for the standard left-recursive, associative/precedence-defining grammar for arithmetic expressions) to compute a postfix string attribute instead of a numeric value attribute. The resulting postfix string attribute should contain the postfix form for the arithmetic expression. E.g., the postfix attribute for (32-3)*42 should be "34 2 - 42 + *". You may assume a concatenation operator || and the existence of a number.strval attribute. 5. (L 6.6) Consider the following grammar for integer binary trees (in Lisp-like form): btree -> nil | (number btree btree) Write an attribute grammar to check that a binary tree is ordered, i.e., that the tree is a binary search tree. 6. (L6.7) Consider the following grammar for simple Pascal-like variable declarations: decl -> var-list : type var-list -> id | var-list , id type -> integer | real Write an attribute grammar for the type of a variable. 7. (L6.8) Consider the grammar of the previous exercise (L6.7). Rewrite the grammar so that the type of a variable can be defined as a purely synthesized attribute, and give a new attribute grammar for the type that has thus property. 8. Louden, Exercise 6.10. 9. Which of the compound types described in the week 6 lecture notes may be constructed in C, Java and Haskell, respectively? Describe how each type is defined in each language (where possible, of course). 10. (L6.17) Rewrite the attribute grammar for let-expressions in the notes to use collateral declarations instead of sequential declarations. 11. (L6.18) Extend the attribute grammar for let-expressions in the notes to compute the value of each expression. 12. Louden, Exercise 6.19. 13. (L6.29) Write a Yacc specification for a program that will compute the value of let-expressions defined using the grammar of the previous exercises (L6.17, L6.18). 14. Study the semantic analyser from the TINY compiler, files symbtab.h, symtab.c, analyze.h and analyze.c. 15. (L6.32) Rewrite the TINY semantic analyser so that it makes only a single pass over the syntax tree. 16. (L6.33) Rewrite the TINY semantic analyser so that it makes "reasonable" checks that each variable has been assigned a value before it is used in an expression. What prevents such checks from being foolproof?