实现一个小的编译器

来自于👉 the-super-tiny-compiler-CN,只是为了路上看着方便,BTW 分享。

  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
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
'use strict';

/**
 * TTTTTTTTTTTTTTTTTTTTTTTHHHHHHHHH     HHHHHHHHHEEEEEEEEEEEEEEEEEEEEEE
 * T:::::::::::::::::::::TH:::::::H     H:::::::HE::::::::::::::::::::E
 * T:::::::::::::::::::::TH:::::::H     H:::::::HE::::::::::::::::::::E
 * T:::::TT:::::::TT:::::THH::::::H     H::::::HHEE::::::EEEEEEEEE::::E
 * TTTTTT  T:::::T  TTTTTT  H:::::H     H:::::H    E:::::E       EEEEEE
 *         T:::::T          H:::::H     H:::::H    E:::::E
 *         T:::::T          H::::::HHHHH::::::H    E::::::EEEEEEEEEE
 *         T:::::T          H:::::::::::::::::H    E:::::::::::::::E
 *         T:::::T          H:::::::::::::::::H    E:::::::::::::::E
 *         T:::::T          H::::::HHHHH::::::H    E::::::EEEEEEEEEE
 *         T:::::T          H:::::H     H:::::H    E:::::E
 *         T:::::T          H:::::H     H:::::H    E:::::E       EEEEEE
 *       TT:::::::TT      HH::::::H     H::::::HHEE::::::EEEEEEEE:::::E
 *       T:::::::::T      H:::::::H     H:::::::HE::::::::::::::::::::E
 *       T:::::::::T      H:::::::H     H:::::::HE::::::::::::::::::::E
 *       TTTTTTTTTTT      HHHHHHHHH     HHHHHHHHHEEEEEEEEEEEEEEEEEEEEEE
 *
 *    SSSSSSSSSSSSSSS UUUUUUUU     UUUUUUUUPPPPPPPPPPPPPPPPP   EEEEEEEEEEEEEEEEEEEEEERRRRRRRRRRRRRRRRR
 *  SS:::::::::::::::SU::::::U     U::::::UP::::::::::::::::P  E::::::::::::::::::::ER::::::::::::::::R
 * S:::::SSSSSS::::::SU::::::U     U::::::UP::::::PPPPPP:::::P E::::::::::::::::::::ER::::::RRRRRR:::::R
 * S:::::S     SSSSSSSUU:::::U     U:::::UUPP:::::P     P:::::PEE::::::EEEEEEEEE::::ERR:::::R     R:::::R
 * S:::::S             U:::::U     U:::::U   P::::P     P:::::P  E:::::E       EEEEEE  R::::R     R:::::R
 * S:::::S             U:::::U     U:::::U   P::::P     P:::::P  E:::::E               R::::R     R:::::R
 *  S::::SSSS          U:::::U     U:::::U   P::::PPPPPP:::::P   E::::::EEEEEEEEEE     R::::RRRRRR:::::R
 *   SS::::::SSSSS     U:::::U     U:::::U   P:::::::::::::PP    E:::::::::::::::E     R:::::::::::::RR
 *     SSS::::::::SS   U:::::U     U:::::U   P::::PPPPPPPPP      E:::::::::::::::E     R::::RRRRRR:::::R
 *        SSSSSS::::S  U:::::U     U:::::U   P::::P              E::::::EEEEEEEEEE     R::::R     R:::::R
 *             S:::::S U:::::U     U:::::U   P::::P              E:::::E               R::::R     R:::::R
 *             S:::::S U::::::U   U::::::U   P::::P              E:::::E       EEEEEE  R::::R     R:::::R
 * SSSSSSS     S:::::S U:::::::UUU:::::::U PP::::::PP          EE::::::EEEEEEEE:::::ERR:::::R     R:::::R
 * S::::::SSSSSS:::::S  UU:::::::::::::UU  P::::::::P          E::::::::::::::::::::ER::::::R     R:::::R
 * S:::::::::::::::SS     UU:::::::::UU    P::::::::P          E::::::::::::::::::::ER::::::R     R:::::R
 *  SSSSSSSSSSSSSSS         UUUUUUUUU      PPPPPPPPPP          EEEEEEEEEEEEEEEEEEEEEERRRRRRRR     RRRRRRR
 *
 * TTTTTTTTTTTTTTTTTTTTTTTIIIIIIIIIINNNNNNNN        NNNNNNNNYYYYYYY       YYYYYYY
 * T:::::::::::::::::::::TI::::::::IN:::::::N       N::::::NY:::::Y       Y:::::Y
 * T:::::::::::::::::::::TI::::::::IN::::::::N      N::::::NY:::::Y       Y:::::Y
 * T:::::TT:::::::TT:::::TII::::::IIN:::::::::N     N::::::NY::::::Y     Y::::::Y
 * TTTTTT  T:::::T  TTTTTT  I::::I  N::::::::::N    N::::::NYYY:::::Y   Y:::::YYY
 *         T:::::T          I::::I  N:::::::::::N   N::::::N   Y:::::Y Y:::::Y
 *         T:::::T          I::::I  N:::::::N::::N  N::::::N    Y:::::Y:::::Y
 *         T:::::T          I::::I  N::::::N N::::N N::::::N     Y:::::::::Y
 *         T:::::T          I::::I  N::::::N  N::::N:::::::N      Y:::::::Y
 *         T:::::T          I::::I  N::::::N   N:::::::::::N       Y:::::Y
 *         T:::::T          I::::I  N::::::N    N::::::::::N       Y:::::Y
 *         T:::::T          I::::I  N::::::N     N:::::::::N       Y:::::Y
 *       TT:::::::TT      II::::::IIN::::::N      N::::::::N       Y:::::Y
 *       T:::::::::T      I::::::::IN::::::N       N:::::::N    YYYY:::::YYYY
 *       T:::::::::T      I::::::::IN::::::N        N::::::N    Y:::::::::::Y
 *       TTTTTTTTTTT      IIIIIIIIIINNNNNNNN         NNNNNNN    YYYYYYYYYYYYY
 *
 *         CCCCCCCCCCCCC     OOOOOOOOO     MMMMMMMM               MMMMMMMMPPPPPPPPPPPPPPPPP   IIIIIIIIIILLLLLLLLLLL             EEEEEEEEEEEEEEEEEEEEEERRRRRRRRRRRRRRRRR
 *      CCC::::::::::::C   OO:::::::::OO   M:::::::M             M:::::::MP::::::::::::::::P  I::::::::IL:::::::::L             E::::::::::::::::::::ER::::::::::::::::R
 *    CC:::::::::::::::C OO:::::::::::::OO M::::::::M           M::::::::MP::::::PPPPPP:::::P I::::::::IL:::::::::L             E::::::::::::::::::::ER::::::RRRRRR:::::R
 *   C:::::CCCCCCCC::::CO:::::::OOO:::::::OM:::::::::M         M:::::::::MPP:::::P     P:::::PII::::::IILL:::::::LL             EE::::::EEEEEEEEE::::ERR:::::R     R:::::R
 *  C:::::C       CCCCCCO::::::O   O::::::OM::::::::::M       M::::::::::M  P::::P     P:::::P  I::::I    L:::::L                 E:::::E       EEEEEE  R::::R     R:::::R
 * C:::::C              O:::::O     O:::::OM:::::::::::M     M:::::::::::M  P::::P     P:::::P  I::::I    L:::::L                 E:::::E               R::::R     R:::::R
 * C:::::C              O:::::O     O:::::OM:::::::M::::M   M::::M:::::::M  P::::PPPPPP:::::P   I::::I    L:::::L                 E::::::EEEEEEEEEE     R::::RRRRRR:::::R
 * C:::::C              O:::::O     O:::::OM::::::M M::::M M::::M M::::::M  P:::::::::::::PP    I::::I    L:::::L                 E:::::::::::::::E     R:::::::::::::RR
 * C:::::C              O:::::O     O:::::OM::::::M  M::::M::::M  M::::::M  P::::PPPPPPPPP      I::::I    L:::::L                 E:::::::::::::::E     R::::RRRRRR:::::R
 * C:::::C              O:::::O     O:::::OM::::::M   M:::::::M   M::::::M  P::::P              I::::I    L:::::L                 E::::::EEEEEEEEEE     R::::R     R:::::R
 * C:::::C              O:::::O     O:::::OM::::::M    M:::::M    M::::::M  P::::P              I::::I    L:::::L                 E:::::E               R::::R     R:::::R
 *  C:::::C       CCCCCCO::::::O   O::::::OM::::::M     MMMMM     M::::::M  P::::P              I::::I    L:::::L         LLLLLL  E:::::E       EEEEEE  R::::R     R:::::R
 *   C:::::CCCCCCCC::::CO:::::::OOO:::::::OM::::::M               M::::::MPP::::::PP          II::::::IILL:::::::LLLLLLLLL:::::LEE::::::EEEEEEEE:::::ERR:::::R     R:::::R
 *    CC:::::::::::::::C OO:::::::::::::OO M::::::M               M::::::MP::::::::P          I::::::::IL::::::::::::::::::::::LE::::::::::::::::::::ER::::::R     R:::::R
 *      CCC::::::::::::C   OO:::::::::OO   M::::::M               M::::::MP::::::::P          I::::::::IL::::::::::::::::::::::LE::::::::::::::::::::ER::::::R     R:::::R
 *         CCCCCCCCCCCCC     OOOOOOOOO     MMMMMMMM               MMMMMMMMPPPPPPPPPP          IIIIIIIIIILLLLLLLLLLLLLLLLLLLLLLLLEEEEEEEEEEEEEEEEEEEEEERRRRRRRR     RRRRRRR
 *
 * =======================================================================================================================================================================
 * =======================================================================================================================================================================
 * =======================================================================================================================================================================
 * =======================================================================================================================================================================
 */

/**
 * 今天我们会一起编写一个编译器。一个非常非常简化的微型编译器!这个编译器非常小,如果你移除这个
 * 文件里的注释,那么这个文件只剩下大概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. *代码生成* 基于转换后的代码表现形式(code representation)生成目标代码。
 */

/**
 * 解析
 * -------
 *
 * 解析一般被分为两个部分:词法分析和语法分析。
 *
 * 1. *词法分析* 通过一个叫做tokenizer(词素生成器,也叫lexer)的工具将源代码分解成一个个词素。
 *
 *    词素是描述编程语言语法的对象。它可以描述数字,标识符,标点符号,运算符等等。
 *
 * 2. *语法分析* 接收词素并将它们组合成一个描述了源代码各部分之间关系的中间表达形式:抽象语法树。
 *
 *    抽象语法树是一个深度嵌套的对象,这个对象以一种既能够简单地操作又提供很多关于源代码信息的形式
 *    来展现代码。
 *
 * 看下面的代码:
 *
 *   (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: ')'        },
 *     { type: 'paren',  value: ')'        },
 *   ]
 *
 * 而产生的抽象语法树会像下面这样:
 *
 *   {
 *     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',
 *         }]
 *       }]
 *     }]
 *   }
 */

/**
 * 转换
 * --------------
 *
 * 编译器的下一个阶段是转换阶段。再回顾一遍,这个过程接收解析生成的抽象语法树并对它做出改动。
 * 转换阶段可以改变抽象语法树使代码保持在同一个语言(例如Babel,Babel接收的是JS代码生成的也是
 * JS代码),或者编译成另外一门语言。
 *
 * 让我们一起来看如何转换一个抽象语法树。
 *
 * 你可能会注意到我们的抽象语法树包含了长得非常相似的元素。观察那些含有type属性的元素。这些元素
 * 被称为抽象语法树的节点。每一个节点都描述了源代码中的一部分。
 *
 * 针对NumberLiteral我们有一个节点:
 *
 *   {
 *     type: 'NumberLiteral',
 *     value: '2',
 *   }
 *
 * 针对CallExpression我们也有一个节点:
 *
 *   {
 *     type: 'CallExpression',
 *     name: 'subtract',
 *     params: [...nested nodes go here...],
 *   }
 *
 * 在转换抽象语法树的时候,我们可以通过添加/删除/替换节点属性来操纵节点。我们也可以添加节点,
 * 删除节点,或者基于现有的抽象语法树创建一个全新的抽象语法树。
 *
 * 由于我们的编译目标是另外一门语言,所以我们集中注意力新建一个针对目标语言的全新抽象语法树。
 *
 * 遍历
 * ---------
 *
 * 为了处理节点,我们需要遍历它们。这个遍历的过程按照深度优先规则遍历每一个节点。
 *
 *   {
 *     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'
 *         }]
 *       }]
 *     }]
 *   }
 *
 * 所以针对上面这个抽象语法树我们会按照下面步骤遍历节点:
 *
 *   1. Program - 从抽象语法树的最顶端开始
 *   2. CallExpression (add) - 移动到Program的body属性中的第一个元素
 *   3. NumberLiteral (2) - 移动到CallExpression的params中的第一个元素
 *   4. CallExpression (subtract) - 移动到CallExpression的params中的第二个元素
 *   5. NumberLiteral (4) - 移动到CallExpression的params中的第一个元素
 *   6. NumberLiteral (2) - 移动到CallExpression的params中的第二个元素
 *
 * 如果我们直接操纵这个抽象语法树,而不是创建一个新的抽象语法树,那么我们就需要在这个步骤使用到
 * 很多不同的抽象概念。然而为了满足我们的需求,在这一步我们仅仅需要访问抽象语法树中的每一个节点
 * 即可。
 *
 * The reason I use the word "visiting" is because there is this pattern of how
 * to represent operations on elements of an object structure.
 * 在这里我使用“访问”这个词的与原因是因为存在着下面这个用来表示一个对象结构中元素行为的模式。
 *
 * 访问者
 * --------
 *
 * 基本的思想是我们会创建一个“访问者”对象,这个访问者对象有不同的方法来接受不同的节点类型。
 *
 *   var visitor = {
 *     NumberLiteral() {},
 *     CallExpression() {},
 *   };
 *
 * 当我们遍历抽象语法树的时候,我们会根据现在“进入”的节点的类型调用访问者对象相对应的方法。
 *
 * 为了使这个对象能够正常工作,我们需要传入当前节点以及当前节点的父节点的引用。
 *
 *   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) {},
 *     }
 *   };
 */

/**
 * 代码生成
 * ---------------
 *
 * 编译器的最后步骤是代码生成。有时候编译器在这个步骤也会执行转换阶段的一些行为,但是大体而言代
 * 码生成阶段的工作就是基于转换步骤产生的抽象语法树生成目标代码。
 *
 * 代码生成器的工作方式多种多样,一些编译器会重新利用更早阶段产生的词素,还有一些编译器会创建一
 * 个独立的代码表达形式从而能够线性地打印节点,但是基于我的经验大部分编译器会使用我们刚刚创造的
 * 那个抽象语法树,这也是我们接下来讲的方法。
 *
 * 一个有效的代码生成器知道如何“打印”抽象语法树不同类型的节点,并且会递归地调用自己来打印嵌套的
 * 节点直到整个语法树被打印成一长串完整的代码字符串。
 */

/**
 * 上面所讲到的就是编译器的所有不同部分了。
 *
 * 这并不表明所有编译器都像我上面描述的那样工作。不同的编译器有各种各样不同的目的,它们可能需要
 * 一些我没有讲到的步骤。
 *
 * 但是现在你应该已经有了一个编译器如何工作的大体概念了。
 *
 * 既然现在我已经解释了所有东西,你就可以立马动手写一个你自己的编译器了不是吗?
 *
 * 开个玩笑,我会帮助你理解如何写一个编译器 :P。
 *
 * 那么我们开始吧……
 */

/**
 * ============================================================================
 *                                   (/^▽^)/
 *                                THE TOKENIZER!
 * ============================================================================
 */

/**
 * 我们从解析步骤的第一个部分开始,词法分析。也就是tokenizer词素生成器的工作。
 *
 * 我们将源代码分解成一个词素数组。
 *
 *   (add 2 (subtract 4 2))   =>   [{ type: 'paren', value: '(' }, ...]
 */

// 我们首先需要接收一个代码字符串,并且我们需要设置两个变量……
function tokenizer(input) {
  // `current`变量跟踪我们现在在源代码中的什么地方,就像一个光标一样。
  let current = 0;

  // `tokens`变量,顾名思义,用来储存词素的数组。
  let tokens = [];

  // 我们从创建一个`while`循环开始,在这个循环里我们会根据需求增加`current`变量的值。
  //
  // 注意由于词素的长度不同的,我们可能需要在一次循环中多次增加`current`的值。
  while (current < input.length) {
    // 我们将input中的当前字符存到char变量中。
    let char = input[current];

    // 我们需要检测的第一个情况就是开括号,这在之后会被函数调用`CallExpression`所用到。但是
    // 现在我们只需要关心字符即可。
    //
    // 我们检测我们是否有一个开括号:
    if (char === '(') {
      // 如果我们有一个开括号,我们创建一个类型为`paren`的词素并将value设置为开括号。
      tokens.push({
        type: 'paren',
        value: '(',
      });

      // 之后我们增加`current`
      current++;

      // 然后我们继续进行下一个循环
      continue;
    }

    // 接下来我们需要检测的是闭括号。这里的行为和开括号的一模一样:检查是否是一个闭括号,如果是
    // 的话,创建一个新词素,增加`current`然后执行下一个循环。
    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      });
      current++;
      continue;
    }

    // 接下来我们需要检测得是空格。这非常有趣,因为空格只是为了易读性而被添加的,所以我们并不需
    // 要将其储存为一个词素。我们简单地不管它就好。
    //
    // 所以这里我们仅仅检测当前字符是否是一个空格,如果是的话我们直接继续下一个循环。
    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    // 下一个词素类型是数字。这和我们之前碰到的情况都不一样,因为一个数字可能包含任意数量的字符。
    // 我们需要捕获数字的所有字符来创建一个词素。
    //
    //   (add 123 456)
    //        ^^^ ^^^
    //        上面代码中数字只构成了两个词素
    //
    // 所以我们在碰到一个序列中的第一个数字的时候开始下面的步骤。
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {
      // 我们会创造一个`value`字符串,这个字符串用来存储字符。
      let value = '';

      // 之后我们遍历序列中的每一个字符直到遇到一个不是数字的字符,把每一个字符添加到`value`
      // 字符串中并且增加`current`的值。
      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }

      // 之后我们将我们的数字词素添加到`tokens`数组。
      tokens.push({ type: 'number', value });

      // 然后我们继续下一个循环。
      continue;
    }

    // 我们同样支持字符串,字符串是由双引号"包裹的文字内容。
    //
    //   (concat "foo" "bar")
    //            ^^^   ^^^ string tokens
    //
    // 我们引号开始检测。
    if (char === '"') {
      // 创造一个`value`变量保存我们的字符串。
      let value = '';

      // 跳过意味着字符串开始的那个引号。
      char = input[++current];

      // 之后我们遍历每一个字符直到我们到达了另一个引号。
      while (char !== '"') {
        value += char;
        char = input[++current];
      }

      // 跳过意味着字符串结尾的引号。
      char = input[++current];

      // 然后创造字符串词素并添加到`tokens`数组。
      tokens.push({ type: 'string', value });

      continue;
    }

    // 最后一种词素是`name`词素。这是一个字母序列,在我们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];
      }

      // 之后创建词素并添加到`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!!!
 * ============================================================================
 */

/**
 * 我们的语法分析器接受我们的词素数组并创造出一个抽象语法树。
 *
 *   [{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] }
 */

// 好的,那么我们定义一个`parser`函数,这个函数接收词素数组tokens。
function parser(tokens) {
  // 我们还是创建一个`current`变量跟踪我们所处的位置。
  let current = 0;

  // 但是这一次我们使用的是递归而不是一个`while`循环。所以我们定义一个`walk`函数。
  function walk() {
    // 在walk函数中我们首先获取当前词素。
    let token = tokens[current];

    // 针对不同类型的词素,我们的处理方式也不同,从数字词素开始。
    //
    // 我们检测当前词素是否为一个数字词素。
    if (token.type === 'number') {
      // 如果是一个数字词素,我们增加`current`变量的值。
      current++;

      // 之后我们返回一个类型为`NumberLiteral`类型的抽象语法树节点,并且设置这个节点的value。
      return {
        type: 'NumberLiteral',
        value: token.value,
      };
    }

    // 如果我们有一个字符串词素,那么和数字词素的情况类似,只不过这里我们返回一个`StringLiteral`
    // 类型的词素。
    if (token.type === 'string') {
      current++;

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

    // 接下来我们检测是否是一个函数调用。我们在碰到一个开括号的时候处理这种情况。
    if (token.type === 'paren' && token.value === '(') {
      // 我们会增加`current`变量的值来跳过开括号以选取下一个词素,这是因为在我们的抽象语法树
      // 中开括号本身并没有意义。
      token = tokens[++current];

      // 我们创建一个类型为`CallExpression`的基础词素,之后我们将它的名字设置为当前词素的value。
      // 这是因为开括号之后的词素的value就是函数的名字。
      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: ')'        }, <<< 闭括号
      //     { type: 'paren',  value: ')'        }, <<< 闭括号
      //   ]
      //
      // 我们依赖嵌套的`walk`函数在处理每一个嵌套的CallExpression`的时候增加我们的`current`变量。

      // 所以我们创建一个`while`循环直到我们碰到一个类型为`paren`并且`value`是闭括号的词素。
      while (
        token.type !== 'paren' ||
        (token.type === 'paren' && token.value !== ')')
      ) {
        // 我们调用`walk`函数,`walk`函数会返回一个节点然后我们将这个节点添加到我们的`node.params`。
        node.params.push(walk());
        token = tokens[current];
      }

      // 最后我们还需要增加`current`变量来跳过闭括号。
      current++;

      // 返回这个节点。
      return node;
    }

    // 同样,如果我们没有匹配到以上任何类型,我们抛出一个错误。
    throw new TypeError(token.type);
  }

  // 现在,我们来创建我们的抽象语法树。抽象语法树的根节点是一个`Program`节点。
  let ast = {
    type: 'Program',
    body: [],
  };

  // 然后我们调用我们的`walk`函数,将返回的节点都添加到`ast.body`数组中。
  //
  // 我们在一个循环中这样做的原因是因为我们可能有多个单独的函数调用,而不是相互嵌套。
  //
  //   (add 2 2)
  //   (subtract 4 2)
  //
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  // 最后,语法分析器会返回抽象语法树。
  return ast;
}

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

/**
 * 现在我们有了抽象语法树,而我们希望可以使用一个访问者对象来访问各个节点。我们需要能够在碰到一
 * 个节点的时候调用访问者对象相应的方法。
 *
 *   traverse(ast, {
 *     Program: {
 *       enter(node, parent) {
 *         // ...
 *       },
 *       exit(node, parent) {
 *         // ...
 *       },
 *     },
 *
 *     CallExpression: {
 *       enter(node, parent) {
 *         // ...
 *       },
 *       exit(node, parent) {
 *         // ...
 *       },
 *     },
 *
 *     NumberLiteral: {
 *       enter(node, parent) {
 *         // ...
 *       },
 *       exit(node, parent) {
 *         // ...
 *       },
 *     },
 *   });
 */

// 所以我们定义一个traverser函数,这个函数接收抽象语法树以及一个访问者对象。在这个函数内部我们
// 还会定义两个函数……
function traverser(ast, visitor) {
  // `traverseArray`函数,这个函数允许我们遍历一个数组并且调用我们接下来定义的函数:"traverseNode`。
  function traverseArray(array, parent) {
    array.forEach(child => {
      traverseNode(child, parent);
    });
  }

  // `traverseNode`函数会接收一个节点以及这个节点的父节点。这样它就可以将这两个参数传递给我们
  // 的访问者对象的方法。
  function traverseNode(node, parent) {
    //我们首先检测访问者对象是否含有一个匹配当前类型节点的方法。
    let methods = visitor[node.type];

    // 如果当前类型节点有相匹配的`enter`方法,我们调用这个方法`enter`方法并传入节点以及父节点。
    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;

      // 对于`NumberLiteral`和`StringLiteral`的情况,我们并没有任何子节点去访问,所以我们
      // 直接break。
      case 'NumberLiteral':
      case 'StringLiteral':
        break;

      // 同样的,如果出现没有匹配的情况,我们抛出一个错误。
      default:
        throw new TypeError(node.type);
    }

    // 如果访问者对象针对当前类型节点存在着一个`exit`方法的话,我们在这里调用它并传入节点和父节点。
    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  // 最后,我们通过调用`traverseNode`并传入ast和null来开始遍历。这里传入null作为父节点的原
  // 因是因为抽象语法树的根节点并没有父节点。
  traverseNode(ast, null);
}

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

/**
 * 接下来就是转换器。我们的转换器会接收我们创造的抽象语法树并将它和一个访问者对象传给traverser
 * 函数。然后创造一个新的抽象语法树。
 *
 * ----------------------------------------------------------------------------
 *   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.)  |         }
 *                                    |       }
 *                                    |     }]
 *                                    |   }
 * ----------------------------------------------------------------------------
 */

// 所以我们定义一个transformer函数,这个函数接收一个lisp抽象语法树对象。
function transformer(ast) {
  // 我们会创建一个`newAst`,这个新抽象语法树和之前的抽象语法树一样有一个Program节点。
  let newAst = {
    type: 'Program',
    body: [],
  };

  // 接下来我会小小地作弊一下并使用一个小小的hack。我们会给父节点添加一个`context`属性,我们
  // 会将子节点添加到它们的父节点的`context`属性中。通常情况下你会有一个比这个更好的抽象,
  // 但是针对我们的目的这样做更简洁。
  //
  // 只要记住`context`是一个从旧的抽象语法树到新的抽象语法树的引用即可。
  ast._context = newAst.body;

  // 我们从调用traverser函数并传入抽象语法树和访问者对象开始。
  traverser(ast, {
    // 访问者对象处理的第一种情况是`NumberLiteral`节点。
    NumberLiteral: {
      // 我们会在进入节点的时候访问节点。
      enter(node, parent) {
        //我们创建一个`NumberLiteral`类型的新节点并添加到父节点的`context`。
        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) {
        // 我们创建一个新的`CallExpression`类型节点,这个新节点还有一个嵌套的`Identifier`对象。
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        };

        // 接下来我们给原始的`CallExpression`节点定义一个`context`属性。这个属性指向
        // `expression`的arguments属性,这样我们就可以添加参数了。
        node._context = expression.arguments;

        // 接下来我们检测父节点是否是一个`CallExpression`,如果不是的话……
        if (parent.type !== 'CallExpression') {
          // 我们将我们的`CallExpression`节点包裹在`ExpressionStatement`节点中。
          // 我们这样做的原因是因为JS中顶层的`CallExpression`实际上是语句。
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          };
        }

        // 最后,我们将我们的`CallExpression`(可能被包裹)添加到父节点的`context`属性。
        parent._context.push(expression);
      },
    },
  });

  // 最后,转换器会返回我们刚刚创造的全新抽象语法树。
  return newAst;
}

/**
 * ============================================================================
 *                               ヾ(〃^∇^)ノ♪
 *                            THE CODE GENERATOR!!!!
 * ============================================================================
 */

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

function codeGenerator(node) {
  // 我们根据节点类型分情况处理。
  switch (node.type) {
    // 如果我们有一个`Program`节点。我们会使用代码生成器遍历`body`属性中的所有节点然后使用
    // 换行符\n连接起来。
    case 'Program':
      return node.body.map(codeGenerator).join('\n');

    // 针对`ExpressionStatement`我们会对节点的expression属性调用代码生成器,并加上一个分号……
    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`,我们简单地返回节点的name属性。
    case 'Identifier':
      return node.name;

    // 针对`NumberLiteral`,我们简单地返回节点的值。
    case 'NumberLiteral':
      return node.value;

    // 针对StringLiteral`,我们在节点value周围加上引号。
    case 'StringLiteral':
      return '"' + node.value + '"';

    // 如果没有匹配,我们抛出一个错误。
    default:
      throw new TypeError(node.type);
  }
}

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

/**
 * 终于到了!我们定义我们的`compiler`函数。这个函数会将所有部分连接起来。
 *
 *   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);

  // 返回输出!
  return output;
}

/**
 * ============================================================================
 *                                   (๑˃̵ᴗ˂̵)و
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 * ============================================================================
 */

// 这里我只是在导出函数……
module.exports = {
  tokenizer,
  parser,
  traverser,
  transformer,
  codeGenerator,
  compiler,
};
updatedupdated2020-10-072020-10-07