Homework

Assigned: 5^th week

Due: 6^th week

Represent the following as a NDFSA and then show all of the steps to reduce it to a minimum state DFSA:

d⁺ | d^* . d⁺

Use either the e-closure or table methods as discussed in class. Be sure to show the minimum state DFSA state table and state diagram.

Assigned: 7^th week

Due: 8^th week

Given the following grammar G₁:

D ® D T L ; | e

T ® int | float

L ® L , id | id

(where non-terminals = {D T L}, terminals = { id int float ; ,}, and D is the goal symbol)

1. Eliminate left recursion wherever it occurs and generate a new grammar, G_2, that is equivalent to G₁, but which does not contain left-recursion.
2. Compute the first and follow sets for G₂.
3. Construct an LL(1) parse table for G₂.

Assigned: 10^th week

Due: 11^th week

Chapter 4:

1. 4.34a,

2. 4.39 (SLR(1))

3. 4.40 (LR(1))

Hint: You only have to eliminate left recursion and do left factoring in LL(1) (Top Down) parsing, not SLR(1) or LR(1) (Bottom Up) parsing.

Assigned: 12^th week

Due: 13^th week

1. Given the following grammar:

E ® E + T | T

T ® T * F | F

F ® ( E ) | id

a. Define attributes and write semantic rules that cause a parse to fail if there are more addition operators than multiplication operators in the final expression.

b. Define attributes and write semantic rules that cause a parse to fail if the level of nesting parentheses is greater than three.

2. Given the following grammar where non-terminals are {int_num, int, digit}, terminals are {0,1, 2, 3, 4, 5, 6, 7, 8, 9} and the goal symbol is int_num:

int_num ® + int | - int | int

int ® int digit | digit

digit ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The grammar recognizes signed and unsigned decimal numbers such as 3, 93, and 463268. Define attributes and add semantic rules to the grammar so that the integer numeric value of the number is printed out at the goal non-terminal. Also, assume that n binary bits are available to represent this number. Print out an error if the integer number is larger than the maximum size (for positive signed numbers this would be 2^n-1 and for negative signed integers it would be 2^n-1 - 1).