如何編寫簡單的parser（基礎篇）

Barry_Ng 發布于2019-08-23 14:53 / 2770人閱讀

摘要：在這里，詞法解析器應用的規則即為詞匯語法的定義，語法解釋器應用的規則即為表達式語句聲明和函數等的定義。如何編寫簡單的實踐篇

什么是parser？

簡單的說，parser的工作即是將代碼片段轉換成計算機可讀的數據結構的過程。這個“計算機可讀的數據結構”更專業的說法是“抽象語法樹（abstract syntax tree）”，簡稱AST。AST是代碼片段具體語義的抽象表達，它不包含該段代碼的所有細節，比如縮進、換行這些細節，所以，我們可以使用parser轉換出AST，卻不能使用AST還原出“原”代碼，當然，可以還原出語義一致的代碼，就如同將ES6語法的js代碼轉換成ES5的代碼。

parser的結構

一般來說，一個parser會由兩部分組成：

詞法解析器（lexer/scanner/tokenizer）

對應語法的解釋器（parser）

在解釋某段代碼的時候，先由詞法解釋器將代碼段轉化成一個一個的詞組流（token），再交由解釋器對詞組流進行語法解釋，轉化為對應語法的抽象解釋，即是AST了。

為了讓大家更清楚的理解parser兩部分的工作順序，我們通過一個例子來進行說明：

437 + 734

在parser解析如上的計算表達式時，詞法解析器首先依次掃描到“4”、“3”、“7”直到一個空白符，這時，詞法解析器便將之前掃描到的數字組成一個類型為“NUM”的詞組（token）；接下來，詞法解析器繼續向下掃描，掃描到了一個“+”，對應輸出一個類型為“PLUS”的詞組（token）；最后，掃描“7”、“3”、“4”輸出另一個類型為“NUM”的詞組（token）。

語法解釋器在拿到詞法解析器輸出的詞組流后，根據詞組流的“NUM”，“PLUS”，“NUM”的排列順序，解析成為加法表達式。

由上的例子我們可以看出，詞法解析器根據一定的規則對字符串進行解析并輸出為詞組（token），具體表現為連續不斷的數字組合（“4”、“3”、“7”和“7”、“3”、“4”）即代表了數字類型的詞組；語法解釋器同樣根據一定的規則對詞組的組合進行解析，并輸出對應的表達式或語句。在這里，詞法解析器應用的規則即為詞匯語法（Lexical Grammar）的定義，語法解釋器應用的規則即為表達式（Expressions）、語句（Statements）、聲明（Declarations）和函數（Functions）等的定義。

ECMAScript標準

看到這里大家可能會感覺到奇怪，為什么講parser講的好好的，又跑到ECMAScript標準上來了呢？因為以上提到的詞匯語法（Lexical Grammar）、表達式（Expressions）、語句（Statements）、聲明（Declarations）和函數（Functions）等都是ECMAScript標準中的所定義的，這其實也是ECMAScript標準的作用之一，即定義JavaScript的標準語法。

詞匯詞法（Lexical Grammar）

ECMAScript的詞匯詞法規定了JavaScript中的基礎語法，比如哪些字符代表了空白（White Space），哪些字符代表了一行終止（Line Terminators），哪些字符的組合代表了注釋（Comments）等。具體的規定說明，可以在ECMAScript標準11章中找到。

這里我們不仔細研讀每個語法的定義，只需知道詞法解析器（lexer）判讀詞組（token）的依據來源于此即可，為了讓大家有一定的了解，這里，我們拿上面例子中的數字字面量（Numeric Literals）來進行說明：
ECMAScript標準中，對數字字面量的定義如下：

該定義需要自上向下解讀：

首先，規則定義了數字字面量（Numeric Literal）可以是十進制字面量（Decimal Literal）、二進制整數字面量（Binary Integer Literal）、八進制整數字面量（Octal Integer Literal）、十六進制整數字面量（Hex Integer Literal）；

在我們的例子中，我們只關心十進制的字面量，所以，接下來，規則定義十進制字面量（Decimal Literal）可以是包含小數點與不包含小數點的組合，這里我們只需關注不包含小數點的定義，即十進制整數字面量（Decimal Integer Literal） + 可選的指數部分（Exponent Part）；

最后，規則定義十進制整數字母量由非零數字（Non Zero Digit）+ 十進制數字（Decimal Digit）或十進制數字組（Decimal Digits）組成，非零數字是由1~9的數字組成，十進制數字是由0~9組成。

將上面的定義重新整合后，就能得到我們需要的數字字面量的定義規則：

非零數字（1~9）+十進制數字組（0~9）

需要注意的是，這是簡化版的數字字面量定義，完整版的需要加上以上規則中的所有分支條件。

表達式（Expressions）、語句（Statements）

ECMAScript標準12~13章包含了表達式和語句的相關定義，之前由詞法解析器（lexer）處理后生成的詞組流（token）交由語法解釋器（parser）處理的主要內容，即是處理詞組流構成的表達式與語句。在這里，我們需要稍加明確一下表達式與語句之間的不同與關系：

首先，語句包含表達式，大部分語句是由關鍵字+表達式或語句組成，而表達式則是由字面量（Literal）、標識符（Identifier）、符號（Punctuators）等低一級的詞組組成；

其次，表達式一般來講會產生一個值，而語句不總有值。

理解第一點對于我們寫語法解釋器很重要，由于語句是由表達式組成的，而表達式是有詞組組成的，詞組是有詞法解析器進行解析生成的，所以，在語法解釋器中，將以表達式為切入點，由表達式解析再深入到語句解析中。

抽象語法樹（AST）

了解一個parser的結構，以及parser解析語法所依賴的規則后，接下來，我們需要了解一下一個parser所生產出來的結果——抽象語法樹。在文章的開頭，我有簡單的解釋抽象語法樹即是具體代碼片段的抽象表達，那它具體是長什么樣的呢？

function sum (a , b) {
  return a+b;
}

以上的代碼片段，AST樹的描述如下（使用babylon7-7.0.0-beta.44，結果進行了簡化）：

{
      "type": "Program",
    "body": [
      {
        "type": "FunctionDeclaration",
        "id": {
          "type": "Identifier",
          "name": "sum"
        },
        "params": [
          {
            "type": "Identifier",
            "name": "a"
          },
          {
            "type": "Identifier",
            "name": "b"
          }
        ],
        "body": {
          "type": "BlockStatement",
          "body": [
            {
              "type": "ReturnStatement",
              "argument": {
                "type": "BinaryExpression",
                "left": {
                  "type": "Identifier",
                  "name": "a"
                },
                "operator": "+",
                "right": {
                  "type": "Identifier",
                  "name": "b"
                }
              }
            }
          ]
        }
      }
    ]
}

對該AST仔細觀察一番，便會明白，AST其實即是我們在已經ECMAScript標準對代碼進行解析后，將標識符（identifier）、聲明（declaration）、表達式（expression）、語句（statement）等按代碼表述的邏輯整理成為樹狀結構。就拿上面的例子來說，當語法解析器識別了一個二元表達式（Binary Expression），便將這個二元表達式所攜帶的信息——左值，右值，操作符按照固定的計算機可讀的數據格式保存下來，即是我們看到的AST樹了。

當然，AST也需要具備固定的格式，這樣計算機才能依照該格式閱讀AST并進行接下來的編譯工作，當然，有一些AST也被用來轉義（如babel）。關于AST定義的規則，我們可以參考babel的定義，這也是后面我們實現parser時，所參考的標準。

接下來

理解完以上相關的知識，我們便具備編寫一個parser的先決條件了，那在下一章，我們將實際操作一番，編寫一個簡易版本的JavaScript語言parser。

《如何編寫簡單的parser（實踐篇）》

GPU云服務器云服務器鳥哥的服務器篇如何基礎篇之基礎篇 java語言程序設計基礎篇

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101303.html

如何編寫簡單的parser（實踐篇）

摘要：負責讀取和記錄當前代碼的位置，并把讀取到的代碼交給處理，其意義在于，當傳遞給的代碼需要進行判讀猜測時，能夠記錄當前讀取的位置，并在接下來的操作匯總回滾到之前的讀取位置，也能在發生語法錯誤時，準確指出錯誤發生在代碼段的第幾行第幾個字符。上一篇（《如何編寫簡單的parser（基礎篇）》）中介紹了編寫一個parser所需具備的基礎知識，接下來，我們要動手實踐一個簡單的parser，既然是簡...

shaonbean 2019-08-23 15:04 評論0 收藏0
如何構建一個分布式爬蟲：基礎篇

摘要：繼上篇我們談論了的基本知識后，本篇繼續講解如何一步步使用構建分布式爬蟲。到此，我們就實現了一個很基礎的分布式網絡爬蟲，但是它還不具有很好的擴展性，而且貌似太簡單了下一篇我將以微博數據采集為例來演示如何構建一個穩健的分布式網絡爬蟲。繼上篇我們談論了Celery的基本知識后，本篇繼續講解如何一步步使用Celery構建分布式爬蟲。這次我們抓取的對象定為celery官方文檔。首先，我們新建...

ssshooter 2019-07-31 10:56 評論0 收藏0
PostCSS自學筆記（一）【安裝使用篇】

摘要：而則可制定個人需求的一套解決方案僅安裝需要的插件。迫不及待的你已經等不及安裝使用了吧。安裝及使用一般是結合自動化工具使用，如果要單獨使用可以安裝，這里我先對的安裝使用講解下。接下來說點實際的，如何利用結合自動化工作在項目中使用。 PostCSS介紹 PostCSS是一個利用JS插件來對CSS進行轉換的工具，這些插件非常強大，強大到無所不能。其中，Autoprefixer就是眾多Post...

jsummer 2019-08-29 13:17 評論0 收藏0
Spring Cloud Alibaba基礎教程：Nacos的集群部署

摘要：通過本文，我們將完成生產環境的搭建。第二步修改文件，增加支持數據源配置，添加目前只支持數據源的用戶名和密碼。另外，的集群需要個或個以上的節點，并且確保這三個節點之間是可以互相訪問的。也可以故意的關閉某個實例，來驗證集群是否還能正常服務。前情回顧：《Spring Cloud Alibaba基礎教程：使用Nacos實現服務注冊與發現》《Spring Cloud Alibaba基礎教...

elarity 2019-08-16 15:15 評論0 收藏0
Spring Cloud Alibaba基礎教程：Nacos的集群部署

摘要：通過本文，我們將完成生產環境的搭建。第二步修改文件，增加支持數據源配置，添加目前只支持數據源的用戶名和密碼。另外，的集群需要個或個以上的節點，并且確保這三個節點之間是可以互相訪問的。也可以故意的關閉某個實例，來驗證集群是否還能正常服務。前情回顧：《Spring Cloud Alibaba基礎教程：使用Nacos實現服務注冊與發現》《Spring Cloud Alibaba基礎教...

godruoyi 2019-06-24 18:19 評論0 收藏0