CS 375, Compilers: Example Question Answers for Midterm Exam

Addressing:

     type complex = record  re, im: real  end;

          person  = record name:     alfa;
                           age:      integer;
                           location: complex;
                           weight:   real;
                           salary:   real     end;

     var  people = array [ 7..14, (austin, dallas, houston)]
                          of person;

• Assuming integer and boolean are 4 bytes, and alfa, pointers and real are 8 bytes, how much storage is occupied by the array people?

  Answer: complex contains 2 reals, for a total of 16 bytes.

  The person record has the following layout:

  Field:	Offset:	Size:	Comment:
  name	0	8
  age	8	4
  	12	4	padding
  location	16	16	records are 16-aligned
  salary	32	8	reals are 8-aligned
  weight	40	8
  Total	48

  The total size of a person record is 48 bytes.

  The array size should be calculated back-to-front to provide numbers that are used in the next step. (austin, dallas, houston) is 3 items, 3*48 = 144 bytes. Using the formula (high - low + 1), the array is (14 - 7 + 1) * 144 = 8*144 = 1152 bytes.

• Calculate the effective address of the expression:

     people[10,dallas].location.im
  

  Show how it was derived and give the aref form.

  Answer: We calculate the offset by adding the components, left-to-right:

  Item:	Value:	Multiplier:	Subtotal:
  [10]	(10 - 7)	144	432
  dallas	(1 - 0)	48	48
  location	16	1	16
  im	8	1	8
  Total			504

  The code for this reference is (aref people 504).

Other Questions:

• Show how an operator precedence parser would parse the string:

       A - (B / C - D) / E + F
  

  Show the contents of the stacks at each step; produce a tree as output.

  Answer: This can be done using either a diagram or parenthesized notation for the tree structure.

  Item:	Operators:	Operands:	Note:
  A		A	Shift A
  -	-	A	Shift -
  (	- (	A	Shift (
  B	- (	A B	Shift B
  /	- ( /	A B	Shift /
  C	- ( /	A B C	Shift C
  -	- (	A (/ B C)	Reduce: / > -
  -	- ( -	A (/ B C)	Shift -
  D	- ( -	A (/ B C) D	Shift D
  )	- (	A (- (/ B C) D)	Reduce
  )	-	A (- (/ B C) D)	Discard ()
  /	- /	A (- (/ B C) D)	Shift /
  E	- /	A (- (/ B C) D) E	Shift E
  +	-	A (/ (- (/ B C) D) E)	Reduce: / > +
  +		(- A (/ (- (/ B C) D) E))	Reduce: - = +
  +	+	(- A (/ (- (/ B C) D) E))	Shift +
  F	+	(- A (/ (- (/ B C) D) E)) F	Shift F
  end		(+ (- A (/ (- (/ B C) D) E)) F)	Reduce

• Give one advantage and one disadvantage of hashing as a method of symbol table organization.

  Answer: Adv: Fast, O(1). Dis: Must find a good hash function, must expand table when it gets too full (> 70%).

• Consider the regular expression (a | b)*b+b* . What is the simplest regular expression that denotes the same language?

  Answer: b+ can absorb b*. b+ = b*b. (a | b)* can absorb b*. What is left is (a | b)*b.

• Give the allowable form of productions for a Regular grammar.

  Answer: A -> xB, A -> x where A and B are nonterminals, x is a terminal string.

• Consider the following grammar:

   S  -->  a S
   S  -->  S b
   S  -->  b
  

  • What kind of grammar is this in the Chomsky hierarchy?

    Answer: It has a single nonterminal on the left of each production (thus is Context Free) but does not fit the Regular production pattern, so it is Context Free.

  • What kind of language does it denote?

    Answer: a*b+ is the language denoted. Since a*b+ is a regular expression, the language must be Regular.

  • Is there a simpler kind of grammar that denotes the same language? If so, give the grammar; if not, explain why not.

    Answer:

     S  -->  a S
     S  -->  T
     T  -->  b T
     T  -->  b
    

    This is a Regular grammar that denotes the same language.
• Briefly and clearly define the following terms: ... 8 terms chosen from the vocabulary list on the study guide.