Design a lexical analyzer using transition diagram that recognizes:

• Identifiers (letter followed by letters/digits)
• Integer constants
• Operators: +, -, *, /, <, <=, >, >=, ==, =
• Keywords: if, then, else, while

1. read x
2. i = 1
3. sum = 0
4. prod = 1
5. if i > x goto 13
6. square = i * i
7. sum = sum + square  
8. prod = prod * i
9. i = i + 1
10. if i <= x goto 6
11. write sum
12. write prod
13. halt

• Redundant load/store elimination
• Constant folding
• Strength reduction
• Use of machine idioms

Apply these optimizations to the following assembly code:

MOV R0, a

MOV b, R0

MOV R0, b

ADD R0, R0, #0

MUL R0, R0, #2

MOV R1, #10

ADD R1, R1, #5

MOV R2, #0

Show the activation tree and activation record contents for the following code at the point when factorial(1) is executing:

int factorial(int n) {

    if (n <= 1)

        return 1;

    return n * factorial(n-1);

}

int main() {

    int x = factorial(3);

• Linear list
• Hash table
• Binary search tree

Which is most efficient and why?

Show hash table implementation for storing the following identifiers using hash function h(x) = (sum of ASCII values) mod 7:

Identifiers: {sum, count, avg, total, temp}

E → E + T | T

T → T * F | F

I₀ = {[S’ → •S, $]}

Grammar:

S → AB

A → aA | b

B → c

Show the complete macro expansion for:

#define SQUARE(x) ((x) * (x))

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define CUBE(x) (SQUARE(x) * (x))