Assignment 4, due Sept 22

Homework

1. Do Chapter 5 Problem 4 from the notes.

2. Many computers (including the Intel 80x86 family) have program-counter relative branch instructions with the following format:

   		 F E D C B A 9 8 7 6 5 4 3 2 1 0
   		|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
   		|_______________|_______________|
   		      opcode       displacement
   

   Instruction fetches on such machines are typically done as follows:

   		instruction_register = memory[PC] -- a 16-bit fetch
   		PC = PC + 2
   

   Branch instructions that are taken, when they are executed, operate as follows:

   		PC = PC + 2*sign_extend(displacement);
   

   In the above, the sign-extend operation takes bit 7 of the displacement field of the instruction register and replicates it in all higher bits. The possibility of untaken branches arises from the fact that many branches are conditional branches. Assume that our the assembly language allows the following assembly notation:

   		BACK:	--- some code goes here
   			BZS	NEXT	; goes to NEXT if Z set.
   			--- other code goes here
   			BR	BACK    ; goes to BACK.
   		NEXT:	--- more code goes here
   

   a) Show the appropriate value for the displacement when a branch branches to itself, in a one-instruction infinite loop.

   b) Flesh out Figure 5.2 to include a case for branch instructions, assuming that the opcode table categorizes these as having format 5.

3. The grammar for the LISP programming language is remarkably simple:

   <s-expression> ::= <atom> | <list> 
   <atom> ::= <identifier> | <constant> 
   <list> ::= ( { <s-expression> } [ . <s-expression> ] ) 

   All LISP programs are composed of S expressions, and all LISP data is printable as S-expressions. Aside from punctuation, which is limited to parentheses and the period, there are only two syntactic categories, identifiers and constants.

   Follow the mechanistic rules for writing a top-down recursive descent parser that are given in chapters 2 and 5 in order to write the functions parse_s_expression(), parse_atom(), and parse_list() implied by the above grammar.