## CS 375, Compilers: Example Question Answers for Midterm Exam

Consider the following declarations:
```     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 - 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.

``` S  -->  a S