README.txt

*前言：
  从词法分析，到语法分析，到三地址代码生成，这个几个阶段的本质还只是对字符串的转换，是静态编译阶段。而运行时指的是程序执行顺序、执行环境、内存动态分配等内容。
  运行时刻跟编译时刻虽然是两个不同的阶段，但是由于运行时刻用到的指令是由编译器生成的，要使编译器生成正确指令，必需对程序运行时有足够的了解。如此才能解决在前面一节《03_中间代码生成》的三地址表达式实例2中提出的问题，才能生成能够精确翻译为机器码的中间码。
  总而言之，要使机器码执行时符合ECMA-262标准（https://www.ecma-international.org/publications-and-standards/standards/ecma-262/），就必须先了解该标准，并想法设法使生成的线性代码在运行时符合该标准。


*运行存储分配：
·操作系统对内存的划分:
  -- 操作系统给内存进行规划，将内存大概分成操作系统内核内存和给程序员使用的内存2大部分
  -- 这样的好处是：操作系统的内存不会被大量占用，避免机器卡住、卡死、死机等状态，可通过操作系统把应用程序关闭，使得操作系统更安全
·程序运行存储分配策略：
  -- 静态存储分配：
       -- 数据对象大小确定，编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形
       -- 例如全局常量、全局变量就可以采用静态存储分配
       -- 这种分配策略要求程序代码中不允许有可变数据结构(比如可变数组)的存在,也不允许有嵌套或者递归的结构出现,因为它们都会导致编译程序无法计算准确的存储空间需求
       -- 常用的静态存储分配方法：
          -- 顺序分配法：
             假设一个程序生成了6个过程，树表示过程间的调用关系：
                      1/22 
                     /    \
                  2/15    3/18
                  /   \  /   \
                4/17  6/10   5/23
             过程     存储区域
               1         0~21
               2        22~36
               3        37~54
               4        55~71
               5        72~94
               6        95~104
             特点：按照过程出现的先后顺序逐段分配存储空间；各过程的活动记录占用互不相交的存储空间
             优点：处理上简单
             缺点：对内存空间的使用不够经济合理
          -- 层次分配法：https://www.pianshen.com/article/13011737518/
       -- 实现静态存储分配：
          -- 编译程序对源程序进行处理时，对每个变量在符号表中创建一个记录，保存该变量的属性，其中包括为变量分配的存储空间地址即目标地址
          -- 由于每个变量需要的空间大小已知，则可将数据区开始位置的地址A分配给第一个变量，设第一个变量占n1个字节，则A + n1分配给第二个变量。同理，A + n1 + n2分配给第三个变量等等
             -- 静态存储分配把内存看成一个一维数组。 编译时分配存储单元，运行时才被占用 。一旦分配，运行期间就一直被某个变量占用
          -- 目标地址可以是绝对地址，也可以是相对地址
             -- 开始如果编写的编译程序是用于单任务环境，那么，通常采用绝对地址作为目标地址。 程序和数据区 (开始地址A) 可以放在操作系统的长驻区以外的存储区中
             -- 如果编译程序是在多任务环境中，那么目标地址可采用相对地址，也就是相对于程序数据区的基地址。加载器通过设置一个寄存器，并将数据区的头地址送入该寄存器内以完成数据区的定位
  -- 动态存储分配：
       -- 数据对象大小不确定，在运行时才能进行内存分配
       -- 分为栈式和堆式2种：
          -- 栈式存储分配：用后进先出（LIFO）的动态分配预留的内存空间
          -- 堆式存储分配：没有固定模式的动态分配预留的内存空间
·常见语言的运行存储分配策略：
  -- 早期的FORTRAN语言及COBOL语言等，其存储分配是完全静态的，程序的数据对象与其存储的绑定是在编译期间进行的。而
  -- 另一些语言，所有数据对象与其存储的绑定只能发生在运行期间，完全采用动态存储分配，如Lisp、ML、Perl等。
  -- 多数语言（如Js、C/C++、Java、Pascal等）采取的存储分配策略是结合静态和动态两者的
·栈内存和堆内存的本质区别：
  -- 栈内存和堆内存在物理上都是一样的，都是物理内存的一部分，只不过是操作系统根据程序运行特点将虚拟内存进行了抽象分类
  -- 操作系统为何要将内存分为栈内存和堆内存呢？
     -- 栈是函数调用最方便的实现方式：在汇编里，变量的概念几乎没有了，有的只是各种内存地址，不管是实地址还是虚地址，你访问一个变量就是靠地址，所以如果你不记住一个变量的地址，你就没办法去操作它，这就产生了问题，如果你的程序要1000个变量，你就把他们的地址全记下来吗？这显然是不现实的，首先这会浪费很多空间，因为几乎任何操作都离不开操作变量，也就是地址，那么就相当于你要用两倍甚至更多的空间来表示你的程序，而一半浪费在地址上，其次这样写程序也是没有效率的，1000个变量，难道你能把他们的地址全背下来吗？或者说当你看到地址0x1234的值赋值给地址0x2345时，你如何记得起0x1234和0x2345是两个干什么用的变量？所以以一种系统的方法管理内存就显得尤为重要。而栈具有先进后出和内存连续性的特点，能够很好的描述函数运行时的状态，并且通过指针偏移方便计算出变量的内存位置。
     -- 因为结构化语言里函数调用最方便的实现方式就是用栈，以至于现在绝大部分芯片都对栈提供芯片级的硬件支持，一条指令即可搞定栈的pop操作。栈的好处是：方便、快、有效避免内存碎片化。栈的问题是：不利于管理大内存（尤其在16位和32位时代）、数据的生命周期难于控制（栈内的有效数据通常是连续存储的，所以pop时后申请的内存必须早于先申请的内存失效），所以栈不利于动态地管理并且有效地利用宝贵的内存资源。于是我们有了堆
     -- 从软件设计的角度看，栈代表了处理逻辑，而堆代表了数据。这样分开，使得处理逻辑更为清晰。分而治之的思想。这种隔离、模块化的思想在软件设计的方方面面都有体现。
     -- 堆与栈的分离，使得堆中的内容可以被多个栈共享（也可以理解为多个线程访问同一个对象）。这种共享的收益是很多的。一方面这种共享提供了一种有效的数据交互方式(如：共享内存)，另一方面，堆中的共享常量和缓存可以被所有栈访问，节省了空间。
     -- 栈因为运行时的需要，比如保存系统运行的上下文，需要进行地址段的划分。由于栈只能向上增长，因此就会限制住栈存储内容的能力。而堆不同，堆中的对象是可以根据需要动态增长的，因此栈和堆的拆分，使得动态增长成为可能，相应栈中只需记录堆中的一个地址即可。
  -- 出于程序运行特点，操作系统对堆和栈做了划分，并使其具备各自特点：
     -- Stack:
        -- 和堆一样存储在计算机RAM中
        -- 在栈上创建变量的时候会扩展，并且会自动回收
        -- 相比堆而言在栈上分配要快的多
        -- 用数据结构中的栈实现
        -- 存储局部数据，返回地址，用做参数传递
        -- 当用栈过多时可导致栈溢出（无穷次（大量的）的递归调用，或者大量的内存分配）
        -- 在栈上的数据可以直接访问（不是非要使用指针访问）
        -- 如果你在编译之前精确的知道你需要分配数据的大小并且不是太大的时候，可以使用栈
        -- 当你程序启动时决定栈的容量上限
     -- Heap：
        -- 和栈一样存储在计算机RAM
        -- 在堆上的变量必须要手动释放，不存在作用域的问题
        -- 相比在栈上分配内存要慢
        -- 通过程序按需分配
        -- 大量的分配和释放可造成内存碎片
        -- 在C++中，在堆上创建数的据使用指针访问，用new或者malloc分配内存；JS中，自带垃圾回收器进行堆对象回收
        -- 如果申请的缓冲区过大的话，可能申请失败
        -- 在运行期间你不知道会需要多大的数据或者你需要分配大量的内存的时候，建议你使用堆
        -- 可能造成内存泄露
·对于支持递归进程的内存具体规划，从低位到高位分别是：可参考图《递归语言的运行时内存划分.jpg》
  -- 代码段（文本段）：函数编译成opcode(二进制)后存到磁盘，运行时将二进制从磁盘加载到内存中
  -- 数据段（静态空间）：全局变量、常量、静态变量存数据段
  -- 堆：比栈内存大得多，一般有几G大小
  -- 自由可分配内存：运行时逐渐被堆栈占据，运行完后数据释放空间恢复
  -- 栈：第一个函数运行时压入栈底，函数调新函数时再往栈里压入该新函数，新函数运行完即出栈，第一个函数运行完再出栈，栈为空
  -- 内核：内核区是所有进程共享的



*栈式存储分配：
·活动记录
  -- 使用过程(或函数、方法)作为用户自定义动作的单元的语言，其编译器通常以过程为单位分配存储空间
  -- 活动：activation，过程体的每次执行称为该过程的一个活动
  -- 过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录
·栈式存储分配特点：
  -- 当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈。
  -- 栈式存储不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且允许以如下方式为一个过程编译代码：它的非局部变量的相对地址总是固定的
·寄存器与函数栈帧
  -- 栈帧：函数调用经常是嵌套的，在同一时刻，堆栈中会有多个函数的信息。每个未完成运行的函数占用一个独立的连续区域，称作栈帧(Stack Frame)
  -- 每一个函数独占自己的栈帧空间。当前正在运行的函数的栈帧总是在栈顶。Win32系统提供两个特殊的寄存器用于标识位于系统栈顶端的栈帧。
     -- ESP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的栈顶，当我们往栈内添加数据时，ESP就会往上移动该数据的大小。
     -- EBP：基址指针寄存器(extended base pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的底部
  -- 图例：《寄存器对栈的标识作用.png》
·嵌套函数在栈中的调用过程：当函数A执行到第2行时，开始运行函数B，此时A停止开始运行B，并向系统栈中压入A2（表示函数A的第2行），当B执行到第2行时开始运行函数C，并在系统栈中压入B2，当C运行完时再查看系统栈，发现了B2，系统开始继续执行B的第2行，B执行完后查看系统栈，发现A2，则继续执行A直到完成。
·JavaScript的语言特点：
  -- 函数允许嵌套、支持递归
  -- 传参：所有函数的参数都是按值传递的,也就是说把函数外部的值复制给函数内部的参数
      例子1：
        var person  = {
            name : "Tom"
        };
        function obj(peo){
            peo.name = "Jerry";
            return peo;
        }
        var result = obj(person);
        console.log(result.name);// Jerry
        console.log(person.name);// Jerry
      例子2：
        var person = {
            name : "Tom"
        }; 
        function obj(peo){
            peo = {
              name : "Jerry"
            };
            return peo;
        }
        var result = obj(person);
        console.log(result.name);// Jerry
        console.log(person.name);// Tom
  -- 遵循静态作用域
     所谓的词法作用域其实是指作用域在词法解析阶段既确定了，不会改变。例子：
      var foo=1;
      function static(){
        alert(foo);
      }
      !function(){
        var foo=2;
        static();
      }();
     在js中，会弹出1而非2，因为static的scope在创建时，记录的foo是1。如果js是动态作用域，那么他应该弹出2
  -- 数据类型：
     -- 基本类型：基本数据类型都储存在栈中
     -- 引用类型：引用类型的值是储存在堆中，栈内存中保存着一个堆内存的对象的引用
·作用域
  -- 作用域分为：词法作用域（也叫静态作用域）和环境作用域（也叫执行时作用域/动态作用域）。
  -- js遵循词法作用域
  -- 词法作用域：在词法分析时就可以知道一个变量的作用域，如果是有一个作用域，则创建一个block，满足“最近嵌套原则”，并形成一个作用域链。作用域在你写代码时将变量和块作用域写在哪里时就已经决定
  -- 子作用域：js在调用函数时会创建一个子环境，并且，父环境对象作为一个参数传入这个子环境对象创建当中，这个子环境就是一个子作用域
  -- 词法闭包：在词法分析时就可以知道闭包的存在
  -- 定义作用域：
      LexicalSope
        -- add：为当前作用域添加子作用域
        -- bind：添加变量进入词法作用域
        -- find：在词法作用域中查找变量
        -- table：存数据的哈希表
        -- id：int索引
·全局运行环境：
  -- 除了程序员自身写的代码外，程序自身会自带一个全局运行环境，例如js中在浏览器中的window对象，在node环境中的global对象
  -- 全局运行环境的组成：
     -- hashmap：{}
     -- level：0  //环境当前的嵌套层级，初始为0
     -- parent：sp  //子环境（字作用域）指向父环境的指针
·源码到运行时的内存分配分析：
  源码：          三地址码：     符号表的设计    翻转符号表   映射到运行时的地址
  var a=2*3+1     p0=2*3         p0              b            sp+0
  var b=a+1       p1=p0+1        p1              a            sp+4
                  a=p1           a               p1           sp+8
                  b=a+1          b               p2           sp+12
·三地址表达式实例2（斐波那契函数）栈的活动记录图示：
      栈空间（通过指针偏移拿到数据）                 代码段（通过行号值拿到数据）    
    |  link7   |                           
    //link7会指向数字2                            |     f    |
    |     2    |                                 |  t1=n==1  |
    |  link6   |                                 |  t2=n==2  |
    |  link5   |                                 |t3=t1 or t2|
    |其他临时变量|                                |           |
    |  返回值3 |                                  |branch goto|
    |     3    |                                 |   ...     |
    |  link4   |                                 |           |
    |  link3   |                                 |           |
    |其他临时变量|                                |           |
    |  返回值2 |                                  |          |
    |     4    |                                 |           |
    |  link2   |                                 |           |
    //link2会指向数字5（即上一个栈帧 ）            |           |
    |  link1   |                                 |           |
    //link1会指向代码call f                       |           |
    |其他临时变量|                                |           |
    |  返回值1 |                                  |          |
    //返回值可根据5的偏移量计算拿到                |           |  
    //通过push空为返回值1占位                     |   call f  |
    |     5    |                                 //call f将指向f函数体的第一行
    ------------                                 --------------
  运行时分析：
    程序执行时，操作系统首先会开辟一个内存空间（具体参考《递归语言的运行时内存划分.jpg》），并将二进制机器码（为了易于理解，我们这里讨论的机器码用三地址码表示）载入存到开辟的内存的代码段，此时CS（Code Segment，代码段寄存器）指向该代码段的基址。
    通过CS:IP（即Instruction Pointer，指令指针寄存器，即代码段CS对应的偏移指针）的指向从内存中取出下一条执行的指令，产生如下流程：取出的指令装入CPU的指令寄存器 → 执行指令 → IP++（即指向下一条指令了）或 通过JMP等跳转指令重新修改CS:IP而该表下一条指令的位置 → 重复第一步（循环）。
    当然，在前面运行存储分配讲到，对于JS这种复杂的语言不会这么简单执行，而是要依赖栈进行临时数据和执行流程进行管理。根据ecma-262标准，JS引擎会先创建一个全局环境，并将全局上下文压入栈底。当遇到函数执行时，会创建函数执行上下文，并将该上下文压入栈顶。而栈中的指令可以根据EBP:ESP（ESP是堆栈指针寄存器，存放执行函数对应栈帧的栈顶地址(也是系统栈的顶部)，且始终指向栈顶；EBP是栈帧基址指针寄存器，存放执行函数对应栈帧的栈底地址）获取当前的内存地址空间，以指导生成准确操作数的机器码。
    通过栈的指针偏移和代码段的指针偏移，两者配合就可以完成运行时的内存分配，并记录下各个数据的地址。    
·设计一个三地址码生成规则：
  -- @：表示作用域
  -- section：执行上下文
  -- set：赋值
  -- branch：if语句判断
  -- $：临时变量
  -- call：调用函数
  -- %:寄存器，%TOP%表示TOP寄存器
  -- SP：指针
  -- call：函数调用
  -- pass：表示传参
·源码 → 三地址
    function fibonacci(n){
      if(n==1 || n==2){
        return n
      }
      return fibonacci(n-1)+fibonacci(n-2)
    }
    print(fibonacci(5))
  转换后的三地址码：
    section fibonacci@2
    set %TOP% %SP%
    set $t1@2 n==1
    set $t2@2 n==2
    set $t3@2 $t1@2 || $t2@2
    branch $t3@2 LB1  //$t3@2为true时继续，否则跳转到LB1行
    return n@2
    LB1:set $t4@2 n-1
    pass $t4@2    //pass表示传参，压栈
    call fibonacci@1
    set $6@2 n-2
    pass $t6@2    //pass表示传参，压栈
    call fibonacci@1
    set $t8@2 $t5@2 + $t7@2
    return $t8@2@2
    section main@1
    set %TOP% %SP%
    declare function fibonacci@1
    pass 5
    call fibonacci@1
    pass $t2@1
    call print@1