Solo  当前访客:0 开始使用

词法分析 - 一步步实现JS语言编译执行


实现编译器的第一步即实现词法解析

目标: 解析如下语法
var a = 1
3 * 4
1+2 * 3
1+1+1

词法解析

语言是由一个个Token组成的语句,js里的token包括如下

IdentifierName // 标识符
Punctuator // 标点
Literal // 字面量
Reserved Words // 保留字

词法解析即将一个个token分解开

如:

var a = 1;
a = a+b;

解析出token如下: var, a,=,1,a,=,a,+,b
其中:var 为保留字, a为标识符,+为标点,1为字面量

如何实现

如何分解一个个token呢, 我们常用的字符串分解,如按特定字符分割,但是在代码分解token上不太实用。 常用的方法是有限自动机

我们先使用确定的有限自动机(DFA)实现几个简单语句的分析

DFA: 逐个字符输入,每次输入都有一个确定的转换状态,

在使用DFA解析之前,我们需要指定各规则:

  1. 标识符组成:以字母开始,可包含字母和数字
  2. *、+为标点符号
  3. 数字字面量,只包含0-9
  4. var 未保留字

使用DFA解析如下

注:

  • 状态1:为初始状态, 一旦匹配到终止状态,需要再回到状态1
  • 状态2: 输入v时转到状态2,表示保留字var的第一个状态
  • 状态3:输入a时转到状态3, 表示保留字var的第二个状态
  • 状态4: 输入r时转到状态4, 表示保留字var匹配完毕
  • 状态5: 图上表面输入路径有1,2,3,4, 表示标识符状态
  • 状态6: 输入数字时进入, 表示数字字面量状态

按上图简化的DNF可以简单实现如下

1. 定义一个状态列表

this.DfaState = {
            Initial: "Initial",
            Var:"Var", Id_var1:"Id_var1", Id_var2:"Id_var2", Id_var3:"Id_var3",
            Identifier:"Identifier", GT:"GT", GE:"GE",
            Assignment:"Assignment",
            Plus:"Plus", Minus:"Minus", Star:"Star", Slash:"Slash",
            SemiColon:"SemiColon",
            Num:"Num"
        }

2. 编写DFA主体代码

dfaParse() {
        let code = this.code // 源代码
        let codeLen = code.length;
        let chIndex = 0;
        let ch = '' // 表示当前字符
        let state = this.DfaState.Initial // 初始化状态
        while(chIndex < codeLen) {
            ch = code.charAt(chIndex);
            switch(state) {
		// 状态判断及转换	
	   }
           chIndex++
	}
}

3. 状态转换过程

按本节的目标, 我们只需要识别出标识符var数字字面量赋值符号 =+、-、*、/标点
由于标识符规则包含了var, 所以我们需要优先匹配var状态

switch(state) {
                case this.DfaState.Initial:
                    // 对于初始状态, 我们需要直接按字符进入指定状态
                    state = this.toInitial(ch)
                    break;
                case this.DfaState.Id_var1:
                    // 如上图所示,如果为a,则进入var2,非a则进入标识符状态
                    if(ch === 'a') {
                        state = this.switchState(this.DfaState.Id_var2, ch)
                    } else if(Utils.isAlpha(ch) || Utils.isNum(ch)){
                        state = this.switchState(this.DfaState.Identifier, ch)
                    } else {
                        state = this.toInitial(ch)
                    }
                    break;
                case this.DfaState.Id_var2:
                    if(ch === 'r') {
                        state = this.switchState(this.DfaState.Var, ch)
                    } else if(Utils.isAlpha(ch) || Utils.isNum(ch)){
                        state = this.switchState(this.DfaState.Identifier,ch)
                    } else {
                        state = this.toInitial(ch)
                    }
                    break;
                case this.DfaState.Var:
                    if(Utils.isAlpha(ch) || Utils.isNum(ch)){
                        state = this.switchState(this.DfaState.Identifier, ch)
                    } else {
                        state = this.toInitial(ch)
                    }
                    break;
                case this.DfaState.Identifier:
                    if(Utils.isAlpha(ch) || Utils.isNum(ch)){
                        state = this.switchState(this.DfaState.Identifier, ch)
                    } else {
                        state = this.toInitial(ch)
                    }
                    break;
                case this.DfaState.Num:
                    if(!Utils.isNum(ch)) {
                        state = this.toInitial(ch)
                    }
                    break;
                // 单字符直接判断
                case this.DfaState.GT:
                case this.DfaState.Assignment:
                case this.DfaState.Plus:
                case this.DfaState.Minus:
                case this.DfaState.Star:
                case this.DfaState.Slash:
                case this.DfaState.SemiColon:
                    state = this.toInitial(ch)
                    break;
                default:

            }

其中toInitial,用于初始化处理, 主要是判断初始状态及创建token

Token定义如下

// token 含义type 和value 属性
function Token (type, value) {
    this.type = type;
    this.value = value || '';
}

toInitial

toInitial(ch) {

        if(this.token && this.token.value.length > 0) {
            this.tokens.push(this.token)
        }
        this.token = new Token();

        let state = this.DfaState.Initial // 初始化状态

        if(Utils.isAlpha(ch)) {
            if(ch === 'v') {
                state = this.DfaState.Id_var1
            } else {
                state = this.DfaState.Identifier
            }
            this.token.type = this.DfaState.Identifier
            this.token.value = this.token.value + ch;
        } else if(Utils.isNum(ch)) {
            state = this.DfaState.Num
            this.token.type = this.DfaState.Num
            this.token.value = this.token.value + ch;
        } else if (ch == ';') {
            state = this.DfaState.SemiColon;
            this.token.type = this.DfaState.SemiColon;
            this.token.value = this.token.value + ch;
        } else if (ch == '>') {
            state = this.DfaState.GT;
            this.token.type = this.DfaState.GT;
            this.token.value = this.token.value + ch;
        } else if (ch == '=') {
            state = this.DfaState.Assignment;
            this.token.type = this.DfaState.Assignment;
            this.token.value = this.token.value + ch;
        } else if (ch == '+') {
            state = this.DfaState.Plus;
            this.token.type = this.DfaState.Plus;
            this.token.value = this.token.value + ch;
        } else if (ch == '-') {
            state = this.DfaState.Minus;
            this.token.type = this.DfaState.Minus;
            this.token.value = this.token.value + ch;
        } else if (ch == '*') {
            state = this.DfaState.Star;
            this.token.type = this.DfaState.Star;
            this.token.value = this.token.value + ch;
        } else if (ch == '/') {
            state = this.DfaState.Slash;
            this.token.type = this.DfaState.Slash;
            this.token.value = this.token.value + ch;
        }

        return state;
    }
 // switchState 用于状态切换
    switchState(newState, val) {
        this.token.type = newState
        this.token.value = this.token.value + val;
        return newState
    }

测试

  1. 测试var定义
let lexer = new LexerLevel1("var a = 1");

    lexer.dfaParse();
    console.log(lexer.tokens)

结果:

[ Token { type: 'Var', value: 'var' },
  Token { type: 'Identifier', value: 'a' },
  Token { type: 'Assignment', value: '=' },
  Token { type: 'Num', value: '1' } ]
  1. 测试运算符
 let lexer3 = new LexerLevel1("2 + 4 * 3");

    lexer3.dfaParse();
    console.log(lexer3.tokens)

结果:

[ Token { type: 'Num', value: '2' },
  Token { type: 'Plus', value: '+' },
  Token { type: 'Num', value: '4' },
  Token { type: 'Star', value: '*' },
  Token { type: 'Num', value: '3' } ]

第一步词法解析到此就完成了简单的demo, 扩展该DFA,我们可以解析出所有的token。 接下来我们将会完善该token解析


标题:词法分析 - 一步步实现JS语言编译执行
作者:hugh0524
地址:https://blog.uproject.cn/articles/2020/02/19/1582105269312.html

, , , 0 0