一个很经典的例子,20k+的star,很早之前看到过。今日有空,给理解翻译了一遍。

说是代码,不如说这是一篇循序渐进的文章,简明扼要的说明了编译过程中的几大步骤分别是在做什么。

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
'use strict';
/**
* 今天我们要一起编写一个编译器。但不是普通的编译器。一个超级棒的小编译器!一个非常小的编译器,如果您删除所有注释,该文件将只有大约200行实际代码。
*
* 我们将把一些类似LISP的函数调用编译成一些类似C的函数调用。
*
* 如果你对其中一个不熟悉的话。我就给你简单介绍一下。
*
* 如果我们有两个函数`add`和`subtract`,它们会写成这样:
*
* LISP C
*
* 2 + 2 (add 2 2) add(2, 2)
* 4 - 2 (subtract 4 2) subtract(4, 2)
* 2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
*
* 很简单,对吧?
*
* 很好,因为这正是我们要编译的。虽然这不是一个完整的LISP或C语法,但它的语法足以演示现代编译器的许多主要部分。
*/


/**
* 大多数编译器分为三个主要阶段:解析(Parsing)、转换(Transformation)和代码生成(Code Generation)
*
* 1. *解析* 是将原始代码转换为更抽象的代码表示形式
*
* 2. *转换* 接受这种抽象表示,并操纵它来做编译器希望它做的任何事情
*
* 3. *代码生成* 获取代码的转换表示形式,并将其转换为新代码
*/


/**
* 解析(Parsing)阶段
* -------
*
* 解析通常分为两个阶段:词法分析和语法分析
*
* 1. *词法分析(Lexical Analysis)*获取原始代码,并通过一种称为记号赋值器(或词法分析器)的东西将其拆分成这些称为记号的东西。
*
* 标记(Token)是一组微小的小对象,它们描述了一段孤立的语法。它们可以是数字、标签、标点符号、运算符等等。
*
* 2. *语法分析(Syntactic Analysis)*获取标记并将其重新格式化为描述语法的每个部分及其相互关系的表示。这称为中间表示或抽象语法树。
*
* 抽象语法树,简称AST,是一个嵌套很深的对象,它以一种既易于使用又能告诉我们大量信息的方式来表示代码。
*
* 例如下面的语法:
*
* (add 2 (subtract 4 2))
*
* 词法解析所得到的Token会是像下面这样:
*
* [
* { type: 'paren', value: '(' },
* { type: 'name', value: 'add' },
* { type: 'number', value: '2' },
* { type: 'paren', value: '(' },
* { type: 'name', value: 'subtract' },
* { type: 'number', value: '4' },
* { type: 'number', value: '2' },
* { type: 'paren', value: ')' },
* { type: 'paren', value: ')' },
* ]
*
* 而抽象语法树(AST)长这样:
*
* {
* type: 'Program',
* body: [{
* type: 'CallExpression',
* name: 'add',
* params: [{
* type: 'NumberLiteral',
* value: '2',
* }, {
* type: 'CallExpression',
* name: 'subtract',
* params: [{
* type: 'NumberLiteral',
* value: '4',
* }, {
* type: 'NumberLiteral',
* value: '2',
* }]
* }]
* }]
* }
*/


/**
* 转换阶段(Transformation)
* --------------
*
* 编译器的下一个阶段是转换。同样,这只是取自上一步的AST并对其进行更改。它可以在同一种语言中操作AST,也可以将其翻译成一种全新的语言。
*
* 让我们看看如何转换AST。
*
* 您可能注意到,AST中包含一些看起来非常相似的元素。他们都有一个type属性。
* 这些节点中的每一个都称为AST节点。这些节点上定义了一些属性,用来描述抽象语法树上一个独立的部分。
*
* 例如一个 "数字字面量(NumberLiteral)"节点:
*
* {
* type: 'NumberLiteral',
* value: '2',
* }
*
* 或者一个"调用表达式(CallExpression)"节点:
*
* {
* type: 'CallExpression',
* name: 'subtract',
* params: [...nested nodes go here...],
* }
*
* 当转换AST时,我们可以通过添加/删除/替换属性来操作节点,我们可以添加新节点、删除节点,或者我们可以不考虑现有的AST而基于它创建一个全新的AST。
*
* 由于我们的目标是一种新语言,因此我们将专注于创建一种特定于目标语言的全新AST。
*
* 遍历
* ---------
*
* 为了浏览所有这些节点,我们需要能够遍历它们。此遍历过程以深度优先的方式到达AST中的每个节点。
*
* {
* type: 'Program',
* body: [{
* type: 'CallExpression',
* name: 'add',
* params: [{
* type: 'NumberLiteral',
* value: '2'
* }, {
* type: 'CallExpression',
* name: 'subtract',
* params: [{
* type: 'NumberLiteral',
* value: '4'
* }, {
* type: 'NumberLiteral',
* value: '2'
* }]
* }]
* }]
* }
*
* 因此,对于上面的AST,我们会这样做:
*
* 1. Program - 从AST的顶层开始
* 2. CallExpression (add) - Program body的第一个元素
* 3. NumberLiteral (2) - CallExpression(add) params的第一个元素
* 4. CallExpression (subtract) - CallExpression(add) params的第二个元素
* 5. NumberLiteral (4) - CallExpression(subtract)的第一个参数
* 6. NumberLiteral (2) - CallExpression(subtract)的第二个参数
*
* 如果我们直接操作这个AST,而不是创建单独的AST,我们很可能会在这里引入各种抽象。但是,仅访问树中的每个节点就足以完成我们要做的事情。
*
* 我之所以使用“访问”这个词,是因为存在这样一种模式,即如何表示对对象结构元素的操作。
*
* 访问
* --------
*
* 这里的基本思想是,我们将创建一个“访问者”对象,该对象具有接受不同节点类型的方法。
*
* var visitor = {
* NumberLiteral() {},
* CallExpression() {},
* };
*
* 当我们遍历AST时,每当我们“输入”匹配类型的节点时,都会调用此访问器上的方法。
*
* 为了使访问器工作,调用时会将节点和一个父节点的引用传递给它。
*
* var visitor = {
* NumberLiteral(node, parent) {},
* CallExpression(node, parent) {},
* };
*
* 然而,也存在所谓“退出”的可能性。想象一下前面的的树结构以列表形式展现:
*
* - Program
* - CallExpression
* - NumberLiteral
* - CallExpression
* - NumberLiteral
* - NumberLiteral
*
* 当我们往下走的时候,我们会到达死胡同的分支。当我们完成树的每个分支时,我们“退出”它。所以沿着树往下走,我们“进入”每个节点,再往上走,我们“退出”。
*
* -> Program (enter)
* -> CallExpression (enter)
* -> Number Literal (enter)
* <- Number Literal (exit)
* -> Call Expression (enter)
* -> Number Literal (enter)
* <- Number Literal (exit)
* -> Number Literal (enter)
* <- Number Literal (exit)
* <- CallExpression (exit)
* <- CallExpression (exit)
* <- Program (exit)
*
* 为了支持进入和退出,最终的访问器应该长这样::
*
* var visitor = {
* NumberLiteral: {
* enter(node, parent) {},
* exit(node, parent) {},
* }
* };
*/


/**
* 代码转换(Code Generation)
* ---------------
*
* 编译器的最后一个阶段是代码生成。有时,编译器会做与转换重叠的事情,但在大多数情况下,代码生成只是将AST和字符串化为代码。
*
* 代码转换有几种不同的工作方式,一些编译器将复用前面的Token,另一些编译器将创建单独的代码表示形式,以便它们可以线性打印节点。
* 但判断的是,大多数编译器将使用我们刚刚创建的AST,这就是下面将要关注的。
*
* 实际上,我们的代码生成器将知道如何“打印”AST的所有不同节点类型,并且它将递归调用自身来打印嵌套节点,直到所有内容都打印成一个很长的代码字符串。
*/


/**
* 上面就是就是编译器的所有不同部分。
*
* 这并不是说每个编译器看起来都与我在这里描述的完全一样。编译器有很多不同的用途,它们可能需要比我详细描述的更多的步骤。
*
* 但是现在你应该对大多数编译器的大致样子有了一个高层面的认识。
*
* 现在我已经解释了所有这些,你们都可以开始编写自己的编译器了,对吗?
*
* 开个玩笑,这就是我下面要写的:P
*
* 那么开始吧...
*/


/**
* ============================================================================
* (/^▽^)/
* 词法分析器(THE TOKENIZER!)
* ============================================================================
*/


/**
* 我们将用 tokenizer 来开始第一个阶段 ”解析“ 的词法分析部分
*
* 我们将写一段代码字符串,并且将它解析成Token数组
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/


// 我们首先接受一串输入的代码,然后我们将设置两个东西...
function tokenizer(input) {

// 一个‘current`变量,用于像光标一样跟踪我们在代码中的位置。
let current = 0;

// 一个`tokens` 数组,用于存放解析出来的token
let tokens = [];

//我们首先创建一个循环,在循环中,可以让current变量增加任意值
//
// 我们这样做是因为我们可能想要在单个循环中多次递增‘current`,因为我们的token可以是任意长度。
while (current < input.length) {

// 我们把current所在的字符存在char变量中
let char = input[current];

// 我们首先要检查的是左括号。这将在稍后用于`CallExpression`,但现在我们只关心字符。
//
// 我们检查是否有左括号:
if (char === '(') {

// 如果是,我们将创建一个类型为`paren`的新标记,将值设置为左圆括号,并push到token数组中
tokens.push({
type: 'paren',
value: '(',
});

// 递增current
current++;

// 然后我们“继续”进入下一个循环周期。
continue;
}

// 接下来,我们将检查右括号。我们执行与前面完全相同的操作:检查右括号、添加新token、递增`current`然后`Contine`。
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}

// 接下来,我们将检查是否有空格。这很有趣,因为我们关心空格是用来分隔字符的,但实际上存储为token对我们来说并不重要,我们会在晚些时候把它扔掉
//
// 所以在这里,我们只是要测试它的存在,如果它确实存在,我们就会“continue”下去。
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}

// 下一种token类型是数字。这与我们以前看到的不同,因为数字可以是任意数量的字符,我们希望将整个字符序列捕获为一个令牌。
//
// (add 123 456)
// ^^^ ^^^
// 应该只被当做两个独立的token
//
// 所以当我们遇到一个序列中的第一个数字时,我们就开始这项工作。
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {

// 我们将创建一个`value`字符串,并将字符写到该字符串。
let value = '';

// 然后,我们将遍历序列中的每个字符,直到遇到一个不是数字的字符,将每个数字字符推入我们的“值”,并在前进过程中递增“current`”。
// (这个是简单demo,实际实现的时候还要考虑变量名数组啥的)
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}

// 完成后,我们将一个 `number` token 放到 `tokens` 数组中.
tokens.push({ type: 'number', value });

// 然后继续.
continue;
}

// 同时也应该支持任何用双引号包起来的字符
//
// (concat "foo" "bar")
// ^^^ ^^^ 字符串 tokens
//
// 我们将从检测引号开始:
if (char === '"') {
//创建一个value变量用于存储字符串
let value = '';

// 从保存第一个双引号开始
char = input[++current];

// 然后继续迭代,知道遇到另一个双引号
// (实际实现时要考虑转义字符啥的)
while (char !== '"') {
value += char;
char = input[++current];
}

// 保存后面的双引号并递增current
char = input[++current];

// 创建一个string token并放到tokens数组中
tokens.push({ type: 'string', value });

continue;
}

// 最后一个类型是 `name` token。 这是一个字母序列,而不是数字序列,是我们的LISP语法中的函数名称。
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';

// 同样,我们不断循环直到所有字符都被放到value中
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}

// 然后将value作为一个 `name` token放到 tokens 数组中。
tokens.push({ type: 'name', value });

continue;
}

// 最后如果遇到了上面没有匹配到的字符,则抛异常并退出程序。
throw new TypeError('I dont know what this character is: ' + char);
}

// 最后,返回tokens数组就好了
return tokens;
}

/**
* ============================================================================
* ヽ/❀o ل͜ o\ノ
* 解析器( THE PARSER!!!)
* ============================================================================
*/


/**
* 在解析器中,我们将获取令牌数组并将其转换为AST。
*
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/


// 好了,我们定义一个 `parser` 函数, 接收 tokens 数组作为参数
function parser(tokens) {

// 同样,我们创建一个 `current` 变量,作为游标
let current = 0;

// 但这一次,我们将使用递归,而不是“While”循环. 所以我们定义一个 `walk` 函数.
function walk() {

// 在walk函数中,我们首先获取current游标所在的token
let token = tokens[current];

// 对于不同的token类型, 将走到下面不同的代码逻辑
// 从 number 类型的token开始
//
// 判断number类型token
if (token.type === 'number') {

// 增加current游标
current++;

// 然后返回一个叫 `NumberLiteral` 的AST节点,并将它的value设置为token的value
return {
type: 'NumberLiteral',
value: token.value,
};
}

// 如果是一个string类型的token,也一样,AST节点类型是 `StringLiteral`
if (token.type === 'string') {
current++;

return {
type: 'StringLiteral',
value: token.value,
};
}

// 然后我们开始寻找调用表达式。当我们遇到左括号时,就开始。
if (
token.type === 'paren' &&
token.value === '('
) {

//我们将递增`current`以跳过括号,因为我们在AST中并不关心它。
token = tokens[++current];

//我们创建了一个类型为`CallExpression`的基节点,我们将Name设置为当前Token的值,因为左括号后面的下一个Token是函数的名称。
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};

// 我们再次*递增`current`以跳过函数名称标记。
token = tokens[++current];

// 现在,我们要遍历作为`CallExpression`的`params`的每个令牌,直到遇到右括号。
//
// 这就是递归的用途,我们用递归来解决这个问题,而不是试图解析潜在的无限嵌套节点集。
//
// 为了解释这一点,让我们以Lisp代码为例。您可以看到,`add`的参数是一个数字和一个嵌套的`CallExpression`,该`CallExpression`包含它自己的数字。
//
// (add 2 (subtract 4 2))
//
// 您还会注意到,在我们的记号数组中,我们有多个右括号。
//
// [
// { type: 'paren', value: '(' },
// { type: 'name', value: 'add' },
// { type: 'number', value: '2' },
// { type: 'paren', value: '(' },
// { type: 'name', value: 'subtract' },
// { type: 'number', value: '4' },
// { type: 'number', value: '2' },
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// ]
//
// 我们将依靠嵌套的`walk`函数来递增我们的`current`变量,使其跳过任何嵌套的`CallExpression`。

// 因此,我们创建了一个循环,该循环将一直持续下去直到它遇到一个`type`为`‘paren’`、`value`为右圆括号的token。
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 在循环中我们将调用`walk`函数,该函数将返回一个`node`并将其推送到我们的`node.params`中。
node.params.push(walk());
token = tokens[current];
}

// 最后,我们将最后一次递增`current`以跳过右括号。
current++;

// 然后返回 node.
return node;
}

// 同样,如果我们到目前为止还没有识别出令牌类型,我们将抛出一个错误。
throw new TypeError(token.type);
}

// 现在,我们将创建AST,它将有一个根节点,‘Program’节点。
let ast = {
type: 'Program',
body: [],
};

// 我们将启动我们的`walk`函数,将节点推入我们的`ast.body`数组。
//
// 我们之所以在循环中这样做,是因为我们的程序可以一个接一个地使用“CallExpression`”,而不是嵌套。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}

// 在解析器结束时,我们将返回AST。
return ast;
}

/**
* ============================================================================
* ⌒(❀>◞౪◟<❀)⌒
* 转换器(THE TRAVERSER!!!)
* ============================================================================
*/


/**
* 现在我们有了AST,我们希望能够通过访问者访问不同的节点。我们需要能够在遇到具有匹配类型的节点时调用访问器上的方法。
*
* traverse(ast, {
* Program: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
*
* CallExpression: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
*
* NumberLiteral: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
* });
*/


// 所以我们定义了一个遍历函数,它接受AST和visitor。在里面,我们将定义两个函数。
function traverser(ast, visitor) {

// 定义一个`traverseArray`函数,它允许我们迭代数组并调用我们将定义的下一个函数:`traverseNode`。
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}

// `traverseNode`将接受`node`及其`parent`节点。这样它就可以同时传递给我们的visitor方法。
function traverseNode(node, parent) {

// 我们首先测试具有匹配的“type`”的访问者上是否存在一个方法。
let methods = visitor[node.type];

// 如果该节点类型有`enter`方法,我们会使用`node`及其`parent`来调用它。
if (methods && methods.enter) {
methods.enter(node, parent);
}

// 接下来,我们将按当前节点类型进行不同的处理。
switch (node.type) {

// 我们从顶级的`Program`开始。由于Program节点有一个名为Body的属性,该属性有一个节点数组,因此我们将调用`traverseArray`向下遍历到这些节点中。
// (注意,`traverseArray`将依次调用`traverseNode`,因此我们将导致递归遍历树)
case 'Program':
traverseArray(node.body, node);
break;

// 下面,对于 `CallExpression` 将他们的 `params` 做同样的遍历.
case 'CallExpression':
traverseArray(node.params, node);
break;

// 在`NumberWrital`和`StringWrital`的情况下,我们没有任何要访问的子节点,所以我们将中断。
case 'NumberLiteral':
case 'StringLiteral':
break;

// 如果没有type则抛异常
default:
throw new TypeError(node.type);
}

// 如果该节点类型有`exit`方法,我们将使用`node`及其`parent`调用它。
if (methods && methods.exit) {
methods.exit(node, parent);
}
}

// 最后,我们通过调用带有AST的`traverseNode`来启动遍历器,但没有`parent`,因为AST的顶层没有父级。
traverseNode(ast, null);
}

/**
* ============================================================================
* ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽
* 转换器(THE TRANSFORMER!!!)
* ============================================================================
*/


/**
* 接下来是转换器。我们的转换器将获取我们构建的AST,并将其传递给具有访问者的遍历函数,并将创建一个新的AST。
*
* ----------------------------------------------------------------------------
* Original AST | Transformed AST
* ----------------------------------------------------------------------------
* { | {
* type: 'Program', | type: 'Program',
* body: [{ | body: [{
* type: 'CallExpression', | type: 'ExpressionStatement',
* name: 'add', | expression: {
* params: [{ | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }, { | name: 'add'
* type: 'CallExpression', | },
* name: 'subtract', | arguments: [{
* params: [{ | type: 'NumberLiteral',
* type: 'NumberLiteral', | value: '2'
* value: '4' | }, {
* }, { | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }] | name: 'subtract'
* }] | },
* }] | arguments: [{
* } | type: 'NumberLiteral',
* | value: '4'
* ---------------------------------- | }, {
* | type: 'NumberLiteral',
* | value: '2'
* | }]
* (sorry the other one is longer.) | }
* | }
* | }]
* | }
* ----------------------------------------------------------------------------
*/


// 所以我们创建一个转换器函数可以接受最后的LISP的AST对象
function transformer(ast) {

// 我们将创建一个`newAst`,与前面的AST一样,它将有一个程序节点。
let newAst = {
type: 'Program',
body: [],
};

//接下来,我将用一个小技巧。我们将在父节点上使用名为`context`的属性,将节点推送到其父节点的`context`。
// 通常情况下,您会有比这更好的抽象,但出于我们的目的,这会使事情变得简单。
//
// 需注意上下文是从"旧ast"到"新ast"的引用。
ast._context = newAst.body;

// 我们将从使用ast和一个访问者调用遍历器函数开始。
traverser(ast, {

// 第一个访问器方法接受任何`NumberWrital`
NumberLiteral: {
// 在enter函数中访问`NumberWrital`
enter(node, parent) {
// 我们将创建一个名为`NumberWrital`的新节点,并将其推送到父上下文中。
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},

// 然后处理 `StringLiteral`
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},

// 然后, `CallExpression`.
CallExpression: {
enter(node, parent) {

// 我们开始创建一个带有嵌套`Identifier`的新节点`CallExpression`。 这里新的AST Node,和LISP语言AST Node的结构就产生了差异。
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};

// 接下来,我们将在原始的`CallExpression`节点上定义一个新的上下文,它将引用`expression`的arguments数组
// 以便我们可以在后面的递归中,推送新的AST Node到arguments数组中。
node._context = expression.arguments;

// 检测父节点是否是 `CallExpression`.
// 如果不是
if (parent.type !== 'CallExpression') {

//我们将用`ExpressionStatement`包装`CallExpression`节点。我们这样做是因为JavaScript中的顶层`CallExpression`实际上是语句。
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}

// 最后,我们将(可能包装的)`CallExpression`推送到`parent`的`context`
parent._context.push(expression);
},
}
});

// 在转换器函数的末尾,我们将返回刚刚创建的新ast。
return newAst;
}

/**
* ============================================================================
* ヾ(〃^∇^)ノ♪
* 代码生成器(THE CODE GENERATOR!!!!)
* ============================================================================
*/


/**
* 现在让我们进入最后一个阶段:代码生成器。
*
* 我们的代码生成器将递归调用自身,将树中的每个节点打印到一个巨大的字符串中。
*/


function codeGenerator(node) {

// 我们将按“节点”的“类型”来分析。
switch (node.type) {

// 如果是‘Program’节点。我们将处理`body‘中的每个节点,并通过代码生成器运行它们,然后用换行符将它们连接起来。
case 'Program':
return node.body.map(codeGenerator)
.join('\n');

// 如果是 `ExpressionStatement`,我们将用代码生成器运行它并在末尾加上分号
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...because we like to code the *correct* way)
);

// 对于`CallExpression`,我们将打印`callee`,添加一个左括号,`arguments`数组中的每个节点通过代码生成器运行,然后用逗号将它们连接起来,最好在末尾添加括号。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);

// 对于 `Identifier` 节点,直接返回它的名字就行了
case 'Identifier':
return node.name;

// 对于数字节点,返回value
case 'NumberLiteral':
return node.value;

// 对于字符串节点,返回用双引号包裹的字符串value
case 'StringLiteral':
return '"' + node.value + '"';

// 位置的节点类型,抛出异常
default:
throw new TypeError(node.type);
}
}

/**
* ============================================================================
* (۶* ‘ヮ’)۶”
* !!!!!!!!THE COMPILER!!!!!!!!
* ============================================================================
*/


/**
* 最好!我们将创建我们的`编译器‘函数。在这里,我们将把上面的pipeline的每一部分连接起来。
*
* 1. input => tokenizer => tokens
* 2. tokens => parser => ast
* 3. ast => transformer => newAst
* 4. newAst => generator => output
*/


function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);

// and simply return the output!
return output;
}

/**
* ============================================================================
* (๑˃̵ᴗ˂̵)و
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!完事!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* ============================================================================
*/


// 暴露所有的函数...
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};

上面的代码可以直接运行

1
2
compiler("(add 2 (subtract 4 2))")
//输出:add(2, subtract(4, 2));

☞ 参与评论