前端編譯原理 the-super-tiny-compiler

時隔四個月的更新#

其實後面的遞歸步驟只是借助 JS 的引用數據類型特性，模擬了類似 c 語言的指針功能 😐 ，就是簡單的傳遞指針，不斷生成類似鏈表的數據結構，填充數據，最終得到目標代碼... 而已.. 已.

起初#

the-super-tiny-compiler 是 github 上的一個使用 js 編寫的編譯器，代碼註釋中稱其可能是最小的編譯器，可以將 lisp 風格的語言編寫為 c 風格的語言

這個編譯器項目可以說是麻雀雖小，五臟俱全

但是本人再閱讀器源代碼的時候，在生成新 ast 的過程中，對其遞歸過程產生了不解

所以從現在開始，要對源代碼進行一下分析

編譯器原理簡單來說就是
詞法分析
語法分析（生成 ast）
將 oldAst -> newAst
最後將產生的 newAst 生成目標語言語法進行輸出
將 (add 2 (subtract 4 2)) 作為輸入，得到的 ast 結構如下

const 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",
            },
          ],
        },
      ],
    },
  ],
};

得到這個結構後，執行了這樣一個函數


function transformer(ast) {
  let newAst = {
    type: "Program",
    body: []
  }

  ast._context = newAst.body
}

給 ast 對象下添加了一個新屬性，將該屬性指向了 newAst 的 body 屬性中
然後向下執行了

function transformer(ast) {
  let newAst = {
    type: "Program",
    body: []
  }

// 這裡改變 ast 的屬性就可以直接影響到 newAst 
  ast._context = newAst.body

  traverser(ast, {
    // 處理數字
    NumberLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value
        })
      }
    },
    // 字串
    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        });
      },
    },

    CallExpression: {
      enter(node, parent) {
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name
          },
          arguments: []
        }

        node._context = expression.arguments;

        if (parent.type !== "CallExpression") {
          expression = {
            type: 'ExpressionStatement',//表達式語句
            expression
          }
        }

        parent._context.push(expression)
      }
    }


  })

  return newAst//返回 newAst
}

可以看到，newAst 的數據變化只執行了一個 traverser 函數就完成了，函數把剛剛的 ast 當作參數，以及根據不同類型對 newAst 中的 body 複製的行為，

這個函數的內部是這樣子的

function traverser(ast, visitor) {

  function traverseArray(array, parent) {
    
  }

  function traverseNode(node, parent) {
    // 判斷傳入進來的 node 有沒有對應的屬性
    let methods = visitor[node.type]

    // 如果有 就給其父節點的 body 賦值進去
    if (methods && methods.enter) {
      methods.enter(node, parent)
    }

    // 然後再把 visiter 中不包括的屬性進行單獨處理 
    switch (node.type) {
      // first exec 執行最外層的 遍歷 節點下的 body
      case "Program":
        traverseArray(node.body, node);
        break;

      case "CallExpression":
        traverseArray(node.params, node)
        break;

      case "NumberLiteral":
      case "StringLiteral":
        break;

      default:
        throw new TypeError(node.type)
    }
  }

  traverseNode(ast, null)

}

執行他的時候，主線為 traverser -> traverseNode ->
ast 作為 node 參數傳入進去，這個函數的執行過程就進行了遞歸調用
第一次執行 methods 為 undefined 然後進入 switch 語句中
第一次的 ast type 是 Program 然後就將 ast 的 body 當作參數傳遞進去，然後 break; 掉
至此，函數主線已經執行完畢了
之後的執行流程則是對 ast.body 進行的一個偽遞歸或者叫嵌套調用，函數每次根據其傳入的 tree 參數，根據表達式，參數，去判斷是否生成新的 ast

值得一提的是，在生成 newAst 的時候
有類似這樣的語句
node._context = expression.arguments;
將傳入節點的_context 屬性指向當前對象下的某個屬性，達到引用的效果，這時，使用 visitor 遍歷語法數的時候，不管傳入的對象是什麼，因為已經在上層構建好了內存地址的引用關係，所以只需要給 parent._context 屬性添加只就可以了

最後的最後就是將生成的新 ast 生成我們的目標語言，這個沒什麼好說的，遞歸生成字符串就好了。

總結，看似簡單的小項目，如果自己去實現，不知道要考慮多少細節，所以說，前端深入之路，任重而道遠！