编译原理

发表于 | 分类于

一个简单的四则运算的解释器

编译过程

  1. 词法分析
  2. 语法分析
  3. 语义分析
  4. 生成中间代码
  5. 优化
  6. 生成目标代码

其中，1~3只跟语言的语法有关，跟机器目标无关，所以又被称为前端，指对程序代码的分析和理解的过程。

词法分析

如同读文章一样，文章是由一个个中文单词组成的。在程序中也一样，只不过这里不叫单词，叫“语法记号”（Token）。

1
2
3
4
5
6
7
8
9
10
11
function main( age = 30) {
      const age = 30
      const target = 5 + 5 * 5
      let ret = ''
      if(age >= target) {
        ret = 'hello old man'
      } else {
        ret = 'hello young man'
      }
      return ret
    }

上述代码，我们会先识别出const，let,if else 等关键字，age、target等标识符(变量)，+，=，>=等操作符，这些都是token。

词法分析大多数情况下是使用状态机来实现的释义详见浏览器工作原理

分析规则

  • 识别 age 这样的标识符。以字母开头后面跟数字/字符/下划线，遇到第一个不是数字/下划线/字符时结束；
  • 识别 >= 这样的操作符。 当识别到 > 字符时，会判断下一个字符是空格/ = / > 用于区分是要进入 GT (Greater Than)/ 大于等于 (Greater Equal)/ 位运算
  • 识别30这样的数字字面量。 当遇到非数字字符时，结束当前字面量匹配。

语法分析

语法分析就是根据语法结构，构建出一棵抽象语法树。

如 “我喜欢聪明又勇敢的你”。句子中包含主谓宾三个部分。根据语法结构层层拆分出一个上下级节点有关联的语法树。

构造语法树

首先构造根节点，代表整个程序，然后向下扫描Token构建子节点且绑定父节点。可以使用stack实现（递归下降算法）。

语义分析

语义分析就是让计算机理解我们真实地意图。

如“我喜欢聪明又勇敢的你”。你是谁？需要结合文本上下文才能确定具体指代的谁。

规则

  • 计算表达式的数据类型是否统一，是否需要做转换。
  • 代码块内部和外部有相同名称的变量，要用哪个？
  • 在统一作用域中，检查变量唯一性，不允许有两个同名的变量。

回归标题，5 + 5 * 5，词法定义如下：

  • Token
    • Number 0~9的组合
    • 操作符 +、-、*、/之一
    • whitespace
    • LineTerminator

产生式

在计算机中指Tiger编译器将源程序经过词法分析（Lexical Analysis）和语法分析（Syntax Analysis）后得到的一系列符合文法规则（Backus-Naur Form，BNF）的语句

  • 用尖括号（<, >）括起来的名称来表示语法结构名
  • 语法结构分成基础结构和需要用其他语法结构定义的复合结构
    • 基础结构称终结符
    • 复合结构称非终结符
  • 引号和中间的字符表示终结符
  • 可以有括号
  • *表示重复多次
  • | 表示 “或”
    • 表示至少一次

由于加减乘除有优先级，所以可以理解为加法是由若干个乘法表达式再由加号或者减号链接起来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// BNF产生式

<Expression> ::= 
    <AdditiveExpression><EOF>

<AdditiveExpression> ::= 
    <MultiplicativeExpression>
    |<AdditiveExpression><+><MultiplicativeExpression>
    |<AdditiveExpression><-><MultiplicativeExpression>

<MultiplicativeExpression> ::= 
    <Number>
    |<MultiplicativeExpression><*><Number>
    |<MultiplicativeExpression></><Number>

四则运算表达式运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
function Expression(source){
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF" ) {
        let node = {
            type:"Expression",
            children:[source.shift(), source.shift()]
        }
        source.unshift(node);
        return node;
    }
    AdditiveExpression(source);
    return Expression(source);
}
function AdditiveExpression(source){
    if(source[0].type === "MultiplicativeExpression") {
        let node = {
            type:"AdditiveExpression",
            children:[source[0]]
        }
        source[0] = node;
        return AdditiveExpression(source);
    } 
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
        let node = {
            type:"AdditiveExpression",
            operator:"+",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
    }
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
        let node = {
            type:"AdditiveExpression",
            operator:"-",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
    }
    if(source[0].type === "AdditiveExpression")
        return source[0];
    MultiplicativeExpression(source);
    return AdditiveExpression(source);
}
function MultiplicativeExpression(source){
    if(source[0].type === "Number") {
        let node = {
            type:"MultiplicativeExpression",
            children:[source[0]]
        }
        source[0] = node;
        return MultiplicativeExpression(source);
    } 
    if(source[0].type === "MultiplicativeExpression" && source[1] && source[1].type === "*") {
        let node = {
            type:"MultiplicativeExpression",
            operator:"*",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);
        return MultiplicativeExpression(source);
    }
    if(source[0].type === "MultiplicativeExpression"&& source[1] && source[1].type === "/") {
        let node = {
            type:"MultiplicativeExpression",
            operator:"/",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);
        return MultiplicativeExpression(source);
    }
    if(source[0].type === "MultiplicativeExpression")
        return source[0];

    return MultiplicativeExpression(source);
};

var source = [{
    type:"Number",
    value: "5"
}, 
{
    type:"+",
    value: "+"
}, {
    type:"Number",
    value: "5"
}, 
{
    type:"*",
    value: "*"
},{
    type:"Number",
    value: "5"
}, {
    type:"EOF"
}];
var ast = Expression(source);

console.log(ast);



function evaluate(node) {
    if(node.type === "Expression") {
        return evaluate(node.children[0])
    }
    if(node.type === "AdditiveExpression") {
        if(node.operator === '-') {
            return evaluate(node.children[0]) - evaluate(node.children[2]);
        }
        if(node.operator === '+') {
            return evaluate(node.children[0]) + evaluate(node.children[2]);
        }
        return evaluate(node.children[0])
    }
    if(node.type === "MultiplicativeExpression") {
        if(node.operator === '*') {
            return evaluate(node.children[0]) * evaluate(node.children[2]);
        }
        if(node.operator === '/') {
            return evaluate(node.children[0]) / evaluate(node.children[2]);
        }
        return evaluate(node.children[0])
    }
    if(node.type === "Number") {
        return Number(node.value);
    }
}

const aaa = evaluate(ast)
console.log(aaa)