编译程序中的词法分析器的输出是二元组( 二 )

(2) 缺点

逻辑非常复杂
可能存在回溯情况，可能需要记忆已匹配的前N个字符，效率低
大量IF判断，可维护性差，扩展性差

2、DFA法
DFA即deterministic finite automaton有限状态自动机，其特点是可以实现状态的自动转移，可以用于解决字符匹配问题
(1) 核心构成
DFA的核心构成要素是状态和状态的转移

定义自动机所具备的N种状态，并定义初始状态
定义上一个状态转移至下一个状态的条件

文章插图
(2) 应用实践
如何用DFA实现词法分析器呢，步骤如下

先定义不同的状态：如操作符状态、数字状态、符号状态等
再定义状态转移条件：如当前状态是初始状态，遇到数字则转移至数字状态，遇到符号则转移至符号状态
如果字符读取完成，则整个转移过程结束

(3) 伪代码

let state = 0; // 当前状态, 也是初始状态while ((ch = nextChar()) !== false) { let match = false; // 获取下一个状态, 如果下一个状态不是初始状态, 则说明匹配成功 let nextState = getNextState(ch, state); if (nextState) { match = true; } // 如果匹配成功, 则字符读取序列的下标+1，并转移至下一个状态 if (match) { incrSeq(); flowtoNextState(ch, nextState); } else { // 不匹配则生成token，并转移至初始状态，开始重新匹配 produceToken(); flowtoResetState(); }}复制代码

(4) 优点