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 就可以形成 seqseq 是一個高階函數。但是,seq 是直接組合 match 嗎?當然不是,因為 match 需要一個參數,表示需要匹配的字元是哪個,所以 match 也是一個高階函數,而 seq 需要 match 產生的函數組合成新函數,即 seq([match('a'), match('b'), match('c')])。那 matchseq 生成的函數是什麼?答案是匹配器。允許我們直接對文本進行匹配:

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
更多相關文章
  • 問題 搭建Typecho的時候使用的是Mariadb資料庫,建立在Debian伺服器上,正常aptitude install mariadb-server,安裝好之後顯示success沒有任何報錯,出於習慣第一次用資料庫之前我都會mysql_secure_installation命令將其初始化避免一 ...
  • Mysql資料庫 一、資料庫 mysql服務啟動,在cmd輸入net start mysql #創建資料庫 CREATE DATABASE hsp_db01; #創建一個使用 utf8 字元集的 hsp_db02 資料庫 CREATE DATABASE hsp_db02 CHARACTER SET ...
  • P3 創建資料庫 CHARACTER SET:指定資料庫採用的字元集,如果不指定字元集,預設utf8 COLLATE:指定資料庫字元集的校對規則(常用的 utf8_bin[區分大小寫]、utf8_general_ci[不區分大小寫],註意預設是utf8_general_ci) 創建指令:CREATE ...
  • 原文鏈接:https://www.zhoubotong.site/post/92.html 通常我們直接通過遞歸查詢來達到實現子節點數據獲取的需求,這裡不談存儲過程的實現,存儲過程普通賬號有許可權限制,通常也不易於開發者維護,這裡介紹下純mysql遞歸實現的方式:測試數據可以通過之前的一篇文章來模擬。 ...
  • 一、字元串數據類型: MySQL類型名 大小 用途 對應Java類名 char 0-255 bytes 定長字元串 (姓名、性別、學號) String varchar 0-65535 bytes 變長字元串(比上面更長一點的那種) String tinytext 0-255 bytes 比較短的那種 ...
  • 隨著機票訂單業務的不斷增長,當前訂單處理系統的架構已經不能滿足日益增長的業務需求,系統性能捉襟見肘,主要體現在以下方面: 資料庫CPU資源在業務高峰期經常達到50%以上,運行狀況亮起了黃燈; 磁碟存儲空間嚴重不足,需要經常清理磁碟數據騰挪可用空間; 系統擴容能力不足,如果需要提升處理能力只能更換配置... ...
  • 引言 前一段時間, 正好在做微前端的接入和微前端管理平臺的相關事項。 而我們當前使用的微前端框架則是 qiankun, 他是這樣介紹自己的: qiankun 是一個基於 single-spa 的微前端實現庫,旨在幫助大家能更簡單、無痛的構建一個生產可用微前端架構系統。 所以本文基於 single-s ...
  • 路由模式(Router Pattern):將頁面的不同狀態映射到不同的URL路徑上,使得用戶可以直接通過URL來訪問頁面的不同狀態。 路由模式通常用於實現單頁面應用(SPA)的頁面導航和狀態管理。具體來說,路由模式通過解析URL路徑來確定應該顯示哪個頁面,並使用歷史記錄API來管理頁面狀態。 一般來 ...
一周排行
    -Advertisement-
    Play Games
  • 下麵是一個標準的IDistributedCache用例: public class SomeService(IDistributedCache cache) { public async Task<SomeInformation> GetSomeInformationAsync (string na ...
  • 這個庫提供了在啟動期間實例化已註冊的單例,而不是在首次使用它時實例化。 單例通常在首次使用時創建,這可能會導致響應傳入請求的延遲高於平時。在註冊時創建實例有助於防止第一次Request請求的SLA 以往我們要在註冊的時候實例單例可能會這樣寫: //註冊: services.AddSingleton< ...
  • 最近公司的很多項目都要改單點登錄了,不過大部分都還沒敲定,目前立刻要做的就只有一個比較老的項目 先改一個試試手,主要目標就是最短最快實現功能 首先因為要保留原登錄方式,所以頁面上的改動就是在原來登錄頁面下加一個SSO登錄入口 用超鏈接寫的入口,頁面改造後如下圖: 其中超鏈接的 href="Staff ...
  • Like運算符很好用,特別是它所提供的其中*、?這兩種通配符,在Windows文件系統和各類項目中運用非常廣泛。 但Like運算符僅在VB中支持,在C#中,如何實現呢? 以下是關於LikeString的四種實現方式,其中第四種為Regex正則表達式實現,且在.NET Standard 2.0及以上平... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他們的程式記憶體會偶發性暴漲,自己分析了下是非托管記憶體問題,讓我幫忙看下怎麼回事?哈哈,看到這個dump我還是非常有興趣的,居然還有這種游戲幣自助機類型的程式,下次去大玩家看看他們出幣的機器後端是不是C#寫的?由於dump是linux上的程式,剛好win ...
  • 前言 大家好,我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的,可以參考我的另一個項目: 手寫從零實現簡易版 tomcat minicat 手寫 ngin ...
  • 上一次的介紹,主要圍繞如何統一去捕獲異常,以及為每一種異常添加自己的Mapper實現,並且我們知道,當在ExceptionMapper中返回非200的Response,不支持application/json的響應類型,而是寫死的text/plain類型。 Filter為二方包異常手動捕獲 參考:ht ...
  • 大家好,我是R哥。 今天分享一個爽飛了的面試輔導 case: 這個杭州兄弟空窗期 1 個月+,面試了 6 家公司 0 Offer,不知道問題出在哪,難道是杭州的 IT 崩盤了麽? 報名面試輔導後,經過一個多月的輔導打磨,現在成功入職某上市公司,漲薪 30%+,955 工作制,不咋加班,還不捲。 其他 ...
  • 引入依賴 <!--Freemarker wls--> <dependency> <groupId>org.freemarker</groupId> <artifactId>freemarker</artifactId> <version>2.3.30</version> </dependency> ...
  • 你應如何運行程式 互動式命令模式 開始一個互動式會話 一般是在操作系統命令行下輸入python,且不帶任何參數 系統路徑 如果沒有設置系統的PATH環境變數來包括Python的安裝路徑,可能需要機器上Python可執行文件的完整路徑來代替python 運行的位置:代碼位置 不要輸入的內容:提示符和註 ...