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
  • C#TMS系統學習（BaseCity頁面）
    C#TMS系統代碼-基礎頁面BaseCity學習 本人純新手，剛進公司跟領導報道，我說我是java全棧，他問我會不會C#，我說大學學過，他說這個TMS系統就給你來管了。外包已經把代碼給我了，這幾天先把增刪改查的代碼背一下，說不定後面就要趕鴨子上架了 Service頁面 //using => impo ...
  • C# - 委托與事件
    委托與事件 委托 委托的定義 委托是C#中的一種類型，用於存儲對方法的引用。它允許將方法作為參數傳遞給其他方法，實現回調、事件處理和動態調用等功能。通俗來講，就是委托包含方法的記憶體地址，方法匹配與委托相同的簽名，因此通過使用正確的參數類型來調用方法。 委托的特性 引用方法：委托允許存儲對方法的引用， ...
  • 解析 ABP vNext 依賴註入實現【屬性註入】的原理
    前言 這幾天閑來沒事看看ABP vNext的文檔和源碼，關於關於依賴註入(屬性註入)這塊兒產生了興趣。 我們都知道。Volo.ABP 依賴註入容器使用了第三方組件Autofac實現的。有三種註入方式，構造函數註入和方法註入和屬性註入。 ABP的屬性註入原則參考如下： 這時候我就開始疑惑了，因為我知道 ...
  • C#TMS系統學習（ShippingNotice頁面）
    C#TMS系統代碼-業務頁面ShippingNotice學習 學一個業務頁面，ok，領導開完會就被裁掉了，很突然啊，他收拾東西的時候我還以為他要旅游提前請假了，還在尋思為什麼回家連自己買的幾箱飲料都要叫跑腿帶走，怕被偷嗎？還好我在他開會之前拿了兩瓶芬達 感覺感覺前面的BaseCity差不太多，這邊的 ...
  • C#動態查詢：巧用Expression組合多條件表達式
    概述：在C#中，通過`Expression`類、`AndAlso`和`OrElse`方法可組合兩個`Expression<Func<T, bool>>`，實現多條件動態查詢。通過創建表達式樹，可輕鬆構建複雜的查詢條件。 在C#中，可以使用AndAlso和OrElse方法組合兩個Expression< ...
  • 在Biwen.QuickApi中整合一個極簡的發佈訂閱(事件匯流排)
    閑來無聊在我的Biwen.QuickApi中實現一下極簡的事件匯流排,其實代碼還是蠻簡單的,對於初學者可能有些幫助 就貼出來,有什麼不足的地方也歡迎板磚交流~ 首先定義一個事件約定的空介面 public interface IEvent{} 然後定義事件訂閱者介面 public interface I ...
  • WPF 穩定的全屏化視窗方法
    1. 案例 成某三甲醫預約系統， 該項目在2024年初進行上線測試，在正常運行了兩天後，業務系統報錯：The connection pool has been exhausted, either raise MaxPoolSize (currently 800) or Timeout (curren ...
  • 在 WPF 中集成 ASP.NET Core 和 WebView2 用於集成 SPA 應用
    背景 我們有些工具在 Web 版中已經有了很好的實踐，而在 WPF 中重新開發也是一種費時費力的操作，那麼直接集成則是最省事省力的方法了。 思路解釋 為什麼要使用 WPF？莫問為什麼，老 C# 開發的堅持，另外因為 Windows 上已經裝了 Webview2/edge 整體打包比 electron ...
  • C#事件
    EDP是一套集組織架構，許可權框架【功能許可權，操作許可權，數據訪問許可權，WebApi許可權】，自動化日誌，動態Interface，WebApi管理等基礎功能於一體的，基於.net的企業應用開發框架。通過友好的編碼方式實現數據行、列許可權的管控。 ...
  • .Net8.0 Blazor Hybird 桌面端 (WPF/Winform) 發佈到 Win7+
    .Net8.0 Blazor Hybird 桌面端 (WPF/Winform) 實測可以完整運行在 win7sp1/win10/win11. 如果用其他工具打包,還可以運行在mac/linux下, 傳送門BlazorHybrid 發佈為無依賴包方式 安裝 WebView2Runtime 1.57 M ...
所有分類