HaileyLHanson@gmail.com
Here is a regular expression engine written in Java. The program reads in a text file as regular expressions separated by new lines.
The regular expressions are taken in in postfixed notation and then created into Nondeterministic Finite Automata (NFA).
To build the software, the text file titled test.txt will need to be present. The file can then be run within a Java compiler(I used Eclipse Kepler).
The files included in this archive are:
1) Main.java
My main program that calls upon my other processes
2) Machine.java
Where the bulk of my program sits and constructs NFAs from reading Regular Expressions in through a text file
3) FinAut.java
Where my Finite Automata object is stored
4) Transition
This is where my regular expression transitions are stored as linked lists
******************************************************
package home;
//import Machine;
public class Main {
public static void main(String[] args) {
new Machine();
}
}
*****************************************************
package home;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
public class Machine {
private BufferedReader br;
private String line;
int i = 0;
private LinkedList
private int currentState = 0;
private FinAut FA1; // FinAut
private FinAut FA2;
public Machine()
{
FAmachine = new LinkedList
try
{
br = new BufferedReader(new FileReader("test.txt"));
} catch (FileNotFoundException e1)
{
e1.printStackTrace();
}// read in a line from RE
int i = 0;
char c;
try
{
while ((line = br.readLine()) != null)
{
for (i = 0; i < (line.length()); i++)
{
c = line.charAt(i);
System.out.println(c);
if (c == '&')
{
FA2=FAmachine.pop();
FA1=FAmachine.pop();
FA1.listOfTransitions.add(new transition(FA1.endState,FA2.startState,'E')); //add epsilon transition onto end of FA1
while (!FA2.listOfTransitions.isEmpty()){//while not at end of list
FA1.listOfTransitions.add(FA2.listOfTransitions.remove());//take end of FA2 and put at end of FA1
}
FA1.endState = FA2.endState; //make FA1 into the new single FA
FAmachine.push(FA1);// push(NFA that accepts the concatenation of
for(i=0;i
}//end of for loop
}
else if (c == '+')// push(NFA that accepts L(nFA1) + L(nFA2));
{
FA2 =FAmachine.pop();
FA1 = FAmachine.pop();
FA1.listOfTransitions.add(new transition(currentState++, FA1.startState, 'E'));//epsilon from new start to FA1 old start
FA1.listOfTransitions.add(new transition(currentState-1, FA2.startState, 'E'));//epsilon from new start to FA2 old start
FA1.listOfTransitions.add(new transition(FA1.endState, currentState++, 'E'));//epsilon from FA1 end to new end
FA1.listOfTransitions.add(new transition(FA2.endState, currentState-1, 'E'));//epsilon from FA2 end to new end
FA1.startState = currentState-1;//update FA1 start to new start
FA1.endState = currentState; //update FA1 end to new end
//take transitions from errthang and put into FA1
while (!FA2.listOfTransitions.isEmpty()){//while not at end of list
FA1.listOfTransitions.add(FA2.listOfTransitions.remove());//take end of FA2 and put at end of FA1
}
for(i=0;i
// System.out.println("+");
} else if (c == '*')
{
FA2 =FAmachine.pop();
FA1 = FAmachine.pop();
FA1.listOfTransitions.add(new transition(currentState++, FA1.startState, 'E'));//epsilon from new start to FA1 old start
FA1.listOfTransitions.add(new transition(currentState-1, FA2.startState, 'E'));//epsilon from new start to FA2 old start
FA1.listOfTransitions.add(new transition(FA1.endState, currentState-1, 'E'));//epsilon from FA1 end to new start
FA1.listOfTransitions.add(new transition(FA2.endState, currentState-1, 'E'));//epsilon from FA2 end to new start
FA1.listOfTransitions.add(new transition(currentState++, FA1.startState, 'E'));//make all new start state with epsilon transition
FA1.startState = currentState-1;//update FA1 start to new start
//take transitions from errthang and put into FA1
while (!FA2.listOfTransitions.isEmpty()){//while not at end of list
FA1.listOfTransitions.add(FA2.listOfTransitions.remove());//take end of FA2 and put at end of FA1
}
for(i=0;i
} else
{
FAmachine.push(new FinAut(currentState++, currentState++, c));
//System.out.println("c = " + c);
}
// System.out.println(line.next());
//System.out.println("line # ");
}
}
} catch (IOException e)
{
e.printStackTrace();
}// end of while
finally {
if (br != null)
{
// br.close();
}
}
}
}// end of class Machine
******************************************************
package home;
import java.util.LinkedList;
public class FinAut {
public int startState;
public int endState;
public LinkedList
public FinAut(int start, int end, char c) {
this.startState = start;
this.endState = end;
listOfTransitions = new LinkedList
listOfTransitions.add(new transition(startState, endState, c));
}// end of FinAut method
}// end of FinAut class
************************************************
package home;
public class transition {
int state1;
int state2;
char symbol;
public transition(int startState, int endState, char c){
this.state1=startState;
this.state2=endState;
this.symbol=c;
}//end of transition method
}//end of class transition
No comments:
Post a Comment