JavaScript 有限状态机（Finite State Machine）基础与实现

解释

状态机(有限状态机，Finite State Machine)是一个抽象的数学模型， 由以下部分组成

• 有限的状态集合
• 可能触发状态转换的输入集合
• 转移函数 定义在特定状态下接收到特定输入时如何转换状态
• 初始状态：状态机的起始点
• 终止状态集合 标识处理完成的特殊状态

特征

1. 状态总数有限
2. 任一时刻，只处在一种状态之中
3. 某种条件下，会从一种状态转变到另一种状态

两种类型

1. 摩尔型(Moore)状态机 - 输出只依赖于当前状态，与输入无关
2. 米利型(Mealy)状态机 - 输出依赖于当前状态和输入

示例

以之前的 抽象语法树 项目为例

// enums.ts

/** 1. 有限的状态集合 */
export enum FSMState {
  // 输入状态
  Idle = 'IDLE',
  // 验证状态
  ValidatingInput = 'VALIDATING_INPUT',
  // 生成AST树
  BuildingAst = 'BUILDING_AST',
  // 渲染AST树
  RenderingAst = 'RENDERING_AST',
  // 更新历史
  UpdatingHistory = 'UPDATING_HISTORY',
}

/** 2. 可能触发状态转换的输入集合 */
export enum FSMEventType {
  UserInput = 'USER_INPUT',
  ValidationSuccess = 'VALIDATION_SUCCESS',
  BuildAstSuccess = 'BUILD_AST_SUCCESS',
  RenderComplete = 'RENDER_COMPLETE',
  SelectAst = 'SELECT_AST',
}

export type BinaryOp = '+' | '-' | '*' | '/';

export type AstNode =
  | number
  | {
      left: AstNode;
      right: AstNode;
      binaryOp: BinaryOp;
    };

export type FSMEvent =
  | { type: FSMEventType.UserInput; payload: { left: string | AstNode; right: string | AstNode; op: BinaryOp } }
  | { type: FSMEventType.ValidationSuccess }
  | { type: FSMEventType.BuildAstSuccess; ast: AstNode }
  | { type: FSMEventType.RenderComplete }
  | { type: FSMEventType.SelectAst; ast: AstNode };

// fsm.ts

import { FSMState, FSMEventType, FSMEvent, AstNode, BinaryOp } from './enums';

export class AstBuilderFSM {
  /** 3. 初始状态 */
  private state: FSMState = FSMState.Idle;
  private currentInput: { left: string | AstNode; right: string | AstNode; op: BinaryOp } | null = null;
  private currentAst: AstNode | null = null;
  private history: AstNode[] = [];

  constructor(private onRender: (ast: AstNode) => void) {}
  /** 4. 转移函数 */
  dispatch(event: FSMEvent) {
    switch (this.state) {
      case FSMState.Idle:
        if (event.type === FSMEventType.UserInput) {
          this.currentInput = event.payload;
          this.state = FSMState.ValidatingInput;
          this.validateInput();
        } else if (event.type === FSMEventType.SelectAst) {
          this.dispatch({
            type: FSMEventType.UserInput,
            payload: { left: event.ast, right: 0, op: '+' },
          });
        }
        break;

      case FSMState.ValidatingInput:
        if (event.type === FSMEventType.ValidationSuccess) {
          this.state = FSMState.BuildingAst;
          this.buildAst();
        }
        break;

      case FSMState.BuildingAst:
        if (event.type === FSMEventType.BuildAstSuccess) {
          this.currentAst = event.ast;
          this.state = FSMState.RenderingAst;
          this.renderAst();
        }
        break;

      case FSMState.RenderingAst:
        if (event.type === FSMEventType.RenderComplete) {
          this.state = FSMState.UpdatingHistory;
          this.updateHistory();
        }
        break;
      /** 5. 终止状态集合 标识处理完成的特殊状态 */
      case FSMState.UpdatingHistory:
        this.state = FSMState.Idle;
        break;
    }
  }

  private validateInput() {
    const { left, right } = this.currentInput!;
    const isValid = (val: unknown) => typeof val === 'number' || typeof val === 'string' || typeof val === 'object';

    if (isValid(left) && isValid(right)) {
      this.dispatch({ type: FSMEventType.ValidationSuccess });
    } else {
      console.warn('Invalid input');
      this.state = FSMState.Idle;
    }
  }

  private buildAst() {
    const { left, right, op } = this.currentInput!;
    const parseVal = (v: string | AstNode): AstNode => {
      if (typeof v === 'string') {
        const parsed = parseFloat(v);
        return isNaN(parsed) ? 0 : parsed;
      }
      return v;
    };

    const ast: AstNode = {
      left: parseVal(left),
      right: parseVal(right),
      binaryOp: op,
    };

    this.dispatch({ type: FSMEventType.BuildAstSuccess, ast });
  }

  private renderAst() {
    if (this.currentAst) {
      this.onRender(this.currentAst);
      this.dispatch({ type: FSMEventType.RenderComplete });
    }
  }

  private updateHistory() {
    if (this.currentAst) {
      this.history.push(this.currentAst);
    }
    this.state = FSMState.Idle;
  }

  getHistory(): AstNode[] {
    return this.history;
  }

  getCurrentState(): FSMState {
    return this.state;
  }
}

部分相关js库

1. xstate
2. machinajs