1. This asked about the general guidelines related to evaluation rules for
synthesized and inherited attributes. Some of the answers were unfocused and
missed some key points. Especially for inh. attr. a question was, what if the
particular non-terminal <N> doesn't appear on the right-side of any production.
The right answer here is that, in that case, there won't be any rules for
evaluation of I() of <N>. Some people said that, in this case if <N> is the
starting non-terminal of the grammar, we will somehow "initialize" I() for that
root occurrence of <N>. That is incorrect; there is no such thing as
"initialization" etc. If <N> is the starting non-terminal, we are not allowed to
have an inh. attr. for <N>.

2. This asked, for a simple block-structured language (in which you are allowed
to access, at any point, variables declared in the current block, in the
surrounding block, etc.), how you would use only synth. attr. to capture the
requirements. The answer is that we should have a DeclIds(<ds>) and
UsedIds(<ss>), as well as for <stmt> etc. Since a <block> is a <stmt>, we need to
defined UsedIds() for <block>. The way to define it is as 
  <block> ::= begin <ds> <ss> end;
              UsedIds(<block>) <-- UsedIds(<ss>)\DeclIds(<ds>)
where "\" denotes set subtraction. With that rule, the UsedIds(<block>) is the
set of identifiers that have been used in that block (possibly in nested levels)
that were not declared in the block so they better be declared at some
surrounding level.

With that, we have only one condition, at the root level:
  <prog> ::= <block>
             Cond: UsedIds(<block>) == empty
This is because there are no more "surrounding" levels so all the id's used
inside the block should already have been declared.

3. This was about overloading where two (or more) procedures with the same name
may be declared in a block as long as the *number* of parameters each one expects
is different. 

You had to make two changes to account for this. First, the condition that checks
for double declarations has to be relaxed so that two procedures with the same
name are allowed to be declared so long as the no. of parameters each one expects
is different from the other. There is no need to define a new attribute to
provide this information because it is already there in the Decs() because we are
including the name of the procedure, the fact that it is a procedure, and the
list of parameter types it expects so the length of that list is, of course, the
no. of parameters it expects. 

Second, we need to change the condition for the proc. calls since, if we look for
a procedure called "P", we might find more than one. So we have to refine our
search, i.e., redefine the function we use, so that we look not just for a
procedure named "P" but one with a specified no. of parameters (which matches the
no. of arguments in the call). 

4. This question sort of combined our S-exp discussion with attr. grammars. You
were given a somewhat strange BNF for s-exp's (which allowed such things as 
"1 . 2 . 3 . 4" to be generated as an <s-exp>) and asked you to define
appropriate attributes and conditions to ensure that only proper s-exp's can be
generated. Also, there was a restriction that no list notation should be allowed
in the generated s-exp's.

There are a couple of problems to address here. First, you have to make sure that
if the alternative of <s-exp> . <s-exp> is used, that at the immediately higher
level, we have parentheses surrounding that. Second, if use the (<s-exp>)
alternative, that the <s-exp> in question is, in fact, a dotted s-exp. Moreover,
at the top level, you do not want overall <ts-exp> to be <s-exp> . <s-exp>

The simplest way to do this is to have a synt. attr. that tells you what kind of
<s-exp> [atom or dotted or parenthesized] a given child is and impose appropriate
conditions at various levels. E.g., at the top-level:

  <ts-exp> ::= <s-exp>
               Cond: Type(<s-exp>) != 2 
where 2 denotes a dotted <s-exp> [1 denotes an atom and 3 denotes a parenthesized
<s-exp>]. 

We also need a cond. for the dotted <s-exp>:
    <s-exp>1 . <s-exp>2
    Cond: Type(<s-exp>1) != 3 && Type(<s-exp>2) != 2

And similarly for the parenthesized <s-exp>
    (<s-exp>1)
    Cond: Type(<s-exp>1) == 2

5. This asked you to define the noDuplicates[L] function that takes a list L of 
atoms as argument and returns T if there are no duplicates in it and NIL otherwise. 

A couple of students said this can't be done in Lisp because you have to check
whether the first element appears anywhere later in L and when you do that
recursively, you are going to throw away the second, third, ... elements of L.
So then, if the first element does not appear later, you cannot check if the
*second* element is duplicated since you have lost that second element. 
In other words, since you cannot introduce temporary variables and update them
etc., it is not possible to write such functions.

While that is an interesting argument, the way around it is to have more than
function, each designed to do just one specific task. In this case, there are two
tasks: one is to check if a given element appears anywhere (later) in the list;
and the second is to check if any of the elements is duplicated. It is the latter
function that is called noDuplicates[] but it should use the auxiliary function,,
call it check1[x, L], which checks if a given element x, its firtst argument,
appears in L, its second argument. With that, you can write such functions.