基于JS實現(xiàn)一個小型編譯器

更新時間：2022年04月16日 10:01:26 作者：zoomdong

這篇文章主要為大家介紹了如何利用JS實現(xiàn)一個小型編譯器，文中的示例代碼講解詳細，對我們學習或工作有一定的參考價值，需要的可以參考一下

前言

the-super-tiny-compiler 是一個代碼行數(shù)只有不到 200 行的超級小型的 compiler，但通過這個 compiler 能學習到最基礎的 compile 原理，包括 babel 也是基于這樣的原理來進行開發(fā)的。

倉庫本身的例子是將一組 lisp 風格的函數(shù)語法編譯成了 C 風格的函數(shù)語法，舉例子來說:

LISP 風格	C 風格
2+2	(add 2 2)	add(2,2)
4-2	(subtract 4 2)	substract(4, 2)
2 + (4 - 2)	(add 2 (substract 4 2))	add(2, (substract(4, 2)))

這就大概是這次 compiler 需要完成的事情，可能看上去語法不是很完整，但是也能夠演示現(xiàn)代編譯器的主要部分思想了。

大多數(shù)的 Compilers 都會把編譯過程分成三個主要的過程: parse、transform 以及 code generate：

parse 主要是將源碼轉換成一種更抽象的代碼表達
transform 則是將上面抽象的表達進行任意 compiler 想進行的操作
code generate 將 transform 處理之后的代碼生成一種新的代碼

Parse

parse 主要分為兩個步驟: 詞法分析以及語法分析。

詞法分析將源碼根據(jù)表達切分一個個的 tokens，tokens 是一組用來描述單獨語法的對象，可以是 numbers、labels、punctuation、operators 等
語法分析則是將詞法分析生成的 tokens 進行重新編排得到一個叫做抽象語法樹 (AST)的結構，AST 是一種易于使用且能展示完整信息的嵌套樹狀結構。

例如前面提到的 add 2 (subtract 4 2) 表達式被詞法分析處理之后生成的 tokens 大概是:

[
  { 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',
            }
           ]
         }]
      }]
}

Transform

transform 主要就是拿到 parse 得到的抽象語法樹，并基于此做出一些修改。tranform 這個過程既可以基于當前語言的風格去修改 ast 也可以使用一種新的語言風格。

下面基于前面的 ast 結構來展示 transform 這個過程的工作流程。

可以看到，ast 里面的元素看起來都很相似，這些元素組成了 ast 的子結點，這些子結點的數(shù)據(jù)結構類型描述了代碼中的一個單獨的部分(例如變量、聲明語句，表達式等等)。

例如上面提到的類型是 NumberLiteral 的節(jié)點:

{
  type: 'NumberLiteral',
  value: '2',
}

或者更復雜一點的子節(jié)點類型:

{
    type: 'CallExpression',
    name: 'substract',
    params: [...nested nodes here ...],
}

在 transfrom 這個過程中，我們可以通過增/刪/改來操作抽象語法樹結點，或者可以直接基于當前的抽象語法樹創(chuàng)建一個新的出來。

既然這里我們的目標是將輸入的代碼轉換成一種新的語言風格的代碼(Lisp -> C)，所以這里會創(chuàng)建一個針對新語言的全新 AST 出來。

因此這里我們需要明確一下修改 AST 的操作:

Traversal(遍歷)

為了能處理所有的結點，我們可以用深度優(yōu)先搜索對其進行遍歷:

{
  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'
      }]
    }]
  }]
}

遍歷流程是這樣的:

Program - 從 AST 的頂結點開始
CallExpression (add) - Program 的第一個子元素
NumberLiteral (2) - CallExpression (add) 的第一個子元素
CallExpression (subtract) - CallExpression (add) 的第二個子元素
NumberLiteral (4) - CallExpression (subtract) 的第一個子元素
NumberLiteral (2) - CallExpression (subtract) 的第二個子元素

如果直接在 ast 內部操作而不是產(chǎn)生一個新的 ast，可能就需要介紹所有的種類的抽象。但目前來看，訪問所有結點的方法已經(jīng)足夠了。

訪問(visiting) 這個詞代表一種在對象結構內對元素進行操作的模式。

Visitors(訪問)

這里我們可以創(chuàng)建一個 visitor 對象，這個對象包括一些方法用于接收不同的結點。

例如:

var visitor = {
  NumberLiteral() {},
  CallExpression() {}
};

因此當我們遍歷 ast 的時候，如果匹配到了對應 type 的結點，可以調用 visitor 中的方法來處理。

Code generate

Compiler 的最后一個階段就是 generate, 這個階段做的事情可能會和 transformation 重疊，但是代碼生成最主要的部分還是根據(jù) AST 來輸出代碼。

Generate 有幾種不同的工作方式，有些 Compilers 會重用之前生成的 token，有些則會創(chuàng)建獨立的代碼表示，以便于線性輸出代碼，但接下來我們還是著重于使用之前生成好的 AST。

我們的生成器需要知道如何打印 AST 中的所有類型結點，然后遞歸調用自身，知道所有的代碼都被打印到一個很長的字符串中。

代碼實現(xiàn)

以上就是 Compiler 所有的部分了，但并不是所有的 Compiler 都是這樣，不同的 compiler 目的不同，所以也可能需要不同的步驟。

接下來就開始代碼的編寫:

詞法分析器(tokenizer)

按照前面的理論分析，我們一步先進行 parser 這個階段里面的詞法分析器(tokenizer)。

這個函數(shù)接收一個字符串，然后將其分割成由 token 組成的數(shù)組:

ex:

(add 2 (substract 4 2)) => [{ type: 'paren', value: '('}, ...]

因此可以編寫這樣的一個函數(shù):

const tokenizer = (input) => {
  const tokens = [];
  let current = 0;
  while (current < input.length) {
    let char = input[current];
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      })

      current++;
      continue;
    }

    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      })
      current ++;
      continue;
    }

    // 空格目前不需要處理
    if (/\s/.test(char)) {
      current++;
      continue;
    }

    // 處理數(shù)字
    if (/[0-9]/.test(char)) {
      let value = '';
      // 一直遍歷直到遇到非數(shù)字的字符
      while (/[0-9]/.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'number',
        value,
      })
      continue;
    }

    // 處理字符串
    if(/[a-z]/i.test(char)) {
      let value = '';

      while(/[a-z]/i.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'name',
        value,
      });

      continue;
    }

    // 如果存在匹配不上的 token 就拋錯
    throw new Error(`Unknown token: ${char}`);
  }
  return tokens;
}

語法分析器(parser)

詞法分析器接收語法分析得到的 token 數(shù)組，然后將其轉換成 AST 結構。

例如:

[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }

const parser = (tokens) => {
  let current = 0;
  
  const walk = () => {
    const token = tokens[current];
    // 如果是 number 類型的結點，返回一個新的 ast 節(jié)點即可
    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }

    // 接下來檢查 CallExpression 類型，先從左圓括號開始
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 跳過左圓括號
      token = tokens[++current];
      // 首先會創(chuàng)建一個 CallExpression 的根節(jié)點，然后 name 設置成當前的 token.value
      // 因為左圓括號后的 token 一定是函數(shù)名稱
      const node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 這里再跳一次函數(shù)名稱
      token = tokens[++current];

      // 通過循環(huán)遍歷接下來的每個 token，直到遇到右圓括號
      // 這些 token 會成為 `CallExpression` 的  `params`

      // 以 lisp 風格的代碼來說: (add 2 (substract 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: ')'        }  <<< 右圓括號
        ]
        遇到嵌套的 CallExpressions 的時候，會通過 walk 函數(shù)來處理
       *
       */
      while (
        token.type !== 'paren' ||
        (token.value !== ')' && token.type === 'paren')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      current++;
      return node;
    }
    throw new Error(`Unknown token type: ${token.type}`);
  }

  const ast = {
    type: 'Program',
    body: [],
  }

  /**
   * 使用遞歸函數(shù)將結點處理進 ast.body 中
   */
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

遍歷器(visitors)

通過語法分析得到 ast 之后，接下來需要一個遍歷器 (visitors) 去遍歷結點。然后當遇到某個類型的結點的時候，可以調用 visitors 中對應的類型處理函數(shù):

traverse(ast, {
  Program(node, parent) {
    // ...
  },
  
  CallExpression(node, parent) {
    // ...
  },
  
  NumberLiteral(node, parent) {
    // ...
  },
});

因此我們的代碼可以這樣寫:

const traverser = (ast, visitor) => {

  // 用于對數(shù)組中的每個元素都調用 traverseNode 函數(shù)
  const traverseArray = (array, parent) => {
    array.forEach((child) => {
      traverseNode(child, parent);
    });
  }

  // 函數(shù)接收一個 node 以及其父結點作為參數(shù)
  // 這個結點會被傳入到 visitor 中相應的處理函數(shù)那里
  const traverseNode = (node, parent) => {
    const method = visitor[node.type];
    if (method) {
      method(node, parent);
    }
    // 對不同的結點分開處理
    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;
        
      // 這種情況下就沒有子節(jié)點了，直接 break 出去
      case 'NumberLiteral':
        break;
      
      default:
        throw new Error(`Unknown node type: ${node.type}`);
    }
  }

  traverseNode(ast, null);
}

轉換器(transformer)

轉換器配合上面的遍歷器來一起使用，它接收之前構建好的 ast，然后將其和 visitor 一起傳入遍歷器中，從而得到一個全新的 AST 出來。

原始的 AST 結構為( add 2 (subtract 4 2) ):

{
  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 結構為( add(2, subtract(4, 2)) ):

{
  type: 'Program',
  body: [{
    type: 'ExpressionStatement',
    expression: {
      type: 'CallExpression',
      callee: {
        type: 'Identifier',
        name: 'add',
      },
      arguments: [{
        type: 'NumberLiteral',
        value: '2',
      }, {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: 'subtract',
        },
        arguments: [{
          type: 'NumberLiteral',
          value: '4',
        }, {
          type: 'NumberLiteral',
          value: '2',
        }]
      }]
    }
  }
}

接下來我們可以這樣編寫對應的轉換器代碼:

const transformer = (ast) => {
  const newAst = {
    type: 'Program',
    body: [],
  }

  ast._context = newAst.body;

  traverser(ast, {
    // 處理 NumberLiteral 類型
    NumberLiteral: (node, parent) => {
      parent._context.push({
        type: 'NumberLiteral',
        value: node.value,
      });
    },

    // 處理 CallExpression 類型
    CallExpression: (node, parent) => {

      // 初始化一個 CallExpression 的新節(jié)點
      // 里面放個嵌套的 Identifier 節(jié)點
      const expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: [],
      };

      node._context = expression.arguments;

      // 看看父節(jié)點是不是 CallExpression
      if (parent.type !== 'CallExpression') {

        // 如果不是的話，就將 CallExpression 節(jié)點包在一個叫 `ExpressionStatement` 的語句節(jié)點里
        // 這么做是因為 top level 的 CallExpression 在 JavaScript 中也可以被當成是聲明語句
        expression = {
          type: 'ExpressionStatement',
          expression,
        };
      }

      // 最后我們把 CallExpression 放入父結點的 context 中
      parent._context.push(expression);
    }
  });

  return newAst;
}

代碼生成器(code generator)

代碼生成器同樣是個遞歸函數(shù)，最后會將 AST 中的每個結點打印到一個大的字符串中:

const codeGenerator = (node) => {
  switch (node.type) {
    // 如果是 Program，則會遍歷 'body' 屬性中的每個結點
    // 并且對這些結點進行遞歸 codeGenerator,再把結果打印進新的一行里面
    case 'Program':
      return node.body.map(codeGenerator).join('\n');
    
    // 對于 ExpressionStatement 對 expression 屬性進行遞歸調用，并加個分號
    case 'ExpressionStatement':
      return `${codeGenerator(node.expression)};`;
    
    // 對于 CallExpression 對 callee 屬性進行遞歸調用，接著加上(括號
    // 然后對 arguments 屬性進行遞歸調用，并加上)括號
    case 'CallExpression':
      return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;

    // 對于 Identifier,直接返回 name
    case 'Identifier':
      return node.name;
    
    // 對于 NumberLiteral,直接返回 value
    case 'NumberLiteral':
      return node.value;
    
    default:
      throw new Error(`Unknown node type: ${node.type}`);
  }
}

編譯器(Compiler)

到這一步，基本上所有的流程就已經(jīng)完成了，我們可以創(chuàng)建一個 compiler 函數(shù)，通過調用上面的函數(shù)就可以完成整個 compiler 的工作了:

input => tokenizer => tokens
tokens => parser => ast
ast => transformer => newAst
newAst => generator => output

代碼只需要以下簡單幾步即可:

const compiler = (input) => {
  const tokens = tokenizer(input);
  const ast = parser(tokens);
  const newAst = transformer(ast);
  
  return codeGenerator(newAst);
}

我們可以輸入前面的幾組測試例子，能保證得到的結果是正確的。

總結

至此一個 tiny-compiler 就被造出來了，babel 的編譯流程也是基于此來完成，因為 babel 本身是個 source to source 的 compiler，整個流程也是分為 parser -> transform -> code generate 這三個步驟完成，具體可以參考

以上就是基于JS實現(xiàn)一個小型編譯器的詳細內容，更多關于JS編譯器的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

JS
編譯器

js圖片滾動效果時間可隨意設定當鼠標移上去時停止
這篇文章主要介紹了js圖片滾動效果時間可隨意設定當鼠標移上去時停止，需要的朋友可以參考下
2014-06-06
js實現(xiàn)淘寶首頁的banner欄效果
這篇文章主要為大家詳細介紹了js實現(xiàn)淘寶首頁的banner欄效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-11-11
微信小程序單選框自定義賦值
這篇文章主要介紹了微信小程序單選框如何自定義賦值，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-05-05
uniapp使用mui-player插件播放m3u8/flv視頻流示例代碼
在小程序里播放視頻是很常見的功能,下面這篇文章主要給大家介紹了關于uniapp使用mui-player插件播放m3u8/flv視頻流的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
2023-06-06
js print打印網(wǎng)頁指定區(qū)域內容的簡單實例
下面小編就為大家?guī)硪黄猨s print打印網(wǎng)頁指定區(qū)域內容的簡單實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2016-11-11
Javascript 詳解封裝from表單數(shù)據(jù)為json串進行ajax提交
這篇文章主要介紹了Javascript 詳解封裝from表單數(shù)據(jù)為json串進行ajax提交的相關資料,需要的朋友可以參考下
2017-03-03
微信小程序自定義頂部導航欄并適配不同機型實例詳解
這篇文章主要為大家介紹了微信小程序開發(fā)自定義頂部導航欄并適配不同機型的實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
2023-12-12
基于javascript處理nginx請求過程詳解
這篇文章主要介紹了基于javascript處理nginx請求過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-07-07
詳解js如何優(yōu)雅處理后端返回的單元格數(shù)據(jù)
這篇文章主要為大家詳細介紹了JavaScript如何優(yōu)雅處理后端返回的單元格數(shù)據(jù),文中的示例代碼講解詳細,有需要的小伙伴可以跟隨小編一起學習一下
2023-10-10
SyntaxHighlighter代碼加色使用方法
原名：SyntaxHighlighter，是一款用于web頁面的代碼著色工具，可以用來著色多種語言，可以是HTML,CSS,Javascript,還可以是C,JAVA等編程語言。最早見于Yahoo的YUI，當時還屬于自由軟件，最近打開官方網(wǎng)站發(fā)現(xiàn)已被goolge收編。
2008-09-09