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

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

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

前言

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

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

LISP 風(fēng)格	C 風(fēng)格
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 都會(huì)把編譯過程分成三個(gè)主要的過程: parse、transform 以及 code generate：

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

Parse

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

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

例如前面提到的 add 2 (subtract 4 2) 表達(dá)式被詞法分析處理之后生成的 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 結(jié)構(gò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',
            }
           ]
         }]
      }]
}

Transform

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

下面基于前面的 ast 結(jié)構(gòu)來展示 transform 這個(gè)過程的工作流程。

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

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

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

或者更復(fù)雜一點(diǎn)的子節(jié)點(diǎn)類型:

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

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

既然這里我們的目標(biāo)是將輸入的代碼轉(zhuǎn)換成一種新的語言風(fēng)格的代碼(Lisp -> C)，所以這里會(huì)創(chuàng)建一個(gè)針對(duì)新語言的全新 AST 出來。

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

Traversal(遍歷)

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

{
  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 的頂結(jié)點(diǎn)開始
CallExpression (add) - Program 的第一個(gè)子元素
NumberLiteral (2) - CallExpression (add) 的第一個(gè)子元素
CallExpression (subtract) - CallExpression (add) 的第二個(gè)子元素
NumberLiteral (4) - CallExpression (subtract) 的第一個(gè)子元素
NumberLiteral (2) - CallExpression (subtract) 的第二個(gè)子元素

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

訪問(visiting) 這個(gè)詞代表一種在對(duì)象結(jié)構(gòu)內(nèi)對(duì)元素進(jìn)行操作的模式。

Visitors(訪問)

這里我們可以創(chuàng)建一個(gè) visitor 對(duì)象，這個(gè)對(duì)象包括一些方法用于接收不同的結(jié)點(diǎn)。

例如:

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

因此當(dāng)我們遍歷 ast 的時(shí)候，如果匹配到了對(duì)應(yīng) type 的結(jié)點(diǎn)，可以調(diào)用 visitor 中的方法來處理。

Code generate

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

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

我們的生成器需要知道如何打印 AST 中的所有類型結(jié)點(diǎn)，然后遞歸調(diào)用自身，知道所有的代碼都被打印到一個(gè)很長(zhǎng)的字符串中。

代碼實(shí)現(xiàn)

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

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

詞法分析器(tokenizer)

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

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

ex:

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

因此可以編寫這樣的一個(gè)函數(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 就拋錯(cuò)
    throw new Error(`Unknown token: ${char}`);
  }
  return tokens;
}

語法分析器(parser)

詞法分析器接收語法分析得到的 token 數(shù)組，然后將其轉(zhuǎn)換成 AST 結(jié)構(gòu)。

例如:

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

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

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

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

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

      // 以 lisp 風(fēng)格的代碼來說: (add 2 (substract 4 2))
      /**
       * token 中會(huì)有很多圓括號(hào)
       * [
          { 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: ')'        }, <<< 右圓括號(hào)
          { type: 'paren',  value: ')'        }  <<< 右圓括號(hào)
        ]
        遇到嵌套的 CallExpressions 的時(shí)候，會(huì)通過 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ù)將結(jié)點(diǎn)處理進(jìn) ast.body 中
   */
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

遍歷器(visitors)

通過語法分析得到 ast 之后，接下來需要一個(gè)遍歷器 (visitors) 去遍歷結(jié)點(diǎn)。然后當(dāng)遇到某個(gè)類型的結(jié)點(diǎn)的時(shí)候，可以調(diào)用 visitors 中對(duì)應(yīng)的類型處理函數(shù):

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

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

const traverser = (ast, visitor) => {

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

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

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

  traverseNode(ast, null);
}

轉(zhuǎn)換器(transformer)

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

原始的 AST 結(jié)構(gòu)為( 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'
      }]
    }]
  }]
}

轉(zhuǎn)換之后生成的 AST 結(jié)構(gòu)為( 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',
        }]
      }]
    }
  }
}

接下來我們可以這樣編寫對(duì)應(yīng)的轉(zhuǎn)換器代碼:

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) => {

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

      node._context = expression.arguments;

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

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

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

  return newAst;
}

代碼生成器(code generator)

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

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

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

編譯器(Compiler)

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

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

代碼只需要以下簡(jiǎn)單幾步即可:

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

我們可以輸入前面的幾組測(cè)試?yán)?，能保證得到的結(jié)果是正確的。

總結(jié)

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

以上就是基于JS實(shí)現(xiàn)一個(gè)小型編譯器的詳細(xì)內(nèi)容，更多關(guān)于JS編譯器的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: