JS 做一個簡單的 Parser

来源:https://www.cnblogs.com/1bite/archive/2023/03/26/17252162.html
-Advertisement-
Play Games

本文使用簡單易懂的代碼，實現了一組可以構造解析器的函數。相信通過本文的演示，你應該對解析器的基本工作原理有了一個淺淺的瞭解。 ...


前言

前些天偶然看到以前寫的一份代碼，註意有一段塵封的代碼，被我遺忘了。這段代碼是一個簡單的解析器，當時是為瞭解析日誌而做的。最初解析日誌時，我只是簡單的正則加上分割，寫著寫著，我想，能不能用一個簡單的方案做個解析器，這樣可以解析多種日誌。於是就有了這段代碼，後來日誌解析完了，沒有解析其它日誌就給忘了。再次看到這段代碼，用非常簡單易讀的代碼就實現了一個解析器，覺得非常值得分享。

思路

言歸正傳，這個簡單的解析器是怎麼構思的呢？那要先從模式匹配開始。解析與模式匹配有很多相似之處，比如解析一個整數，跟匹配一個整數就是相似的。都需要根據整數的文法 0|[1-9]\d* 把文本中滿足文法的部分找出來，不同的是，當說到解析整數的時候，我們希望得到的結果是一個整數，而不是一段文本。更進一步，如果我們已經知道如何解析整數，那麼解析加減表達式又可以看到一些相似性。加減表達式的文法可以表示為 num ('+'|'-' num)*，就像文本模式匹配一樣，需要對一些“東西”的到達順序、重覆次數、分支進行匹配。

從上面的描述可以看出，我們要做的是某種模式匹配。模式匹配的明星非正則表達式莫數。觀察正則表達式，我們基本的需求都有啥？比如有，匹配一個字元或者按順序出現的字元。好了，就從這兩點出發。我們可以設計兩個函數，一個 match 函數用來匹配單個字元，一個 seq 函數表示按順序匹配。顯然，多個 match 就可以形成 seq，seq 是一個高階函數。但是，seq 是直接組合 match 嗎？當然不是，因為 match 需要一個參數，表示需要匹配的字元是哪個，所以 match 也是一個高階函數，而 seq 需要 match 產生的函數組合成新函數，即 seq([match('a'), match('b'), match('c')])。那 match 和 seq 生成的函數是什麼？答案是匹配器。允許我們直接對文本進行匹配：

const match_a = match('a');
match_a('abc');

const match_abc = seq([match('a'), match('b'), match('c')]);
match_abc('abc');

由於我們要組合函數，所以匹配器不是只簡單返回 bool 值，這樣組合過程中，狀態會丟失。我們讓匹配器返回兩個值：一個是匹配後剩餘的字元串；一個是匹配是否成功。於是我們就有了：

declare type Matcher = (src: string) => [string, bool];

function match(ch): Matcher {
    return src => {
        if (src.startsWith(ch)) return [src.substring(1), true];
        return [src, false];
    };
}

// 順序匹配，其中一個失敗則整體失敗
function seq(steps: Matcher[]): Matcher {
    return src => {
        for (const step of steps) {
            const [rest, ok] = step(src);
            if (!ok) return [src, false];
            src = rest;
        }
        return [src, true];
    };
}

試試看。

const match_a = match('a');
console.log(...match_a('abc')); // "bc" true
console.log(...match_a('def')); // "def" false 

const match_abc = seq([match('a'), match('b'), match('c')]);
match_abc('abc');
console.log(...match_abc('abc')); // "" true
console.log(...match_abc('abd')); // "abd" false

妙極了！

nice

擁抱正則表達式

接下來，我們可以在這個基礎上實現正則表達式的其它模式，比如：

  1. alt。候選列表，列表中有一個匹配成功則成功，一個失敗則整體失敗。對應正則表達式中是 | 和 []。
  2. opt。可選，對應正則表達的 ? 模式。
  3. many。多次重覆，對應正則表達式中的 * 模式。

其它不一一列舉，如果繼續下去，應該能實現一個自己的正則表達式，但不是我們的目標，我想先回到“解析”上。

觀察 match 函數，它只能匹配一個字元，如果要匹配多個則要使用 seq 進行組合，不是很方便。既然正則表達式可以進行文本匹配，我們沒有必要重覆正則表達式的工作，直接利用它就好。所以，我們可以把正則表達式作為 match 的參數：

function match(pattern: RegExp): Matcher {
    // ...
}

解析

前面說過，解析整數的結果是整數而不是長得像整數的字元串，因此，Matcher 不能返回 bool，而應該是某個“結果”。所以 Matcher 的簽名應該是 (src: string) => [string, any]。怎麼把文本變成那個“結果”呢，可以在 match 後面加一個回調，表示匹配到了文本後，應該如何處理這個文本。顯然，這個回調的輸入參數是匹配到的文本，輸出是“結果”，即 (token: string) => any。我們把這個回調函數取名為 Action。

如果現在嘗試去改 match 函數，就會發現一個問題，seq 函數也返回 Matcher，但這個匹配器執行後應該返回什麼“結果”呢？為解決這個問題，我們也需要給 seq 函數添加 Action，只不過 seq 函數的 Action 的輸入參數是一個列表。還有，匹配成功後，我也可以不做任何動作，此時把匹配的文本繼續往下傳即可。現在我們再修改代碼：

declare type Matcher = (src: string) => [string, any];
declare type Action = (val: any) => any;

function noop(tok: any){ return tok; }

// 用 `pattern` 匹配文本的開頭
function match(pattern: RegExp, action: Action = noop): Matcher {
    return src => {
        const m = pattern.exec(src);
        if (!m || m.index !== 0) throw new Error(`unexpected token '${src[0]}'`);
        const rest = src.substring(m[0].length);
        return [rest, action(m[0])];
    };
}

// 順序匹配，其中一個失敗則整體失敗
function seq(steps: Matcher[], action: Action = noop): Matcher {
    return src => {
        const list: any[] = [];

        for (const step of steps) {
            const [rest, val] = step(src); // `step` 函數會 `throw`，因此一個失敗整體就會失敗 
            src = rest;
            list.push(val);
        }

        return [src, action(list)];
    };
}

玩玩看：

const match_helloworld = seq([match(/hello/), match(/ /), match(/world/)]);

console.log(...match_helloworld('hello world')); // "" ["hello", " ", "world"]
console.log(...match_helloworld('helloworld'));  // Error: unexpected token 'w'

還是妙，但目前為止還算常規，跟正則表達式差不多。那麼，接下來看下麵這個例子：

const int = match(/0|[1-9]\d*/, Number); // 用整數的文法匹配文本，並把匹配到的文本直接轉成 js 的 `number`

// 根據文法 `int('+'|'-')int` 進行匹配，並根據中間 token 進行計算
const Exp = seq([int, match(/\+|\-/), int], toks => {
    if (toks[1] === '+') return toks[0] + toks[2]; // 因為 `int` 函數返回的是 `number`，所以這裡可以直接進行計算！
    if (toks[1] === '-') return toks[0] - toks[2];
    return toks;
});

console.log(...Exp('1+2')); // "" 3
console.log(...Exp('5-3')); // "" 2

現在是不是更妙了。

oooh

完全體

光有 seq 可不能滿足解析的全部需求，還得要把其它模式加進來，我就不一一說明其它模式的實現方法了，直接給出全部代碼，相信看代碼也很好理解：

declare type Matcher = (src: string) => [string, any];
declare type Action = (val: any) => any;

function noop(tok: any){ return tok; }

// 原來的 `match` 函數，改了個名字
function token(pattern: string|RegExp, action: Action = noop): Matcher {
    if (pattern instanceof RegExp) {
        return (src) => {
            if (src.length === 0) throw new SyntaxError("Unexpected EOS");
            const regex = new RegExp(pattern.source[0] === '^' ? pattern.source : '^' + pattern.source);
            const m = regex.exec(src);
            if (!m || m.index !== 0)
                throw new SyntaxError(`Unexpected token '${src[0]}', expected: ${pattern}`);
            const rest = src.substring(m[0].length);
            return [rest, action(m[0])];
        };
    } else if (typeof pattern === "string") {
        return (src) => {
            if (src.length === 0) throw new SyntaxError("Unexpected EOS");
            if (!src.startsWith(pattern))
                throw new SyntaxError(`Unexpected token '${src[0]}', expected: ${pattern}`);
            const rest = src.substring(pattern.length);
            if (action) return [rest, action(pattern)];
            return [rest, pattern];
        };
    }
    throw Error("pattern must to be instance of string or RegExp");
}

// 順序匹配，其中一個失敗則整體失敗
function seq(steps: Matcher[], action: Action = noop): Matcher {
    return src => {
        const list: any[] = [];

        for (const step of steps) {
            const [rest, val] = step(src); // `step` 函數會 `throw`，因此一個失敗整體就會失敗 
            src = rest;
            list.push(val);
        }

        return [src, action(list)];
    };
}

// 可選匹配
function opt(step: Matcher, action: Action = noop): Matcher {
    return (src) => {
        try {
            const [rest, v] = step(src);
            return [rest, action(v)];
        } catch (err) {
            return [src, undefined]; // 也許這裡可以改成 `return [src, action("")]`;
        }
    };
}

// 候選列表匹配，列表中其中一個匹配即可
function alt(steps: Matcher[], action: Action = noop): Matcher {
    return (src) => {
        for (const step of steps) {
            try {
                const [rest, v] = step(src);
                return [rest, action(v)];
            } catch (_) {
                // mute
            } 
        }

        throw new Error(`unknown token ${src[0]}`);
    };
}

// 重覆任意次數
function many(item: Matcher, action: (vals: any[]) => any = noop): Matcher {
    return src => {
        let list: any[] = [];
        let val = undefined;

        while (true) {
            try {
                [src, val] = item(src);
                list.push(val);
            } catch (_) {
                break;
            }
        }

        return [src, action(list)];
    };
}

// 帶分隔符的重覆，即滿足 `item (sep item)*` 這種文法的
function many_sep(sep: Matcher, item: Matcher, action: (vals: any[]) => any = noop): Matcher {
    const etc = seq([sep, item], vs => vs[1]);
    return (src) => {
        let list: any[] = [];
        let val = undefined;

        try {
            [src, val] = item(src);
            list.push(val);
        } catch (_) {
            return [src, action(list)];
        }

        // 以下邏輯也可通過調用 `many` 實現
        while (true) {
            try {
                [src, val] = etc(src);
                list.push(val);
            } catch (_) {
                break;
            }
        }

        return [src, action(list)];
    };
}

好了，直接攢個大活兒，咱們用這些東西解析 JSON 看看：

const ws = token(/\s*/);

const Sep = seq([token(','), opt(ws)], v => v[0]); // 也可以簡寫為 `token(/,\s*/)`

const Str = token(/"([^\\"]|\\[\\\/bfrtn]|\\u[0-9a-fA-F]{0})*"/, JSON.parse); // 這裡使用 `JSON.parse` 算是作弊，不過用它讓演示代碼縮短了不少

const Num = token(/-?(0|[1-9]\d*)(\.\d+)?([eE][\+\-]?\d+)?/, Number);

// Elems = Val (',' Val)*
const Elems = many_sep(Sep, src => Val(src));

// KVs = KV (',' KV)*
const KVs = many_sep(Sep, src => KV(src));

// js 中可以直接使用 `Object.fromEntries`
function objFromKVs(kvs: [string, any][]) {
    return kvs.reduce((obj, [k, v]) => { obj[k] = v; return obj; }, {} as any);
}

// Val = Str | Num | 'true' | 'false' | 'null' | '[' ws Elems ws ']' | '{' ws KVs ws '}'
const Val = alt([
    Str,
    Num,
    token(/true|false/, token => token === 'true'),
    token(/null/, _ => null),
    seq([token('['), ws, Elems, ws, token(']')], v => v[2]),                   // '[' ws Elems ws ']'
    seq([token('{'), ws, KVs, ws, token('}')], v => objFromKVs(v[2] as any[])) // '{' ws KVs ws '}'
]);

// KV = Str ws ':' ws Val
const KV = seq([
    Str,
    ws,
    token(':'),
    ws,
    Val,
], kv => [kv[0], kv[4]]); // 匹配 KV 列表，並轉換成 `[[key, val]...]` 的形式

// 演示
console.log(...Val('[1, 2.3e4, true, null, "\\t"]')); // "" [1, 23000, true, null, "        "]
console.log(...Val('{ "k1": 123, "k2": true }'));     // "" {k1: 123, k2: true}

怎麼樣，相當不錯吧!!!

god

接下來再演示下進階版本的表達式解析與求值，支持加、減、乘、除和括弧：

// Factor = '(' ws Exp ws ')' | Num
const Factor = alt([
    seq([token('('), ws, src => Exp(src), ws, token(')')], vals => vals[2]),
    Num,
]);

// Term = Factor (ws '*|/' ws Factor)*
const Term = seq([Factor, many(seq([ws, token(/\*|\//), ws, Factor]))], ([head, tail]) => {
    return (tail as any[]).reduce((acc, x) => {
        if (x[1] === '*') return acc * x[3];
        if (x[1] === '/') return acc / x[3];
        return acc;
    }, head);
});

// Exp = Term (ws '+|-' ws Term)*
const Exp = seq([Term, many(seq([ws, token(/\+|-/), ws, Term]))], ([head, tail]) => {
    return (tail as any[]).reduce((acc, x) => {
        if (x[1] === '+') return acc + x[3];
        if (x[1] === '-') return acc - x[3];
        return acc;
    }, head);
});

console.log(...Exp('( 1 + 2 * 5 ) * 3')); // "" 33

總結

本文使用簡單易懂的代碼，實現了一組可以構造解析器的函數。相信通過本文的演示，你應該對解析器的基本工作原理有了一個淺淺的瞭解。實際上，我們實現的這一組函數是一種領域特定語言，即 DSL。雖然實現方式簡單，但不妨礙這種 DSL 的實用性，在日常的小腳本中，更加體現它的小巧、易懂、功能強大。不過也要註意的是，我是以小巧、簡易為目標實現的，所以性能不是首要目標，將本文的實現用於性能挑剔的場合肯定是不合適的。


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

-Advertisement-
Play Games
更多相關文章
  • 解決Mariadb設置密碼無效，可以直接登錄
    問題 搭建Typecho的時候使用的是Mariadb資料庫，建立在Debian伺服器上，正常aptitude install mariadb-server，安裝好之後顯示success沒有任何報錯，出於習慣第一次用資料庫之前我都會mysql_secure_installation命令將其初始化避免一 ...
  • Mysql資料庫詳細筆記(跟隨b站韓順平教程)
    Mysql資料庫 一、資料庫 mysql服務啟動,在cmd輸入net start mysql #創建資料庫 CREATE DATABASE hsp_db01; #創建一個使用 utf8 字元集的 hsp_db02 資料庫 CREATE DATABASE hsp_db02 CHARACTER SET ...
  • P3 創建資料庫
    P3 創建資料庫 CHARACTER SET：指定資料庫採用的字元集，如果不指定字元集，預設utf8 COLLATE：指定資料庫字元集的校對規則（常用的 utf8_bin[區分大小寫]、utf8_general_ci[不區分大小寫]，註意預設是utf8_general_ci） 創建指令：CREATE ...
  • Mysql 查詢指定節點的所有子節點
    原文鏈接：https://www.zhoubotong.site/post/92.html 通常我們直接通過遞歸查詢來達到實現子節點數據獲取的需求，這裡不談存儲過程的實現，存儲過程普通賬號有許可權限制，通常也不易於開發者維護，這裡介紹下純mysql遞歸實現的方式：測試數據可以通過之前的一篇文章來模擬。 ...
  • MySQL與Java常用數據類型的對應關係
    一、字元串數據類型: MySQL類型名 大小 用途 對應Java類名 char 0-255 bytes 定長字元串 （姓名、性別、學號） String varchar 0-65535 bytes 變長字元串（比上面更長一點的那種） String tinytext 0-255 bytes 比較短的那種 ...
  • 支持10倍訂單增長，攜程資料庫架構升級實踐
    隨著機票訂單業務的不斷增長，當前訂單處理系統的架構已經不能滿足日益增長的業務需求，系統性能捉襟見肘，主要體現在以下方面： 資料庫CPU資源在業務高峰期經常達到50%以上，運行狀況亮起了黃燈； 磁碟存儲空間嚴重不足，需要經常清理磁碟數據騰挪可用空間； 系統擴容能力不足，如果需要提升處理能力只能更換配置... ...
  • Single-spa 源碼淺析
    引言 前一段時間, 正好在做微前端的接入和微前端管理平臺的相關事項。 而我們當前使用的微前端框架則是 qiankun, 他是這樣介紹自己的: qiankun 是一個基於 single-spa 的微前端實現庫，旨在幫助大家能更簡單、無痛的構建一個生產可用微前端架構系統。 所以本文基於 single-s ...
  • 前端設計模式——路由模式
    路由模式（Router Pattern）：將頁面的不同狀態映射到不同的URL路徑上，使得用戶可以直接通過URL來訪問頁面的不同狀態。 路由模式通常用於實現單頁面應用（SPA）的頁面導航和狀態管理。具體來說，路由模式通過解析URL路徑來確定應該顯示哪個頁面，並使用歷史記錄API來管理頁面狀態。 一般來 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類