目录
一. 编译的基本流程
二. Lexical Analysis(词法分析阶段)
- 2.1 Lexical Specification(分词原则)
- 2.2 Finite Automata (典型分词算法 - 有穷自动机)
三. 手动实现分词器
3.1 基本定义
3.2 构建 DFA
3.3 开始分词
3.4 查看分词结果
四. 小结
示例代码托管在: http://www.github.com/dashnowords/blogs
博客园地址:《大史住在大前端》原创博文目录
华为云社区地址:[你要的前端打怪升级指南]
B 站地址:[编译原理] https://www.bilibili.com/video/av27845355
Stanford 公开课:[Stanford 大学公开课官网] https://lagunita.stanford.edu/
课程里涉及到的内容讲的还是很清楚的, 但个别地方有点脱节, 任何看不懂卡住的地方, 请自行查阅经典著作《Compilers--priciples, Techniques and Tools》(也就是大名鼎鼎的龙书)的对应章节.
一. 编译的基本流程
完整的编译的 5 个基本步骤包括 lexcical anlysis,parse,sematic,optimize,code generate. 课程中并没有使用复杂的编程语言, 而是一种用于课堂教学的自发明语言 COOL, 很明显老师为它写好了编译器程序.
二. Lexical Analysis(词法分析阶段)
任务: 将字符串分解成为 [Type, (Value)] 元组的形式的词法单元.
"龙书" 里的示例更为直观, 例如表达式语句 E = M * C ** 2 进行词法分析后会得到如下的类似结果:
[id, 指向符号表中 E 的条目的指针]
[assign_op]
[id, 指向符号表中 M 的条目的指针]
[mult_op]
[id, 指向符号表中 C 的条目的指针]
[exp_op]
[number, 整数值 2]
词法分析基本需要经历如下几个阶段:
- Lexical Specification-->Regular expressions-->NFA-->DFA-->Table-driven Implementation of DFA
- 2.1 Lexical Specification(分词原则)
COOL 中的基本 Type 包括如下几个类别:
Indentifier 标识符 - 指以字母开头后续为若干个字母或数字的字符组
Integer - 指一组非空的数字字符
Keyword- 指语言中的关键词, 例如 if,else 等
Whitespace- 指一组非空的空格字符或换行符或制表符
很多程序设计语言中的分词原则基本都会覆盖关键字, 运算符, 标识符, 常量, 标点符号, 他们也会在后面的实现中被作为终止符集合, 课程板书中也提供了 COOL 分词原则的类正则形式.
分词时类型的正则匹配默认为贪婪模式, 即匹配更多的字符. 词法单元也具备一定的优先级次序(通常也是代码逻辑的实现顺序), 例如 if 从正则上来判断既符合 Keywords 也符合 Identifier, 此时该单元的类型就应该标记为 Keywords. 这个阶段就完成了从 Lecical Specification-->Regular expressions 的部分.
2.2 Finite Automata (典型分词算法 - 有穷自动机)
FA 是一个可以自动识别词法单元的机器, 它是一个状态转换图,"有限" 是指它包含的状态是有限的, 一个状态读入一个字符后, 后继的状态可能为:
后继状态为自身
后继状态只有一个
后继状态有多个
如果每次转换后的后继状态都是唯一的, 则称为 DFA(确定有限自动机), 如果后继状态可能有多个则称为 NFA(不确定有限状态机). 由于 DFA 的状态转移路径是唯一的, 所以作为状态查询图时, 无论成功或者失败只需要运行一次, 但 NFA 就可能需要运行多次.
正则表达式是可以转换为 NFA 形式的, 或许你已经在一些可视化正则表达式的网站上 [ https://regexper.com/ ] 见过类似的形式. 下图比较清晰地展示了从正则表达式到 NFA 状态图的转换规则(Regular expressions-->NFA):
如果一个 DFA 和一个 NFA 能够识别的字符集是一致的, 则称它们为等价的, 对于任意 NFA, 一定存在一个 DFA 与其等价, 由 NFA 构建 DFA 的过程被称为 DFA 的确定化, 也就是 NFA-->DFA 的过程. 这个过程是围绕ε -closure 状态集合的概念展开的, 大致的过程就是从起点开始, 每次将当前状态和通过若干次ε转换 (它是一个特殊的状态转移函数, 表示转换后的状态还是当前状态) 作为一个新的ε -closure 状态集合 , 使用矩阵记录每个ε -closure 集合转换前后的集合, 最后对整个状态转移矩阵进行标记重命名, 就可以得到一个 DFA, 事实上转化后的 DFA 中的每一个状态, 就是 NFA 中的一个ε -closure 集合, 你可以将它理解成一个通过分组来简化表达方式的过程, 相关的过程可以参考下面这个文章西北农林科技大学编译原理课程 PPT[词法分析] , 里面图比较多, 能够辅助理解, 本文不再赘述.
三. 手动实现分词器
至此 1-4 课就结束了, 估计看视频课程的人也是一脸懵逼, 因为课程并没有讲解如何利用 DFA 得到最终期望的形式 --Token 元组, 那么最后我们就自己手动来实现一下.
3.1 基本定义
假设我们需要对下面这段代码进行分词解析:
- let snippet = `
- var b3 = 2;
- a = 1 + ( b3 + 4);
- return a;
- `;
那么先来进行一些基本类型集合定义:
- // 解析结束标记
- const EOF = undefined;
- //Token Type 可识别的 Token 类型,
- const TT = {
- num: 'num',
- id: 'id',
- keywords: 'keywords', //var | return
- lparen: 'lparen',// (
- rparen: 'rparen',// )
- semicolon: 'semicolon', //;
- whitespace: 'whitespace', // \n | \t | \s (空格, 制表符, 换行符)
- plus: 'plus', // +
- assign: 'assign',// =
- }
- // 状态集类型, 除开始和结束外, 其他可以与 Token 支持的类型相对应, 每次分词从 start 状态开始, 接收一个字符后改变状态, 直到在 done 状态结束时, 可以得到一个 token
- const S = {
- start: 'start',
- done: 'done',
- ...TT
- }
进行工具函数定义:
- // 判断是否为关键词(为简化流程, 仅检测上面示例中包含的关键词)
- const isKeywords = (token) => ['function', 'return', 'if', 'var'].includes(token);
- // 判断是否为数字
- const isDigit = c => /\d/.test(c);
- // 判断是否为合法的标识符字符
- const isValidId = c => /[A-Za-z0-9]/.test(c);
- // 判断是否为空格
- const isBlank = c => /(\s|\t|\n)/.test(c);
3.2 构建 DFA
以上面定义的状态集合和 token 类别为依据构建 DFA:
3.3 开始分词
分词的逻辑实际上就是, 每次先将状态置为 start, 然后读入一个字符, 根据该字符判断下一个状态, 只要没有到达完成状态 done 就继续读入字符, 每次到达 done 状态时, 就可以得到一个 token, 将其记录下来, 然后重新将状态置为 start, 开始寻找下一个 token 直到分析完整个代码段. 也就是说 DFA 状态机每运行一轮, 就得到一个 token. 参考代码如下:
- /**
- * 词法分析
- */
- function tokenize(code) {
- let state = S.start;
- let currentToken;// 标记当前寻找到的 token
- let index = 0;// 起始指针, 每次分析指向 start 状态
- let lookup = 0;// 前探指针, 每次分析最终指向 done 状态, start->done 之间的字符即为 token
- while (code[lookup] !== EOF) { // 如果还有字符
- while (state !== S.done) { // 开始拆分 token
- // 获取下一个字符
- let c = code[lookup++];
- // 根据当前状态和下一个字符判断 DFA 如何跳转
- switch (state) {
- case S.start: // 开始为空集, 实现 DFA 中各个状态转移分支
- if (isDigit(c)) {
- state = S.num;
- } else if (isValidId(c)) {
- state = S.id;
- } else if (isBlank(c)) {
- state = S.done;
- } else if (c === '=') {
- currentToken = [TT.assign, '=']
- state = S.done;
- } else if (c === '+') {
- currentToken = [TT.plus, '+']
- state = S.done;
- } else if (c === ';') {
- currentToken = [TT.semicolon, ';']
- state = S.done;
- };
- break;
- case S.num: // 如果是整数
- if (isDigit(c)) {
- state = S.num;
- } else {
- currentToken = [TT.num, code.slice(index,lookup - 1)];
- lookup -= 1; // 从数字状态跳出后, 最后一位需要参与下一轮分词, 故回退一位
- state = S.done;
- }
- break;
- case S.id: // 如果是标识符状态
- if (isValidId(c)) {
- state = S.id;
- } else {
- let tempToken = code.slice(index,lookup - 1);
- lookup -= 1; // 从标识符状态跳出后, 最后一位需要参与下一轮分词, 故回退一位
- if (isKeywords(tempToken)) {
- currentToken = [TT.keywords, tempToken];
- }else{
- currentToken = [TT.id, tempToken];
- }
- state = S.done;
- }
- break;
- }
- }
- //state = S.done 时跳出
- currentToken && console.log(currentToken);
- currentToken = undefined;
- // 起指针跟上末指针
- index = lookup;
- // 开始下一轮分词
- state = S.start;
- }
- }
3.4 查看分词结果
运行上述代码即可看到目标程序片段的分词结果:
四. 小结
至此, 我们就得到了元组形式的分词结果, 完成了编译中第一步 lexical analysis 的部分, 笔者同时提供了一份包含 token 所在行列信息的版本, 你可以从附件或[我的 GitHub 仓库] 中拿到示例代码, 如果觉得对你有帮助, 可以在 GitHub 上为我加个星星哦~
来源: https://www.cnblogs.com/dashnowords/p/11552517.html