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?