主頁 > 企業開發 > JS 做一個簡單的 Parser

JS 做一個簡單的 Parser

2023-03-27 08:57:12 企業開發

前言

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

思路

言歸正傳，這個簡單的決議器是怎么構思的呢？那要先從模式匹配開始，決議與模式匹配有很多相似之處，比如決議一個整數，跟匹配一個整數就是相似的，都需要根據整數的文法 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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> {
        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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> {
        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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> {
        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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> {
        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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> {
        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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> Val(src));

// KVs = KV (',' KV)*
const KVs = many_sep(Sep, src =https://www.cnblogs.com/1bite/archive/2023/03/26/> 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 =https://www.cnblogs.com/1bite/archive/2023/03/26/> 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 的實用性，在日常的小腳本中，更加體現它的小巧、易懂、功能強大，不過也要注意的是，我是以小巧、簡易為目標實作的，所以性能不是首要目標，將本文的實作用于性能挑剔的場合肯定是不合適的，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/548250.html

標籤：其他

上一篇：前端設計模式——計算屬性模式

下一篇：前端設計模式——路由模式

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • IEEE1588PTP在數字化變電站時鐘同步方面的應用

    IEEE1588ptp在數字化變電站時鐘同步方面的應用 京準電子科技官微——ahjzsz 一、電力系統時間同步基本概況 隨著對IEC 61850標準研究的不斷深入，國內外學者提出基于IEC61850通信標準體系建設數字化變電站的發展思路。數字化變電站與常規變電站的顯著區別在于程序層傳統的電流/電壓互 ......

    uj5u.com 2020-09-10 03:51:52 more
  • HTTP request smuggling CL.TE

    CL.TE 簡介 前端通過Content-Length處理請求，通過反向代理或者負載均衡將請求轉發到后端，后端Transfer-Encoding優先級較高，以TE處理請求造成安全問題。 檢測 發送如下資料包 POST / HTTP/1.1 Host: ac391f7e1e9af821806e890 ......

    uj5u.com 2020-09-10 03:52:11 more
  • 網路滲透資料大全單——漏洞庫篇

    網路滲透資料大全單——漏洞庫篇漏洞庫 NVD ——美國國家漏洞庫 →http://nvd.nist.gov/。 CERT ——美國國家應急回應中心 →https://www.us-cert.gov/ OSVDB ——開源漏洞庫 →http://osvdb.org Bugtraq ——賽門鐵克 →ht ......

    uj5u.com 2020-09-10 03:52:15 more
  • 京準講述NTP時鐘服務器應用及原理

    京準講述NTP時鐘服務器應用及原理京準講述NTP時鐘服務器應用及原理 安徽京準電子科技官微——ahjzsz 北斗授時原理 授時是指接識訓通過某種方式獲得本地時間與北斗標準時間的鐘差，然后調整本地時鐘使時差控制在一定的精度范圍內。 衛星導航系統通常由三部分組成：導航授時衛星、地面檢測校正維護系統和用戶 ......

    uj5u.com 2020-09-10 03:52:25 more
  • 利用北斗衛星系統設計NTP網路時間服務器

    利用北斗衛星系統設計NTP網路時間服務器 利用北斗衛星系統設計NTP網路時間服務器 安徽京準電子科技官微——ahjzsz 概述 NTP網路時間服務器是一款支持NTP和SNTP網路時間同步協議，高精度、大容量、高品質的高科技時鐘產品。 NTP網路時間服務器設備采用冗余架構設計，高精度時鐘直接來源于北斗 ......

    uj5u.com 2020-09-10 03:52:35 more
  • 詳細解讀電力系統各種對時方式

    詳細解讀電力系統各種對時方式 詳細解讀電力系統各種對時方式 安徽京準電子科技官微——ahjzsz，更多資料請添加VX 衛星同步時鐘是我京準公司開發研制的應用衛星授時時技術的標準時間顯示和發送的裝置，該裝置以M國全球定位系統（GLOBAL POSITIONING SYSTEM,縮寫為GPS）或者我國北 ......

    uj5u.com 2020-09-10 03:52:45 more
  • 如何保證外包團隊接入企業內網安全

    不管企業規模的大小，只要企業想省錢，那么企業的某些服務就一定會采用外包的形式，然而看似美好又經濟的策略，其實也有不好的一面。下面我通過安全的角度來聊聊使用外包團的安全隱患問題。 先看看什么服務會使用外包的，最常見的就是話務/客服這種需要大量重復性、無技術性的服務，或者是一些銷售外包、特殊的職能外包等 ......

    uj5u.com 2020-09-10 03:52:57 more
  • PHP漏洞之【整型數字型SQL注入】

    0x01 什么是SQL注入 SQL是一種注入攻擊，通過前端帶入后端資料庫進行惡意的SQL陳述句查詢。 0x02 SQL整型注入原理 SQL注入一般發生在動態網站URL地址里，當然也會發生在其它地發，如登錄框等等也會存在注入，只要是和資料庫打交道的地方都有可能存在。 如這里http://192.168. ......

    uj5u.com 2020-09-10 03:55:40 more
  • [GXYCTF2019]禁止套娃

    git泄露獲取原始碼 使用GET傳參，引數為exp 經過三層過濾執行 第一層過濾偽協議，第二層過濾帶引數的函式，第三層過濾一些函式 preg_replace('/[a-z,_]+\((?R)?\)/', NULL, $_GET['exp'] (?R)參考當前正則運算式，相當于匹配函式里的引數 因此傳遞 ......

    uj5u.com 2020-09-10 03:56:07 more
  • 等保2.0實施流程

    流程 結論 ......

    uj5u.com 2020-09-10 03:56:16 more
最新发布
  • 使用Django Rest framework搭建Blog

    在前面的Blog例子中我們使用的是GraphQL, 雖然GraphQL的使用處于上升趨勢,但是Rest API還是使用的更廣泛一些. 所以還是決定回到傳統的rest api framework上來, Django rest framework的官網上給了一個很好用的QuickStart, 我參考Qu ......

    uj5u.com 2023-04-20 08:17:54 more
  • 記錄-new Date() 我忍你很久了！

    這里給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 大家平時在開發的時候有沒被new Date()折磨過？就是它的諸多怪異的設定讓你每每用的時候，都可能不小心踩坑。造成程式意外出錯，卻一下子找不到問題出處，那叫一個煩透了…… 下面，我就列舉它的“四宗罪”及應用思考 可惡的四宗罪 1. Sa ......

    uj5u.com 2023-04-20 08:17:47 more
  • 使用Vue.js實作文字跑馬燈效果

    實作文字跑馬燈效果，首先用到 substring()截取 和 setInterval計時器 clearInterval()清除計時器 效果如下： 實作代碼如下： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta ......

    uj5u.com 2023-04-20 08:12:31 more
  • JavaScript 運算子

    JavaScript 運算子/運算子 在 JavaScript 中，有一些運算子可以使代碼更簡潔、易讀和高效。以下是一些常見的運算子： 1、可選鏈運算子（optional chaining operator） ?.是可選鏈運算子（optional chaining operator）。?. 可選鏈操 ......

    uj5u.com 2023-04-20 08:02:25 more
  • CSS—相對單位rem

    一、概述 rem是一個相對長度單位，它的單位長度取決于根標簽html的字體尺寸。rem即root em的意思，中文翻譯為根em。瀏覽器的文本尺寸一般默認為16px，即默認情況下： 1rem = 16px rem布局原理：根據CSS媒體查詢功能，更改根標簽的字體尺寸，實作rem單位隨螢屏尺寸的變化，如 ......

    uj5u.com 2023-04-20 08:02:21 more
  • 我的第一個NPM包:panghu-planebattle-esm(胖虎飛機大戰)使用說明

    好家伙,我的包終于開發完啦 歡迎使用胖虎的飛機大戰包!! 為你的主頁添加色彩 這是一個有趣的網頁小游戲包,使用canvas和js開發 使用ES6模塊化開發 效果圖如下: (覺得圖片太sb的可以自己改) 代碼已開源!! Git: https://gitee.com/tang-and-han-dynas ......

    uj5u.com 2023-04-20 08:01:50 more
  • 如何在 vue3 中使用 jsx/tsx?

    我們都知道,通常情況下我們使用 vue 大多都是用的 SFC(Signle File Component)單檔案組件模式,即一個組件就是一個檔案,但其實 Vue 也是支持使用 JSX 來撰寫組件的。這里不討論 SFC 和 JSX 的好壞,這個仁者見仁智者見智。本篇文章旨在帶領大家快速了解和使用 Vu ......

    uj5u.com 2023-04-20 08:01:37 more
  • 【Vue2.x原始碼系列06】計算屬性computed原理

    本章目標：計算屬性是如何實作的？計算屬性快取原理以及洋蔥模型的應用？在初始化Vue實體時，我們會給每個計算屬性都創建一個對應watcher，我們稱之為計算屬性watcher ......

    uj5u.com 2023-04-20 08:01:31 more
  • http1.1與http2.0

    一、http是什么 通俗來講，http就是計算機通過網路進行通信的規則，是一個基于請求與回應，無狀態的，應用層協議。常用于TCP/IP協議傳輸資料。目前任何終端之間任何一種通信方式都必須按Http協議進行，否則無法連接。tcp(三次握手，四次揮手)。 請求與回應：客戶端請求、服務端回應資料。 無狀態 ......

    uj5u.com 2023-04-20 08:01:10 more
  • http1.1與http2.0

    一、http是什么 通俗來講，http就是計算機通過網路進行通信的規則，是一個基于請求與回應，無狀態的，應用層協議。常用于TCP/IP協議傳輸資料。目前任何終端之間任何一種通信方式都必須按Http協議進行，否則無法連接。tcp(三次握手，四次揮手)。 請求與回應：客戶端請求、服務端回應資料。 無狀態 ......

    uj5u.com 2023-04-20 08:00:32 more

Copyright © 2010-2020 有解無憂