1. ::= | | | | | ::= select end; ::= -> | -> `||' Note that || is enclosed in quotes so that it is not mistaken for a BNF symbol (specifying another alternative). Note that you need the additional non-terminal because if you write something like: end; you will end up with too many of the "select" and "end" keywords as well as the ";" symbols. 2. [Recall that the idea of the array representation is as follows. The abstract parse tree is represented as an array of numbers where each node of the parse tree is represented by one row in the array. Each row contains 5 columns. The first column contains a number that tells us what the non-terminal at that node is. For example, if this number is 8, that means the non-terminal at that node is ; if it is 7, the non-term. is ; etc; these numbers are listed at the end of the line for each production on slides 18, 19. The second column tells us which alternative from the corresponding production we are using at this point. For example, if the first column is 8 (so the non-term. at that node is ) and we are using the second alternative from the production, the second column will have the value 2. The remaining three columns are the row numbers corresponding to the children nodes of the current node. If there are only 2 children, the fifth column will be 0 (saying there is no third child); similarly if there is only one child, the fourth and fifth columns will both be 0.] Exec-select should simply call Exec-rest; that procedure should call Eval-cond to evaluate the condition; if this returns true, call Exec-ss to execute the following ; if not, Exec-rest should return if its alternative number is 1 (because in this case there are no more s to evaluate); and if alt.no. is 2, it should call Exec-rest with its third child as the argument. Thus Exec-select() may be written, using the notation from the class notes, as follows: procedure Exec-select(int n) { Exec-rest( PT[n,3] ); } procedure Exec-rest(int n) { int x; x = Eval-cond( PT[n,3] ); if (x==1) { Exec-ss( PT[n,4] ); } else if (PT[n,2]==2) { Exec-rest( PT[n,5] ); } } Note: A common mistake in doing this assignment is as follows: Writing the syntax of the select statement so that it looks like an equivalent set of nested if statements. That is incorrect. What the problem asks you to do is to introduce a new statement into the language. The fact that you can write a semantically equivalent statement using a bunch of if's is not relevant. An analogous problem would be as follows: If we had a low-level language that had conditional (and unconditional) branches and we wanted to introduce "if-then-else" commands into the language, the fact that we could write, using the branch statments of the language, a set of statements that would be semantically equivalent to the proposed if-then-else command is irrelevant. This should be considered a new command with its own syntax etc. That is the case with the select statement. Another common mistake is for Exec-select to go down the branch. That violates the spirit of recursive descent. In rec. desc., each procedure handles only *one* level of the tree, and calls other procedures to handle the children nodes.