欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間：2022年04月16日 10:01:26   作者：zoomdong  
這篇文章主要為大家介紹了如何利用JS實現(xiàn)一個小型編譯器，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)或工作有一定的參考價值，需要的可以參考一下

本文內(nèi)容基于倉庫源碼進行學(xué)習(xí)

最近在研究一些構(gòu)建側(cè)的東西，在翻 babel 官網(wǎng)的時候看到了這樣一段話:

For an awesome tutorial on compilers, check out the-super-tiny-compiler, which also explains how Babel itself works on a high level.

出于學(xué)習(xí)的心態(tài)，去翻了一下這個倉庫源碼，以下是筆者的一些學(xué)習(xí)的記錄，希望看完之后能對你理解 babel 的工作原理有一些幫助~

前言

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

倉庫本身的例子是將一組 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 都會把編譯過程分成三個主要的過程: parse、transform 以及 code generate：

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

Parse

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

  • 詞法分析將源碼根據(jù)表達(dá)切分一個個的 tokens，tokens 是一組用來描述單獨語法的對象，可以是 numbers、labels、punctuation、operators 等
  • 語法分析則是將詞法分析生成的 tokens 進行重新編排得到一個叫做抽象語法 樹 (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 這個過程既可以基于當(dāng)前語言的風(fēng)格去修改 ast 也可以使用一種新的語言風(fēng)格。

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

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

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

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

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

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

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

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

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

Traversal(遍歷)

為了能處理所有的結(jié)點，我們可以用深度優(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 的頂結(jié)點開始
  • CallExpression (add) - Program 的第一個子元素
  • NumberLiteral (2) - CallExpression (add) 的第一個子元素
  • CallExpression (subtract) - CallExpression (add) 的第二個子元素
  • NumberLiteral (4) - CallExpression (subtract) 的第一個子元素
  • NumberLiteral (2) - CallExpression (subtract) 的第二個子元素

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

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

Visitors(訪問)

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

例如:

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

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

Code generate

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

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

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

代碼實現(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ù)組，然后將其轉(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é)點，返回一個新的 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 設(shè)置成當(dāng)前的 token.value
      // 因為左圓括號后的 token 一定是函數(shù)名稱
      const node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

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

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

      // 以 lisp 風(fēng)格的代碼來說: (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ù)將結(jié)點處理進 ast.body 中
   */
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

遍歷器(visitors)

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

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

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

const traverser = (ast, visitor) => {

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

  // 函數(shù)接收一個 node 以及其父結(jié)點作為參數(shù)
  // 這個結(jié)點會被傳入到 visitor 中相應(yīng)的處理函數(shù)那里
  const traverseNode = (node, parent) => {
    const method = visitor[node.type];
    if (method) {
      method(node, parent);
    }
    // 對不同的結(jié)點分開處理
    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);
}

轉(zhuǎn)換器(transformer)

轉(zhuǎn)換器配合上面的遍歷器來一起使用，它接收之前構(gòu)建好的 ast，然后將其和 visitor 一起傳入遍歷器中，從而得到一個全新的 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',
        }]
      }]
    }
  }
}

接下來我們可以這樣編寫對應(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) => {

      // 初始化一個 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 中也可以被當(dāng)成是聲明語句
        expression = {
          type: 'ExpressionStatement',
          expression,
        };
      }

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

  return newAst;
}

代碼生成器(code generator)

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

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

我們可以輸入前面的幾組測試?yán)樱鼙ＷC得到的結(jié)果是正確的。

總結(jié)

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

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

相關(guān)文章

最新評論