Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package lexer;
- import java.util.Arrays;
- import java.util.HashMap;
- import symbols.Tokens.Token;
- /**
- * Abstract class for Deterministic Finite Automata.
- */
- public abstract class AbstractDFA {
- // Token that is recognized by this automaton
- protected Token token;
- // TODO: use data structure for representing
- // - states
- // - final states (and sink states)
- // - transitions of the form (state, input) -> state
- // - current state
- private int currentState; // Current State with -1 as the SinkState and 0 as the StartState
- private HashMap<Integer, Character> stateType = new HashMap<Integer, Character>(); // With Character in {F,N,S} (Final,Nonfinal,Sink}
- private HashMap<Integer, HashMap<Character, Integer>> stateSelection = new HashMap<Integer, HashMap<Character, Integer>>();
- private HashMap<Character, Integer> stateTransition = new HashMap<Character, Integer>();
- /**
- * Constructor for Abstract DFA.
- *
- * @param token
- * Token recognized by this automaton.
- * @param noStates
- * Number of states in the DFA.
- */
- public AbstractDFA(Token token, int noStates) {
- this.token = token;
- // TODO: initialize data structures
- currentState = 0;
- stateType.put(-1, 'S');
- // Hier muesste die Erstellung des Automaten hin, also stateSelection und stateTransition besetzen, wie noetig, glaube ich
- }
- /**
- * Reset the automaton to the initial state.
- */
- public void reset() {
- // TODO: reset automaton to initial state
- currentState = 0;
- }
- /**
- * Performs one step of the DFA for a given letter. If there is a transition
- * for the given letter, then the automaton proceeds to the successor state.
- * Otherwise it goes to the sink state. By construction it will stay in the
- * sink for every input letter.
- *
- * @param letter
- * The current input.
- */
- public void doStep(char letter) {
- // TODO: do step by going to the next state according to the current
- // state and the read letter.
- if(stateTransition.get(letter)!=null) {
- currentState = stateTransition.get(letter);
- }
- else {
- currentState = -1;
- }
- }
- /**
- * Check if the automaton is currently accepting.
- *
- * @return True, if the automaton is currently in the accepting state.
- */
- public boolean isAccepting() {
- // TODO: return if the current state is accepting
- if(stateType.get(currentState).equals('F')) {
- return true;
- }
- return false;
- }
- /**
- * Run the DFA on the input.
- *
- * @param inputWord
- * String that contains the input word
- * @return True, if if the word is accepted by this automaton
- */
- public boolean run(String inputWord) {
- this.reset();
- char[] inputCharWord = inputWord.toCharArray();
- for (char letter : inputCharWord) {
- doStep(letter);
- }
- return isAccepting();
- }
- /**
- * Checks if the final state can be reached from the current state.
- *
- * @return True, if the state is productive, i.e. the final state can be
- * reached.
- */
- public boolean isProductive() {
- // TODO: return if the current state is productive
- if(stateType.get(currentState).equals('F')) { // Preemptive Final State Check
- return true;
- }
- if(stateType.get(currentState).equals('S')) { // Preemptive Sink State Check
- return false;
- }
- HashMap<Character, Integer> productiveTransition = stateSelection.get(currentState); // get transitions of current State
- for(Character s: productiveTransition.keySet()) {
- if(stateType.get(productiveTransition.get(s)).equals('F')) {
- return true;
- }
- }
- return false;
- }
- /**
- * @return The Token that this automaton recognizes
- */
- public Token getToken() {
- return token;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement