Skip to content

Latest commit

 

History

History
217 lines (152 loc) · 9.45 KB

explain-1.x.md

File metadata and controls

217 lines (152 loc) · 9.45 KB

源码讲解

注意: 本源码讲解文档适用于1.x版本系列

本文会对项目的源码进行详细讲解，欢迎讨论

目录

一、项目结构

  • /doc 存放项目文档、图片等资源
  • /lang 存放不同语言的配置定义，如c-define.js
  • /index.html 词法分析器的在线效果演示
  • /lexer.js 词法分析器的核心文件

二、语言扩展

实现语言扩展的方式很简单，创建一个/lang/{lang}-define.js文件，然后按照如下步骤操作

1、定义常量

  • [必须] 定义枚举型常量，如符号、状态值等
  • [必须] 定义字符集合型常量，包括单字符、双字符、双字符首位符、双字符次位符，关键字，其中单字符又分为运算符、符号 、空白符
  • [必须] 定义DFA的STATE常量
const ENUM_CONST = [];
const CHARSET_CONST = [];
const DFA_STATE_CONST = [];

2、定义函数工具包

以C语言版本为例，主要定义了如下函数

  • judgeTokenTypeByValue(value) 通过Value值判断Token的类型，如关键字类型的Token可以直接通过Value值判断
  • judgeTokenType(state, value) 判断Token的类型，包括根据Value判断和根据State判断两种
  • getFirstCharState(ch) 如果是双字符首位符则返回对应的state，否则返回S_RESET重置状态
  • getSecondCharState(ch) 如果是双字符次位符则返回对应的state，否则返回S_RESET重置状态

如何实现和PHP一样关键字不区分大小写的效果呢？很简单，在judgeTokenTypeByValue(value)函数中将Value转小写进行比较即可，可以参考/lang/sql-define.js中的实现

3、定义自动化测试

只需要实现一个returnCaseList()函数返回所有测试Case即可，每一个测试Case必须定义input和output两种属性

  • input 表示输入的待处理字符序列
  • output 表示预期的输出结果，根据不同严格程度的测试，选择使用数字（预期的token数量）或数组（预期的token列表）中的任一种类型
let autoTest = {
    returnCaseList() {
        return [
            // 严格: 生成的每一个token的类型、值必须完全一致，才说明测试通过
            {
                'input': "int",
                'output': [{"type": "Keyword", "value": "int"}],
            },

            // 宽松: 只要最后生成的token数量是1个，就说明测试通过
            {
                'input': "int",
                'output': 1,
            },
        ];
    },
};

4、定义状态流转模型（FlowModel）

这一节是整个语言扩展环节中最核心的部分，其思想是用户定义自己的状态流转模型

  • result属性，用于定义结果部分，主要包括paths状态流转记录
  • resultChange属性，用于定义修改结果时需要调用的函数，主要包括pathGrow()状态流转记录函数，和toDefault()结果重置
  • getNextState函数，通过输入的字符和当前的状态，来判断下一次要流转的状态
let flowModel = {
    result: {
        paths: [],
    },
    resultChange: {
        pathGrow(path) {
            flowModel.result.paths.push(path)
        },
        toDefault() {
            flowModel.result.paths = [];
        }
    },

    getNextState(ch, state, matchs) {

        // ... 逻辑处理

        return nextState;
    }
}

三、词法分析器核心

1、模块构成

lexer.js文件中定义的lexer变量即是词法分析器核心，它主要有以下两部分构成

  • ISR（Input Stream Reader）输入流读取器
  • DFA（Deterministic finite automaton）有限状态自动机

其它的如resetDefault()和start()等方法都是lexer对外提供的交互接口，不属于词法分析器的核心模块，不在讨论范畴

2、各司其职

词法分析器首先需要读取输入的字符串，然后才能做相应处理，所以ISR负责整个输入流读取的控制，DFA负责判断应当对当前输入的字符序列做什么相应操作

  • ISR ：负责对输入字符序列的控制，如开始读取、读取下一个字符、停止读取等
  • DFA ：负责对状态流转的控制，如流向下一个状态、流向自身状态、回到重置状态

3、ISR介绍

ISR的核心是read()函数，不仅控制字符的读取，内部还有两个最重要的机制，即match与end

  • match如果是true，表示DFA判断可以流转到下一个状态，即当前字符匹配成功，需要把字符下标+1，读取下一个字符。
  • match如果是false，表示DFA判断无法流转到下一个状态，需要通知DFA生成token，并回到重置状态
  • end如果是traue，表示当前是否是最后一个字符，不再读取字符，直接通知DFA生成token

4、DFA介绍

ISR读取字符后，会传给DFA，DFA会根据当前的state状态，把下一次应该流向的state状态返回给ISR

5、时间复杂度

lexer的时间复杂度，即是ISR与DFA的时间复杂度之和

  • DFA只根据当前状态判断下一个状态且无循环、无递归，时间复杂度是O(1)
  • ISR需要依次读入字符直到读取结束，时间复杂度为O(N)

所以lexer时间复杂度为O(N)，即耗时会随着字符串输入的增加而线性增长

四、开发实践

1、快速开始

如需要新增一个Y语言的扩展，复制c-define.js文件并命名为y-define.js，再修改CHARSET_CONST.KEYWORD中定义的关键字即可。

如果没有调整语言细节的需求，截止到当前步骤Y语言的扩展已经完成啦~

由于编程语言的思想都是通用的，所以无论什么语言，都基本离不开Operator、DoubleOperator、Symbol、Whitespace、Keyword、Identifier、Number、Float、String这几种Token，而这些Token都已经定义过了，所以需要额外添加和修改的代价还是较低的

2、语法细节调整

不同语言的语法细节是不同的，比如PHP语言中支持===或!===三个符号的运算符，PHP只有String类型，没有Char类型等等，这些都是与C语言不同的

如果有调整语言细节的需求，建议参考根据《第二节》中的讲解，去修改源码。

3、单元测试

单元测试需要依赖Node环境，所以需要判断当前环境是否是Node环境

对扩展代码部分的单元测试，示例如下，在每次Git提交时（任何分支）会自动执行，不需要人为干预

// 如果是Node环境, 则执行如下单元测试
if (tool.isNodeEnvironment()) {
    let assert = require('assert');
    assert.equal(tool.isUndefined(flowModel.FakeValue), true, "tool.isUndefined单测失败");
}

最后在.travis.yml文件中加入单元测试的script指令即可

script:
  - node ./lang/x-define.js

4、自动化测试

填充autoTest.returnCaseList()函数后，打开index.html文件即会自动进行自动化测试工作（在控制台输出），如果测试失败会自动化测试失败的alert弹框提示。

自动化测试

五、开发规范

1、Git和GitHub相关

(1) Commit

  • test: 测试相关的英文描述
  • perf: 优化相关的英文描述
  • feat: 新功能相关的英文描述
  • fix: bug修复相关的英文描述
  • doc: 文档更新相关的英文描述
  • style: 代码格式调整相关的英文描述
  • refactor: 设计架构重构相关的英文描述

如lexer的架构如果进行调整，commit信息应该为refactor: refactor lexer