Consider the following grammar rules in YACC notations: %% Exp : Term | Exp '+' Term ; Term : Factor | Term '*' Factor ; Factor : Primary | Primary '^' Factor ; Primary : Id | '(' Exp ')' ; Id : 'a' ; %% 

Note that ^ denotes the exponentiation operator, which is right associative.

Question: Compute the FIRST and FOLLOW sets, and the DFA with item sets.

Note. Here is the y.output file for reference

Grammar

0 $accept: Exp $end

1 Exp: Term 2 | Exp '+' Term

3 Term: Factor 4 | Term '*' Factor

5 Factor: Primary 6 | Primary '^' Factor

7 Primary: Id 8 | '(' Exp ')'

9 Id: 'a'

Terminals, with rules where they appear

$end (0) 0 '(' (40) 8 ')' (41) 8 '*' (42) 4 '+' (43) 2 '^' (94) 6 'a' (97) 9 error (256)

Nonterminals, with rules where they appear

$accept (9) on left: 0 Exp (10) on left: 1 2, on right: 0 2 8 Term (11) on left: 3 4, on right: 1 2 4 Factor (12) on left: 5 6, on right: 3 4 6 Primary (13) on left: 7 8, on right: 5 6 Id (14) on left: 9, on right: 7

State 0

0 $accept: . Exp $end

'(' shift, and go to state 1 'a' shift, and go to state 2

Exp go to state 3 Term go to state 4 Factor go to state 5 Primary go to state 6 Id go to state 7

State 1

8 Primary: '(' . Exp ')'

'(' shift, and go to state 1 'a' shift, and go to state 2

Exp go to state 8 Term go to state 4 Factor go to state 5 Primary go to state 6 Id go to state 7

State 2

9 Id: 'a' .

$default reduce using rule 9 (Id)

State 3

0 $accept: Exp . $end 2 Exp: Exp . '+' Term

$end shift, and go to state 9 '+' shift, and go to state 10

State 4

1 Exp: Term . 4 Term: Term . '*' Factor

'*' shift, and go to state 11

$default reduce using rule 1 (Exp)

State 5

3 Term: Factor .

$default reduce using rule 3 (Term)

State 6

5 Factor: Primary . 6 | Primary . '^' Factor

'^' shift, and go to state 12

$default reduce using rule 5 (Factor)

State 7

7 Primary: Id .

$default reduce using rule 7 (Primary)

State 8

2 Exp: Exp . '+' Term 8 Primary: '(' Exp . ')'

'+' shift, and go to state 10 ')' shift, and go to state 13

State 9

0 $accept: Exp $end .

$default accept

State 10

2 Exp: Exp '+' . Term

'(' shift, and go to state 1 'a' shift, and go to state 2

Term go to state 14 Factor go to state 5 Primary go to state 6 Id go to state 7

State 11

4 Term: Term '*' . Factor

'(' shift, and go to state 1 'a' shift, and go to state 2

Factor go to state 15 Primary go to state 6 Id go to state 7

State 12

6 Factor: Primary '^' . Factor

'(' shift, and go to state 1 'a' shift, and go to state 2

Factor go to state 16 Primary go to state 6 Id go to state 7

State 13

8 Primary: '(' Exp ')' .

$default reduce using rule 8 (Primary)

State 14

2 Exp: Exp '+' Term . 4 Term: Term . '*' Factor

'*' shift, and go to state 11

$default reduce using rule 2 (Exp)

State 15

4 Term: Term '*' Factor .

$default reduce using rule 4 (Term)

State 16

6 Factor: Primary '^' Factor .

$default reduce using rule 6 (Factor)