使用DFA做文本编辑器的自动提示

Mon, 11 Jul 2016 07:59:17 +0000

之前看龙书的时候，龙书提到可以在编译器里用动态的生成的NFA自动机来动态匹配自己的输入串，NFA的简单实现其实写起来非常简单，但是我是实际凭感觉写完之后，却觉得并不是非常的好用，在处理自己已经输入过的串，如果还要处理空串和一个符号对应多种路径就势必涉及回溯，所以我就动态生成了一个DFA，应该不是最简的，但是也能满足需求。

DFA状态

package sample;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * Dfa 状态
 *
 * @author liufengkai
 * Created by liufengkai on 16/7/10.
 */
public class DfaState implements Comparable<DfaState> {

 private static int DFA_ID_COUNT = 0;
 /**
 * state id
 */
 private int stateId;
 /**
 * transition set
 * char / set of dfaState
 */
 private Map<Integer, DfaState> transitionSet;

 private DfaState parentState;

 private Integer parentInput;

 /**
 * 构造方法
 *
 * @param input 输入串
 * @param parentState 父节点
 */
 public DfaState(Integer input, DfaState parentState) {
 this.parentInput = input;
 this.parentState = parentState;
 this.stateId = DFA_ID_COUNT++;
 this.transitionSet = new HashMap<>();
 }

 /**
 * 添加一条转移语句
 *
 * @param input 输入字符
 * @param state 下一个状态
 * @return 返回添加状态
 */
 public DfaState addTransition(int input, DfaState state) {

 if (!transitionSet.containsKey(input)) {
 transitionSet.put(input, state);
 }

 return state;
 }

 public DfaState getTransitionInput(int input) {
 return getTransitionSet().get(input);
 }

 public int getStateId() {
 return stateId;
 }

 public static int getTotalNumber() {
 return DFA_ID_COUNT;
 }

 public Map<Integer, DfaState> getTransitionSet() {
 return transitionSet;
 }

 public DfaState getParentState() {
 return parentState;
 }

 @Override
 public int compareTo(DfaState o) {
 return 0;
 }

 public int getParentInput() {
 return parentInput;
 }

 /**
 * 打印状态
 */
 public void printState() {
 System.out.println("state : " + getStateId());
 for (Integer integer : transitionSet.keySet()) {
 System.out.println("symbol: " +
 (char) integer.intValue() + " to :" +
 transitionSet.get(integer).getStateId());
 transitionSet.get(integer).printState();
 }
 }

 /**
 * 返回结束状态
 *
 * @param list 传入结束状态
 */
 public void returnEndList(ArrayList<DfaState> list) {
 for (Integer key : transitionSet.keySet()) {
 DfaState cur = transitionSet.get(key);
 if (cur.getTransitionSet().isEmpty()) {
 list.add(cur);
 } else {
 cur.returnEndList(list);
 }
 }
 }
}

DFAState定义了很多基础的方法，比如每个状态都有唯一的ID值与之对应，虽然是一个DFA但是插入的过程是发现下一个节点不同才分叉，由此看来每个状态都应该有唯一的父节点与之对应，使用了一个Map来记录我们有哪些路径，还有一个方法来递归查找终结节点，使用这个方法来倒序查找预测分析出的字符串，这并不是一个效率很高的方法，之后也会被替换。

自动机 on lfkdsk's Blog

使用DFA做文本编辑器的自动提示

DFA状态