前端工程师的编译原理指南-「有限状态机」

19组清风

发布于 2022-02-28 10:06:08

5620

发布于 2022-02-28 10:06:08

文章被收录于专栏：Web Front End

往期回顾

有兴趣的小伙伴可以持续关注我的专栏编译原理，

致力于用最通俗易懂的前端语言帮助更多前端开发者探索编译世界。

前端工程师的编译原理指南-「编译器工作流程」

引言

在上一篇文章中我们讨论了编译器的一次完整工作流程，需要经历解析阶段 (Parsing)、转化阶段 (Transformaiton)、生成阶段 (Code Generation) 三个阶段来处理我们的输入最终得到输出的结果。

在熟悉了编译器的基本工作原理后，接下来我们将会从零实现一款小型 JavaScript 编译器。

不过在开始之前，我会先和你来讨论一下 **“有限状态机”FSM(Finite State Machine)**。

有限状态机

概念

有限状态机的概念其实和 JavaScript 关系并不是很大，但是 JavaScript 中绝大多数状态都可以使用有限状态机来描述。

究竟什么是有限状态机呢，通俗来讲所谓有限状态机不过是一种思想、一种模型。 我们可以使用有限状态机的思想来模拟绝大多数场景。

比方说网页上存在一个按钮元素。当鼠标悬浮在按钮上时会出现弹窗，同样当鼠标离开按钮时候弹窗消失。

针对上述行为，我们试试用状态机来描述这个过程。

我们可以将用户的鼠标行为 Event 抽象成为状态机的输入，将按钮看成状态机。

每次产生用户行为（进行输入）都有可能会改变按钮（状态机）的状态，而按钮（状态机）内部仅仅存在两种合法状态：鼠标悬停被触发和鼠标未悬停未被触发。

当我们在按钮外围（并未进入按钮）移动鼠标时，可以看作每次输入给状态机的都是相同的输入，所以状态机的状态并不会改变。

当鼠标移入按钮内部时，此时因为输入改变，状态机内部根据输入判断到需要改变状态，那么此时按钮（状态机）的状态就会被改变，变成高亮状态并且显示悬浮框。

稍微用伪代码来描述这一过程：

const buttonMachine = {
  // 状态机当前状态
  currentState: 'inVisible',
  // 每次输入会调用transform方法根据输入判断更改当前状态
  transform: function (event) {
    // do something 根据用户行为(event)更改currentState
    switch (this.currentState) {
      case 'visible':
        // do something 更改状态为显示时需要 高亮按钮、显示菜单
        break;
      
      case 'inVisible':
        // do something 更改为隐藏状态时 取消高亮同时隐藏菜单
        break;
      
      default:
        break;
    }
  }
}

每次鼠标移动都会产生输入从而进入状态机的 transform 方法，判断是否需要更改状态机的当前状态以及状态变化时随之而来的逻辑处理。

作用

之所以将有限状态机单独拿出来讲，主要是因为我们在上一篇中提到编译器对于输入字符串进行分词时，比如：

<div id="app"><p>hello</p>Jue Jin</div>

在分词阶段它会被分成一个一个 Token：

 [
   {"type": "Punctuator", "value": "<"},
   {"type": "JSXIdentifier","value": "div"}, 
   {"type": "JSXIdentifier","value": "id"}, 
   {"type": "Punctuator","value": "="},
   {"type": "String","value": "\"app\""}, 
   {"type": "Punctuator","value": ">"}, 
   {"type": "Punctuator","value": "<"},
   {"type": "JSXIdentifier","value": "p"},
   {"type": "Punctuator","value": ">"},
   {"type": "JSXText","value": "Hello"},
   {"type": "Punctuator","value": "<"},
   {"type": "Punctuator","value": "/"},
   {"type": "JSXIdentifier","value": "p"},
   {"type": "Punctuator","value": ">"},
   {"type": "JSXText","value": "Jue Jin"},
   {"type": "Punctuator","value": "<"},
   {"type": "Punctuator","value": "/"},
   {"type": "JSXIdentifier","value": "div"},
   {"type": "Punctuator","value": ">"}
]

而这一步恰恰是利用有限状态机来处理的，当然分词有很多途径。比如粗暴的直接使用正则进行分词等等方式，但使用状态机进行分词是最优雅且强大的方式。

同样在之后我们去实现这个过程，这一步在了解了状态机的概念之后。我们现在尝试手写一个小型状态机来帮助我们来消化上边的概念。

小型状态机

上边阐述了状态机的基本概念，接下来让我们结合一个 Demo 来尝试使用状态机来进行词法分析。

比如一段简单的四则运算：

100+200-300

我们需要将上述的语句使用状态机分成以下结构：

[
    { type: 'Numeric', value: '100' },
    { type: 'Punctuator', value: '+' },
    { type: 'Numeric', value: '200' },
    { type: 'Punctuator', value: '-' },
    { type: 'Numeric', value: '300' }
]

这一步其实就是被称为词法分析，不过此时我们实现的状态机仅仅考虑两种状态：Numeric（数字）和（Punctuator）标点符号。

所谓使用状态机分词的过程既是将整体输入（输入代码）按照每个字符去依次读取每个字符，根据每次读到的字符更改当前状态从而执行对应的逻辑。

整个过程我们可以用一张图来描述：

接下来就让我们用代码来实现图中的所有过程：

首先让我们创建分词过程中的一些基础变量：

// 匹配数字的正则
const NumReg = /[0-9]/
// 匹配标点符号的正则规则
const PunctuatorReg = /[\+\-\*/]/

// 最终输出的所有tokens合集
const tokens = []

// 当前状态机中正在处理的token
let currentToken = {}

// 分词函数 接受输入的字符串代码
function tokenizer(input) {
    // dosome thing
}

// 打印分词结果
console.log(tokenizer('100+200-300'))

首先我们定义了：

NumReg、PunctuatorRef 这两个正则匹配规则，这里我们仅仅只考虑基础的加减乘除和数字的分词。
tokens 作为保存最终分词的结果。
currentToken 为当前状态机中正在处理的 Token 。
tokenizer 顾名思义，这个方法是进行词法分析的核心处理函数。

接下来我们需要在 tokenizer 函数中使用有限状态机来进行分词。

首先针对输入的字符 "100+200-300" ，我们需要迭代每一个字符从而将匹配的 Token 加入 Tokens 中去。

同时我们需要维护一个内部状态作为每次输入字符后当前的状态，比如说

当分析到 “1” 时，因为本次输入我们需要改变状态机内部状态为 'Numeric' ，继续迭代下一个字符 “0”，此时因为 "1" 和 "0" 是一个整体可以不被分开的。

所以当输入 “2” 时，状态仍然是 'Numeric' ，而此时我们仅仅修改 currentToken 的 value ，将它从 "1" 变成 "10" 即可，同理直到分析到 “100” 。

当分析到 "+" 时，状态机中输入为 “+” 显然 “+” 是一个标点符号，它并不能和上一次的 “100” 拼接在一起。所以此时我们将上一次的 currentToken 也就是 "100" 推入 Tokens 中，同时改变状态机状态为 "Punctuator" ... 依次类推。

我们重点先来看看所谓 tokenizer 函数的实现：

// ...

function tokenizer(input) {
    // 定义状态机的初始状态判断函数
    let state = start
    // 依次迭代输入的字符串
    input.split("").forEach(char => {
        // 此处的char是每一个字符
        // 调用state函数 并且传入char
        state = state(char)
    })
    return tokens
}

接下来我们来一步一步拆解 tokenizer 函数究竟是在做什么。

重点让我们先来放在这个 forEach 函数上，我们对于输入的 input （需要进行分词的源代码）进行依次迭代，所以每个字符（char）可以认为是每次对于状态机的输入。

关于 state 函数，本质上他是上一次输入返回的处理函数，此时不必深究 state 函数。我会在之后为你讲述它的作用。

首先，第一次输入时状态机并不存在任何前置状态。所以我们需要定义一个 start 函数来初始化状态机处理函数，也就是这一句代码：

function tokenizer(input) {
    // ...
    let state = start
    // ...
}

/**
 * 状态机初始函数
 * @param {*} char 输入的字符
 * @return {*} 
 */
function start (char) {
    if(NumReg.test(char)) {
        // 首个输入的char是数字 初始化token为numeric
        currentToken = { type: 'Numeric', value: char }
        // 返回的是一个nunmer的处理函数
        return numeric
    }else if (PunctuatorReg.test(char)) {
        // 首个输入的char是标点符号 初始化current为punctuator
        currentToken = { type: 'Punctuator', value: char }
        // 返回的是一个punctuator的处理函数
        return punctuator
    }
}

在 start 函数中，主要处理两件事：

根据首次输入的 char 初始化 currentToken ，比如这里我们输入 "100+200-300" 时，第一个输入的 char 为 “1” ，初始化阶段会以 { type: 'Numeric', value: '1' } 来初始化 currentToken。
其次，初始化了 curerntToken 之后状态机会根据当前输入来决定当前状态机内部的状态。

比如说上边我们初始化了 currentToken 为 { type: 'Numeric', value: '1' } 时，此时状态机内部根据输入保留了状态为 'numeric' 状态。

当下一次产生输入时会用上一次状态处理函数来处理（这里是返回的 numeric）。 之所以这么做是因为当我们在状态机内部输入 “1” 时，那么我们返回 numeric （数值的处理函数）。

下一次输入存在两种可能：

第一种为输入的 “0” 仍然为一个 number 类型的数字，因为我们清楚上一次处理的输入仍然是数字所以此时我们仅仅需要修改 currentToken 的 value 为 “10” 即可，两次输入并不会被分开处理。
第二种情况下，假使 “1” 后边紧跟着的是标点符号比如 “+” ，那么状态机中上一次处理结果返回的 numeric 函数中接受到输入为 “+” ，显示它们并不是一个词法内，是需要进行重新分词的。

所以这里我们通过本次的输入来返回下一次的处理函数从而判断是否应该分词 or 连续。

本质上每个 char 可以看作状态机内部的输入，而每次处理完成返回的函数比如 numeric、punctuator 可以看作根据输入确定的状态。我们会在每次输入时，结合上一次状态机的状态（返回的处理函数）来处理词法分析阶段当前输入（char）是否和上一次连续。

在这之后，我们来看看所谓的 numeric（数值处理函数）和 punctuator（标点符号处理函数）的具体内容：

// numeric
function numeric(char) {
    if(NumReg.test(char)) {
        // 如果当前输入是数字 不分词 连续累加value值
        currentToken.value += char
        // 返回numeric函数赋给state
        return numeric
    }else if (PunctuatorRef.test(char)) {
        // 如果是标点符号 分词
        // 如果当前输入的标点符号 进行分词
        // 首先将旧的token输入到tokens中
        emitToken(currentToken)
        // 修改当前token
        currentToken = { type: 'Punctuator', value: char }
        // 返回punctuator处理函数
        return punctuator
    }
}

我们可以看到 numeric 函数处理的逻辑非常简单，当本次输入进入 numeric 处理函数函数中时表示状态机中上一次处理的结果一定是一个 numeric 类型的输入字符。

此时我们仅仅需要在 numeric 中根据输入判断应该如何处理本次的输入，比如输入 numeric 的 char 为 "3" 时表示本次仍然为 numeric 类型，那么此时我并不需要进行分词而是拼接上一次 token 的 value 值。

而假使本次输入为 "+" ，那么此时因为本次的 “+” 和上一次的 "numeric" 类型显然是需要进行分词的，所以此时：

首先会进行 emitToken(currentToken) 将上一次的分词结果保存进入最终的 token 中。
之后我们修改 currentToken 为本次输入的 Punctuator 类型。
随后返回名为 punctuator 的函数作为状态机中的状态作为下一次的处理状态函数。

稍后我们会实现 emitToken 方法的逻辑。它其实很简单，作用就是将 currentToken 塞入到最终输入的 token 数组中，仅此而已。

之后我们来实现一下 punctuator 函数，它和 numeric 存在相同的逻辑，本质上分词时使用状态机进行处理就是根据以本次分到的 char（单词）作为输入传入上一次输入的输入函数状态进行分词的一个过程。

// 标点符号状态处理函数
function punctuator(char) {
  // 无论如何都要发射 因为标点符号在分词阶段不会被拼接起来
  emitToken(currentToken)
  if (NumReg.test(char)) {
    currentToken = { type: 'Numeric', value: char }
    return numeric
  } else if (PunctuatorRef.test(char)) {
    currentToken = { type: 'Punctuator', value: char }
    return punctuator
  }

  return punctuator
}

关于 punctuator 它和 numeric 稍稍有些不同，但凡输入为标点符号，我们都希望立即进行分词而不进行拼接。

所以每次进入 punctuator 函数的第一件事情就是进行 emitToken(currentToken) 发射上一次的分词结果 currentToken ，之后才会根据本次输入的 char 进行匹配返回对应状态函数。

比如分词到第一个 ”2“ 时：

此时因为上一次的状态机中保留的状态处理函数为 punctuator ，所以输入 char（2）会进入 punctuator 函数处理。

也就是它首先会将上一次的 "+" 直接输出到最终的 tokens 中去，之后根据本次的输入修改状态机的状态函数。

有的同学可能会存在疑惑，那么如果进行词法分析的内容存在链接的合法标点符号还会进行拼接吗？

比如我们在 JavaScript 中经常使用的自增（++）和自减（++）操作运算符，通常它们都是成双的使用那么在分词阶段需要将这两个单词进行拼接吗。

答案是否定的，通常在进行词法分析的过程中我们仅仅需要按照基本的词法规则将传入的字符串分割成为一个个 token ，至于自增自减等等之类依据上下文输入的语法，我们会在语法分析阶段来详细处理他们。

当然这里我们的重点并不是词法分析，重点是想通过分词的过程告诉大家有限状态机的概念和使用。

最后，我们来实现所谓的 emitToken 函数：

function emitToken(token) {
  // 重制 currentToken
  currentToken = { type: '', value: '' }
  // 将上一次传入的token参数保存到最终输入的tokens中
  tokens.push(token)
}

它简单的不过如此，重制 currentToken 并且将 currentToken 塞入到最终输入的 token 数组中，仅此而已。

写到这里，我们通过状态机来实现词法分析的小例子已经实现的差不多了。让我们来运行一下代码查看下输出的对应结果：

看起来还不错对吧。不过，好像少了一个 “300”的 token 。这是因为在 tokenizer 函数中 forEach 结束后我们对于最后一次分词结果没有进行任何处理。

我们需要在遍历停止后，需要将最后一次的分词结果同样输入到 tokens 中。就像这样：

function tokenizer(input) {
  // 初始化状态机的状态
  let state = start
  input.split('').forEach(char => {
    state = state(char)
  })
  遍历结束后仍然需要发送一次最后
  tokens.push(currentToken)
  return tokens
}

至此，我们重新运行代码

控制台打印出我们如期的结果，当然我们现在实现的词法分析非常简单仅仅支持标点符号和数字的分词。

不过我们的重点并不是词法分析，希望大家通过这个简单的例子来明白什么是有限状态机，通过代码实例来理解它的概念。

结尾

文中我并没有堆砌太多所谓有限状态机的相关概念，对于有限状态机的概念和如何应用目前大家可以理解文章的例子其实就已经足够了，之后我们会在正式阶段的词法分析详细使用它。

所谓有限状态机不过是一种模型、一种概念。我们可以在任何场景下将它尝试理解成为有限状态机模型来进行处理。

下一篇文章我们会正式进入主题，带领大家去打造一款小型JavaScript编译器。有兴趣的小伙伴可以持续关注我的专栏编译原理。

代码

完整的代码在这里。

const NumReg = /[0-9]/
const PunctuatorRef = /[\+\-\*/]/

// 保存所有格式化的token
const tokens = []
// 当前正在处理的token 
let currentToken = {}

function emitToken(token) {
  // 重制 currentToken
  currentToken = { type: '', value: '' }
  // 将上一次传入的token参数保存到最终输入的tokens中
  tokens.push(token)
}
// 
/**
 * 状态机初始函数
 * @param {*} char 输入的字符
 * @return {*} 
 */
function start(char) {
  // 如果输入是一个数字
  if (NumReg.test(char)) {
    // 初始化 currentToken 为 Numeric类型
    currentToken = { type: 'Numeric', value: char }
    return numeric
  } else if (PunctuatorRef.test(char)) {
    // 初始化 currentToken 为 Punctuator 类型
    currentToken = { type: 'Punctuator', value: char }
    return punctuator
  }
}

// 或许是不一样的
function numeric() {
  // XiWang
  const number = 
}

// 当前进入数字状态
function numeric(char) {
  if (NumReg.test(char)) {
    // 如何匹配的是number
    currentToken.value += char
  } else if (PunctuatorRef.test(char)) {
    // 如果此时匹配标点符号 表示状态需要被改变了
    // 首先将旧的token输入到tokens中
    emitToken(currentToken)
    currentToken = { type: 'Punctuator', value: char }
    return punctuator
  }
  // 返回当前状态函数 下次迭代仍然会调用该函数执行
  return numeric
}

// 标点符号处理函数
function punctuator(char) {
  // 无论如何都要发射 因为标点符号在分词阶段不会被拼接起来
  emitToken(currentToken)
  if (NumReg.test(char)) {
    currentToken = { type: 'Numeric', value: char }
    return numeric
  } else if (PunctuatorRef.test(char)) {
    currentToken = { type: 'Punctuator', value: char }
    return punctuator
  }

  return punctuator
}

function tokenizer(input) {
  // 初始化状态机的状态
  let state = start
  input.split('').forEach(char => {
    state = state(char)
  })
  // 遍历结束后仍然需要发送一次最后
  tokens.push(currentToken)
  return tokens
}

console.log(tokenizer('100+200-300'))

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022/02/14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法