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

目标: 解析如下语法
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' } ]

2. 测试运算符

 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解析