Thompson’s construction Compiler project

Job Description:

For this task you need to implement Thompson’s construction for converting a regular expres- sion to an equivalent NFA. Description of Thompson’s construction can be found in Chapter 3 of the textbook and at [login to view URL]’s_construction.

2 Requirements

• We make the following assumptions for simplicity.

a) The alphabet Σ of the regular expression is always the binary alphabet {0, 1}.

b) Regular expressions do not include ∅.

c) The empty string ε is represented by e.

d) ◦ is represented by . and ∪ by |.

e) Regular expressions are represented in postfix notation.

f) States of the resulting NFA are numbers.

g) For a postfix regular expression R, states introduced by NFA equivalent to a prefix of R are smaller (as numbers) than states introduced by NFA equivalent to longer prefixes of R. For operators (such as concatenation and *) which introduce a start and an accept state, the start state is smaller (as a number) than the accept state.

• You should implement a class constructor RegToNFA and a method toString.

• RegToNFA takes one parameter which is a string description of a postfix regular expression

and constructs the equivalent NFA as per Thompson’s construction.

• toString returns a string describing the NFA resulting from Thompson’s construction. A string describing the NFA resulting from Thompson’s construction is of the form N#I#F#Z#O#E.

– N is the number of states of the NFA.

– I is the initial state.

– F is the final state.

– Z, O, and E, respectively, represent the 0-transitions, the 1-transitions, and the ε-transitions.

1

– Z, O, and E are semicolon-separated sequences of pairs of states; each pair is a comma-separated sequence of two states. A pair i, j represents a transition from state i to state j; for Z this means that δ(i,0) = j, similarly for O and E. These pairs are sorted by the source state and (if multiple pairs share the same source state, due to non-determinism) then by the destination state.

– For example, toString, being invoked on a a RegToNFA object representing the regular expression 01|, should return the string 6#4#5#0,1#2,3#1,5;3,5;4,0;4,2

Compétences : Java

Nº du projet : #33245667