Assignment 2 

2.1

This question refers to the following regular expressions: 

  digit -> 0 | 1 | ... | 9
  letter -> a | ... | z | A | ... | Z
  id -> letter | letter ( digit | letter)* letter
  1. Construct a nondeterministic finite automaton (NFA) for id .
  2. Convert the NFA into a DFA.
  3. Minimize the DFA by reducing the number of states.
  4. Write a lexical analyzer based on the optimized DFA that uses a transition table.
  5. Write a Lex program for id and compare the lexical analyzer with the hand-written one. 
2.2
Write a lexical analyzer for the language defined by the following grammar: 
Program:
	Assignment*

Assignment:
	Identifier = Exp;

Exp: 
	Exp + Term | Exp - Term | Term

Term:
	Term * Fact  | Fact

Fact:
	( Exp ) | - Fact | + Fact | Literal | Identifier

Identifier:
     	Letter [Letter | Digit]*

Letter:
	a|...|z|A|...|Z|_

Literal:
	0 | NonZeroDigit Digit*
		
NonZeroDigit:
	1|...|9

Digit:
	0|1|...|9
For example, given the following program: 
x = 1;
y = 2;
z = x+y*y;
You analyzer should return the following tokens: 
Identifier x
=
Literal 1
;
Identifier y
=
Literal 2
;
Identifier z
=
Identifier x
+
Identifier y
*
Identifier y
;