编译原理二：有限状态机-Toy模板网

这篇具有很好参考价值的文章主要介绍了编译原理二：有限状态机。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 有限状态机介绍

有限状态机是一种计算模型，它可以接受一串输入并根据一组状态转移规则进行状态转移，最终输出一个结果。有限状态机可以分为两种类型：确定性有限状态机（DFA）和非确定性有限状态机（NFA）。

1.1. 确定性有限状态机（DFA）

DFA 是一种状态机，它的每个状态都有一条出边对应每个输入符号，而每个输入符号只能对应一条出边。在实际的编译器实现中，通常使用 DFA 进行词法分析。DFA 能够快速匹配输入的字符串，并且不需要回溯的操作，因此能够有效地提高编译器的词法分析效率。

1.2. 非确定性有限状态机（NFA）

NFA 的每个状态都可以有多条出边对应同一个输入符号。在实际应用中，NFA 通常是通过转换为 DFA 来实现的。NFA 可以描述一些 DFA 不能描述的语言，但是其转换为 DFA 的过程可能需要消耗大量的时间和空间。

1.3. 有限状态机的应用

有限状态机在编译原理中有着广泛的应用。在编译器的词法分析阶段，词法分析器将源代码作为输入，通过有限状态机匹配出其中的词法单元。此外，在其他领域，有限状态机也有一些应用，比如网络协议、自然语言处理、图像处理等等。

有限状态机的实现方式有很多种，比如使用编程语言直接实现、使用专门的工具生成等等。在实际应用中，我们需要根据具体的问题来选择最适合的实现方式和优化策略。

2. 例子：实现一个简易版本的分词

let tokens = []; // 存储分词数据
let NUMBER = /[0-9]/; // 校验数字
let currentToken; // 存每一次的token
const Numeric = "Numeric"; // 数字类型
const Punctuator = "Punctuator"; // 运算符类型
/**
 * 开始状态函数
 * @param {*} char 传递的参数 1,0,+,2,0...
 * @return 下一个状态函数
 */
function start(char) {
  if (NUMBER.test(char)) {
    currentToken = { type: Numeric, value: "" };
  }
  return number(char);
}

function number(char) {
  if (NUMBER.test(char)) {
    // 如果传进来的时数字，就给value赋值
    currentToken.value += char;
    return number;
  } else if (char === "+" || char === "-") {
    // 如果是运算符，就将当前的token传递出去，存到tokens中
    emit(currentToken);
    // 将运算符也存起来
    emit({ type: Punctuator, value: char });
    // 重新开始分词
    currentToken = { type: Numeric, value: "" };
    return number;
  }
}

function emit(token) {
  // 重新计算currentToken
  currentToken = { type: "", value: "" };
  // 更新tokens
  tokens.push(token);
}

function tokenlizier(input) {
  // 开始是start的状态
  let state = start;
  for (let char of input) {
    // 保证每次state都更新
    state = state(char);
  }
  if (currentToken.value.length > 0) {
    // 如果传递的长度大于1则再次开始
    emit(currentToken);
  }
}

tokenlizier("10+20-20");

console.log(tokens);