用JavaScript帶你體驗V8引擎解析標識符

来源:https://www.cnblogs.com/QH-Jimmy/archive/2019/08/08/11321974.html
-Advertisement-
Play Games

上一篇講了字元串的解析過程，這一篇來講講標識符(IDENTIFIER)的解析。 先上知識點，標識符的掃描分為快解析和慢解析，一旦出現Ascii編碼大於127的字元或者轉義字元，會進入慢解析，略微影響性能，所以最好不要用中文、特殊字元來做變數名(不過現在代碼壓縮後基本不會有這種情況了)。 每一位Jav ...


上一篇講了字元串的解析過程，這一篇來講講標識符(IDENTIFIER)的解析。

先上知識點，標識符的掃描分為快解析和慢解析，一旦出現Ascii編碼大於127的字元或者轉義字元，會進入慢解析，略微影響性能，所以最好不要用中文、特殊字元來做變數名(不過現在代碼壓縮後基本不會有這種情況了)。

 

每一位JavaScript的初學者在學習聲明一個變數時，都會遇到標識符這個概念，定義如下。

第一個字元，可以是任意Unicode字母（包括英文字母和其他語言的字母），以及美元符號（$）和下劃線（_）。 第二個字元及後面的字元，除了Unicode字母、美元符號和下劃線，還可以用數字0-9。

籠統來講，v8也是通過這個規則來處理標識符，下麵就來看看詳細的解析過程。

老規矩，代碼我丟github上面，接著前面一篇的內容，進行了一些整理，將文件分類，保證下載即可運行。

鏈接：https://github.com/pflhm2005/V8record/tree/master/JS

 

待解析字元如下。

var

目的就是解析這個var關鍵詞。

首先需要完善Token映射表，添加關於標識符的內容，如下。

const TokenToAsciiMapping = (c) => {
  return c === '(' ? 'Token::LPAREN' : 
  c == ')' ? 'Token::RPAREN' :
  // ...很多很多
  c == '"' ? 'Token::STRING' :
  c == '\'' ? 'Token::STRING' :
  // 標識符部分單獨抽離出一個方法判斷
  IsAsciiIdentifier(c) ? 'Token::IDENTIFIER' :
  // ...很多很多
  'Token::ILLEGAL'
};

在那個超長的三元表達式中添加一個標識符的判斷，由於標識符的合法字元較多，所以單獨抽離一個方法做判斷。

方法的邏輯只要符合定義就夠了，實現如下。

/**
 * 判斷給定字元(數字)是否在兩個字元的範圍內
 * C++通過static_cast同時處理了char和int類型 JS就比較坑了
 * 這個方法其實在C++超簡單的 然而用JS直接炸裂
 * @param {char} c 目標字元
 * @param {char} lower_limit 低位字元
 * @param {chat} higher_limit 高位字元
 */
export const IsInRange = (c, lower_limit, higher_limit) => {
  if(typeof lower_limit === 'string' && typeof higher_limit === 'string') {
    if(typeof c === 'string') c = c.charCodeAt();
    return (c - lower_limit.charCodeAt())
    <= (higher_limit.charCodeAt() - lower_limit.charCodeAt());
  } else {
    return (c - lower_limit) <= (higher_limit - lower_limit);
  }
}

/**
 * 將大寫字母轉換為小寫字母 JS沒有char、int這種嚴格類型 需要手動搞一下
 */
const AsciiAlphaToLower = (c) => { return String.fromCharCode(c | 0x20); }

/**
 * 數字字元判斷
 */
const IsDecimalDigit = (c) => {
  return IsInRange(c, '0', '9');
}

/**
 * 大小寫字母、數字
 */
const IsAlphaNumeric = (c) => {
  return IsInRange(AsciiAlphaToLower(c), 'a', 'z') || IsDecimalDigit(c);
}

/**
 * 判斷是否是合法標識符字元
 */
const IsAsciiIdentifier = (c) => {
  return IsAlphaNumeric(c) || c == '$' || c == '_';
}

v8內部定義了很多字元相關的方法，這些只是一部分。比較有意思的是那個大寫字母轉換為小寫，一般在JS中都是toLowerCase()一把梭，但是C++用的是位運算。

方法都比較簡單，可以看到，大小寫字母、數字、$、_都會認為是一個合法標識符。

得到一個Token::IDENTIFIER的初步標記後，會進入單個Token的解析，即Scanner::ScanSingleToken(翻上一篇)，在這裡，也需要添加一個處理標識符的方法，如下。

class Scanner {
  /**
   * 單個詞法的解析
   */
  ScanSingleToken() {
    let token = null;
    do {
      this.next().location.beg_pos = this.source_.buffer_cursor_ - 1;
      if(this.c0_ < kMaxAscii) {
        token = UnicodeToToken[this.c0_];
        switch(token) {
          /**
           * 在這裡添加標識符的case
           */
          case 'Token::IDENTIFIER':
            return ScanIdentifierOrKeyword();
          // ...
        } 
      }
      /**
       * 源碼中這裡處理一些特殊情況
       * 特殊情況就包括Ascii編碼過大的標識符 特殊情況暫不展開
       */
    } while(token === 'Token::WHITESPACE')
    return token;
  }
}

上一篇這裡只有Token::String，多加一個case就行。一般情況下，所有字元都是普通的字元，即Ascii編碼小於128。如果出現類似於中文這種特殊字元，會進入下麵的特殊情況處理，現在一般不會出現，這裡就不做展開了。

接下來就是實現標識符解析的方法，從名字可以看出，標識符分為變數、關鍵詞兩種類型，那麼還是需要再弄一個映射表來做類型快速判斷，先來完善上一篇留下的尾巴，字元類型映射表。

裡面其實還有一個映射表，叫character_scan_flag，也是對單個字元的類型判定，屬於一種可能性分類。

之前還以為這個表很麻煩，其實挺簡單的(假的，噁心了我一中午)。表的作用如上，通過一個字元，來判斷這個標識符可能是什麼東西，類型總共有6種情況，如下。

/**
 * 字元類型
 */
const kTerminatesLiteral = 1 << 0;
const kCannotBeKeyword = 1 << 1;
const kCannotBeKeywordStart = 1 << 2;
const kStringTerminator = 1 << 3;
const kIdentifierNeedsSlowPath = 1 << 4;
const kMultilineCommentCharacterNeedsSlowPath = 1 << 5;

這6個枚舉值分別表示：

  • 標識符的結束標記，比如')'、'}'等符號都代表這個標識符沒了
  • 非關鍵詞標記，比如一個標識符包含'z'字元，就不可能是一個關鍵字
  • 非關鍵詞首字元標記，比如varrr的首字元是'v'，這個標識符可能是關鍵詞(實際上並不是)
  • 字元串結束標記，上一篇有提到，單雙引號、換行等都可能代表字元串結束
  • 標識符慢解析標記，一旦標識符出現轉義、Ascii編碼大於127的值，標記會被激活
  • 多行註釋標記，參考上面那個代碼的註釋

始終需要記住，這隻是一種可能性類型推斷，並不是斷言，只能用於快速跳過某些流程。

有了標記和對應定義，下麵來實現這個字元類型推斷映射表，如下。

const GetScanFlags = (c) => {
  (!IsAsciiIdentifier(c) ? kTerminatesLiteral : 0) |
  (IsAsciiIdentifier(c) && !CanBeKeywordCharacter(c)) ? kCannotBeKeyword : 0 |
  (IsKeywordStart(c) ? kCannotBeKeywordStart : 0) |
  ((c === '\'' || c === '"' || c === '\n' || c === '\r' || c === '\\') ? kStringTerminator : 0) |
  (c === '\\' ? kIdentifierNeedsSlowPath : 0) |
  (c === '\n' || c === '\r' || c === '*' ? kMultilineCommentCharacterNeedsSlowPath : 0)
}

// UnicodeToAsciiMapping下標代表字元對應的Ascii編碼 上一篇有講
const character_scan_flags = UnicodeToAsciiMapping.map(c => GetScanFlags(c));

對照定義，上面的方法基本上不用解釋了，用到了我前面講過的一個技巧bitmap(文盲不懂專業術語，難怪阿裡一面就掛了)。由於是按照C++源碼寫的，上述部分工具方法還是需要挨個實現。源碼用的巨集，寫起來一把梭，用JS還是挺繁瑣的，具體代碼我放github了。

 

有了這個映射表，後面很多地方就很方便了，現在來實現標識符的解析方法。

實現之前，來列舉一下可能出現的標識符：var、vars、avr、1ab、{ '\a': 1 }、吉米(\u5409\u7c73)，這些標識符有些合法有些不合法，但是都會進入解析階段。所以總的來說，方法首先保證可以處理上述所有情況。

對於數字開頭的標識符，其實在case階段就被攔截了，雖然說數字1也會出現在一個IDENTIFIER中，但是1會首先被優先解析成'Token::Number'，有對應的方法處理這個類型，如下。

case 'Token::STRING':
  return this.ScanString();
// 數字開頭
case 'Token::NUMBER':
  return ScanNumber(false);
case 'Token::IDENTIFIER':
  return ScanIdentifierOrKeyword();

所以1ab這種情況不用考慮，實現方法如下。

Scanner::ScanIdentifierOrKeyword() {
  this.next().literal_chars.Start();
  return this.ScanIdentifierOrKeywordInner();
}
Scanner::ScanIdentifierOrKeywordInner() {
  /**
   * 兩個布爾類型的flag 
   * 一個標記轉義字元 一個標記關鍵詞
   */
  let escaped = false;
  let can_be_keyword = true;
  if(this.c0_ < kMaxAscii) {
    // 轉義字元以'\'字元開頭
    if(this.c0_ !== '\\') {
      let scan_flags = character_scan_flags[this.c0_];
      // 這個地方比較迷 沒看懂
      scan_flags >>= 1;
      this.AddLiteralChar(this.c0_);
      this.AdvanceUntil((c0) => {
        // 當某個字元的Ascii編碼大於127 進入慢解析
        if(c0 > kMaxAscii) {
          scan_flags |= kIdentifierNeedsSlowPath;
          return true;
        }
        // 疊加每個字元的bitmap
        let char_flags = character_scan_flags[c0];
        scan_flags |= char_flags;
        // 用bitmap識別結束標記
        if(TerminatesLiteral(char_flags)) {
          return true;
        } else {
          this.AddLiteralChar(c0);
          return false;
        }
      });
      // 基本上都是進這裡 快分支
      if(!IdentifierNeedsSlowPath(scan_flags)) {
        if(!CanBeKeyword(scan_flags)) return 'Token::IDENTIFIER';
        // 源碼返回一個新的vector容器 這裡簡單處理成一個字元串
        let chars = this.next().literal_chars.one_byte_literal();
        return this.KeywordOrIdentifierToken(chars, chars.length);
      }
      can_be_keyword = CanBeKeyword(scan_flags);
    } else {
      escaped = true;
      let c = this.ScanIdentifierUnicodeEscape();
      // 合法變數以大小寫字母_開頭
      if(c === '\\' || !IsIdentifierStart(c)) return 'Token::ILLEGAL';
      this.AddLiteralChar(c);
      can_be_keyword = CharCanBeKeyword(c);
    }
  }
  // 邏輯同上 進這裡代表首字元Ascii編碼就過大
  return ScanIdentifierOrKeywordInnerSlow(escaped, can_be_keyword);
}

感覺C++的類方法實現的寫法看起來很舒服，博客里也這麼寫了，希望JavaScript什麼時候也借鑒一下，貌似::在JS里目前還不是一個運算符，總之真香。

首先可以發現，標識符的解析也用到了Literal類，之前說這是用了字元串解析並不准確，因此我修改了AdvanceUntil方法，將callback作為參數傳入。啟動類後，掃描邏輯如下。

  • 一旦字元出現Ascii編碼大於127或者轉義符號，扔到慢解析方法中
  • 對所有字元進行逐個遍歷，方式類似於上篇的字元串解析，結束標記略有不同
  • 一般情況下不用慢解析，根據bitmap中的kCannotBeKeyword快速判斷返回變數還是進入關鍵詞解析分支

v8中字元相關的工具方法就單獨搞了一個cpp文件，裡面方法非常多，後續如果是把v8全部翻譯過來估計也要分好多文件了，先這樣吧。

先不管慢解析了，大部分情況下也不會用中文做變數，類似於zzz、jjj的變數會快速跳出，標記為"Token::IDENTIFIER"。而可能是關鍵詞的標識符，比如上面列舉的var、vars、avr，由於或多或少的具有一些關鍵詞特征，會深入再次解析。

需要說的是，從一個JavaScript使用者的角度看，關鍵詞的識別隻需要對字元串做嚴格對等比較就行了，比如長度3，字元順序依次是v、a、r，那麼必定是關鍵詞var。

但是v8的實現比較迷，用上了Hash，既然是v8體驗文章，那麼就按照源碼的邏輯實現上面的KeywordOrIdentifierToken方法。

// 跳到另外一個文件里實現
Scanner::KeywordOrIdentifierToken(str, len) {
  return PerfectKeywordHash.GetToken(str, len);
}
/**
 * 特殊const就放這裡算了
 */
const MIN_WORD_LENGTH = 2;
const MAX_WORD_LENGTH = 10;

class PerfectKeywordHash {
  static GetToken(str, len) {
    if(IsInRange(len, MIN_WORD_LENGTH, MAX_WORD_LENGTH)) {
      let key = PerfectKeywordHash.Hash(str, len) & 0x3f;
      if(len === kPerfectKeywordLengthTable[key]) {
        const s = kPerfectKeywordHashTable[key].name;
        let l = s.length;
        let i = -1;
        /**
         * C++可以直接操作指針 JS只能搞變數了
         * 做字元嚴格校對 形如avr會被識別為變數
         */
        while(i++ !== l) {
          if(s[i] !== str[i]) return 'Token::IDENTIFIER';
        }
        return kPerfectKeywordHashTable[key].value;
      }
    }
    return 'Token::IDENTIFIER';
  }
}

總體邏輯如上所示，關鍵詞的長度目前是2-10，所以根據長度先篩一波，再v8根據傳入的字元串算出了一個hash值，然後根據這個值從映射表找出對應的特征，對兩者進行嚴格對對比，來判定這個標識符是不是一個關鍵詞。

涉及1個hash演算法和2個映射表，這裡把hash演算法給出來，映射表實在是繁瑣，有興趣去github看吧。

/**
 * asso_values保存了Ascii編碼0-127的映射
 * 所有關鍵詞字元都有對應的hash值 而非關鍵詞字元都是56 比如j、k、z等等
 * 通過運算返回一個整形
 */
static Hash(str, len) {
  const asso_values = [
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
    56, 8,  0,  6,  0,  0,  9,  9,  9,  0,  56, 56, 34, 41, 0,  3,
    6,  56, 19, 10, 13, 16, 39, 26, 37, 36, 56, 56, 56, 56, 56, 56,
  ];
  return len + asso_values[str[1].charCodeAt()] + asso_values[str[0].charCodeAt()];
}

可以看到，hash方法的內部也有一個映射表，每一個關鍵字元都有對應的hash值，通過前兩個字元進行運算(最短的關鍵詞就是2個字元，並且)，得到一個hash值，將這個值套到另外的table得到其理論上的長度，長度一致再進行嚴格比對。

這個方法個人感覺有一些微妙，len主要是做一個修正，因為前兩個字元一樣的關鍵詞還是蠻多的，比如說case、catch，delete、default等等，但是長度不一樣，加上len可以區分。如果有一天出現前兩個字元一樣，且長度也一樣的關鍵詞，這個hash演算法肯定要修改了，反正也不關我事咯。

經過這一系列的處理，標識符的解析算是完成了，代碼可以github上面下載，然後修改test文件裡面傳入的參數就能看到輸出。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • JS變數、作用域
    JavaScript變數和作用域的學習筆記，包括變數的含義、作用，機制，以及作用域的機制、JS預解析等 ...
  • page分頁問題，根據頁碼獲取對應頁面的數據，介面調用
    import axios from '@/libs/api.request' const MODULE_URL = '/log'; export const actionLogData = (params, cb) => { axios.request({ url: `${MODULE_URL}/a ...
  • JQuery jquerysessionjs插件使用介紹
    jquerysessionjs插件使用介紹 by:授客 QQ：1033553122 JQuery-3.2.1.min.j 下載地址： https://gitee.com/ishouke/front_end_plugin/blob/master/jquery-3.2.1.min.js jqueryse ...
  • HTML 表單
    <form>元素： <input>元素： 常用屬性： type 文本框類型 name 指定了name的欄位才會被提交（不能用id代替name屬性） placeholder 占位符 value 輸入框中的文本 autofocus 自動聚焦 disabled 禁用 readonly 只讀 require ...
  • 關於獲取input標簽屬性的獲取以及更改，此處用到的是readonly屬性
    一開始，我使用的是Jquery框架中的$.("#input").readOnly,發現取出的值為undefined，不知道是不是jQuery中不支持獲取標簽屬性的函數， 然後就使用了原生的document.getElementById("input1").readOnly並且可以更改它的值以及取值， ...
  • JavaScript之基本語句
    寫在前面：前面的內容記錄了JavaScript的一些基本概念，本次主要講解一下JS中常用的語句。 和大多數其他編程語言一樣，JS也主要包括：選擇、迴圈、錯誤檢測、函數等。JS的語句基本是由值、運算符、表達式、關鍵字和註釋構成，但並不是語句一定包含所有以上要素。 電腦程式一般是指能夠被電腦執行的一 ...
  • swiper 輪播中常用的效果，持續更新
    swiper一款非常好用的輪播插件，支持移動端和PC端，用過很多次了，這次簡單的總結一下。方便以後查找使用，說明一下，下麵的例子是基於swiper 4.0+版本的，如果你是其他的版本，請自行前往官網查看 至於為什麼使用swiper，而不是自己手寫，請看下麵官網的截圖： 開個玩笑，說白了，就是這個確實 ...
  • js 對 只包含簡單類型數據的對象 為元素 組成的數組 進行去重
    /** * 對於由簡單類型數據組成的對象為元素組成的數組進行去重操作 * @params {Array} 需要去重的對象數組 * @returns {Array} 去重後的對象數組 */ function distinct(sourceArray) { var resultArray = []; v ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類