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
  • 如何基於surging跨網關跨語言進行緩存降級
    基於.NET Framework 4.8 開發的深度學習模型部署測試平臺，提供了YOLO框架的主流系列模型，包括YOLOv8~v9，以及其系列下的Det、Seg、Pose、Obb、Cls等應用場景，同時支持圖像與視頻檢測。模型部署引擎使用的是OpenVINO™、TensorRT、ONNX runti... ...
  • 十年沉澱，重啟開發之路
    十年沉澱，重啟開發之路 十年前，我沉浸在開發的海洋中，每日與代碼為伍，與演算法共舞。那時的我，滿懷激情，對技術的追求近乎狂熱。然而，隨著歲月的流逝，生活的忙碌逐漸占據了我的大部分時間，讓我無暇顧及技術的沉澱與積累。 十年間，我經歷了職業生涯的起伏和變遷。從初出茅廬的菜鳥到逐漸嶄露頭角的開發者，我見證了 ...
  • C#.NET體系圖文概述—2024最全總結
    C# 是一種簡單、現代、面向對象和類型安全的編程語言。.NET 是由 Microsoft 創建的開發平臺，平臺包含了語言規範、工具、運行，支持開發各種應用，如Web、移動、桌面等。.NET框架有多個實現，如.NET Framework、.NET Core（及後續的.NET 5+版本），以及社區版本M... ...
  • 班級擂臺（光榮）榜 - 極簡教育小工具
    前言 本文介紹瞭如何使用三菱提供的MX Component插件實現對三菱PLC軟元件數據的讀寫，記錄了使用電腦模擬，模擬PLC，直至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1. PLC開發編程環境GX Works2，GX Works2下載鏈接 https:// ...
  • web server apache tomcat11-31-websocket
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • day31-jQuery
    1、jQuery介紹 jQuery是什麼 jQuery是一個快速、簡潔的JavaScript框架，是繼Prototype之後又一個優秀的JavaScript代碼庫（或JavaScript框架）。jQuery設計的宗旨是“write Less，Do More”，即倡導寫更少的代碼，做更多的事情。它封裝 ...
  • aardio爬蟲) 實戰篇：逆向有道翻譯web介面
    前言 之前的文章把js引擎(aardio封裝庫) 微軟開源的js引擎(ChakraCore))寫好了，這篇文章整點js代碼來測一下bug。測試網站：https://fanyi.youdao.com/index.html#/ 逆向思路 逆向思路可以看有道翻譯js逆向（MD5加密，AES加密）附完整源碼 ...
  • 面試官：這就是你理解的Java多線程基礎？
    引言 現代的操作系統（Windows，Linux，Mac OS）等都可以同時打開多個軟體（任務），這些軟體在我們的感知上是同時運行的，例如我們可以一邊瀏覽網頁，一邊聽音樂。而CPU執行代碼同一時間只能執行一條，但即使我們的電腦是單核CPU也可以同時運行多個任務，如下圖所示，這是因為我們的 CPU 的 ...
  • Python文本統計與分析從基礎到進階
    掌握使用Python進行文本英文統計的基本方法，並瞭解如何進一步優化和擴展這些方法，以應對更複雜的文本分析任務。 ...
  • Redis多數據源，看這篇就夠了
    背景 Redis多數據源常見的場景： 分區數據處理：當數據量增長時，單個Redis實例可能無法處理所有的數據。通過使用多個Redis數據源，可以將數據分區存儲在不同的實例中，使得數據處理更加高效。 多租戶應用程式：對於多租戶應用程式，每個租戶可以擁有自己的Redis數據源，以確保數據隔離和安全性。 ...
所有分類