最新要闻
- 骁龙7+处理性能加持:Redmi Note 12 Turbo拍照加速50%
- 李彦宏:百度文心一言和ChatGPT差距也就一两个月
- 每日消息!虚幻5再次炸场!1部iPhone搞定3A大作级动作捕捉 游戏行业要变天
- 【全球快播报】高校回应考生因航班延误错过复试:通知合规 可按流程重新参加
- 天天视点!中国火箭回收新进展:每年可节省十几亿元
- 视焦点讯!支持Win7运行最后版本:U盘软件Rufus 3.22正式发布
- 女子家中开氛围灯外面看如同着火 引来消防员场面十分尴尬
- 信息:003至薄套壁 杰士邦避孕套0.66元/枚狂促
- 世界热讯:永安林业:副董事长辞职
- 环球观速讯丨肝帝玩家!《暗黑破坏神4》公测玩家达成全职业满级
- 男子高速奇葩操作:头上竟然套了一个“车顶”
- 热点评!股票除权日在什么时候
- 环球观焦点:阿什莉动捕演员庆祝《生化危机4:重制版》发售 身穿黑丝超吸睛
- 今日精选:网络爽文改编 《赘婿》动画定档4月23日B站开播
- 全球球精选!加拿大旅游团费_加拿大旅游费用
- 小米顶级自研技术!Redmi Note 12 Turbo用上小米影像大脑
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
热门:JS 做一个简单的 Parser
前言
前些天偶然看到以前写的一份代码,注意有一段尘封的代码,被我遗忘了。这段代码是一个简单的解析器,当时是为了解析日志而做的。最初解析日志时,我只是简单的正则加上分割,写着写着,我想,能不能用一个简单的方案做个解析器,这样可以解析多种日志。于是就有了这段代码,后来日志解析完了,没有解析其它日志就给忘了。再次看到这段代码,用非常简单易读的代码就实现了一个解析器,觉得非常值得分享。
思路
言归正传,这个简单的解析器是怎么构思的呢?那要先从模式匹配开始。解析与模式匹配有很多相似之处,比如解析一个整数,跟匹配一个整数就是相似的。都需要根据整数的文法 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" trueconsole.log(...match_a("def")); // "def" false const match_abc = seq([match("a"), match("b"), match("c")]);match_abc("abc");console.log(...match_abc("abc")); // "" trueconsole.log(...match_abc("abd")); // "abd" false
妙极了!
拥抱正则表达式
接下来,我们可以在这个基础上实现正则表达式的其它模式,比如:
alt
。候选列表,列表中有一个匹配成功则成功,一个失败则整体失败。是正则表达式中是|
和[]
。opt
。可选,正则表达的?
模式。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")); // "" 3console.log(...Exp("5-3")); // "" 2
现在是不是更妙了。
完全体
光有 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 Valconst 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}
怎么样,相当不错吧!!!
接下来再演示下进阶版本的表达式解析与求值,支持加、减、乘、除和括号:
// Factor = "(" ws Exp ws ")" | Numconst 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 的实用性,在日常的小脚本中,更加体现它的小巧、易懂、功能强大。不过也要注意的是,我是以小巧、简易为目标实现的,所以性能不是首要目标,将本文的实现用于性能挑剔的场合肯定是不合适的。
关键词:
热门:JS 做一个简单的 Parser
【全球新视野】SCO音频采集
骁龙7+处理性能加持:Redmi Note 12 Turbo拍照加速50%
李彦宏:百度文心一言和ChatGPT差距也就一两个月
每日消息!虚幻5再次炸场!1部iPhone搞定3A大作级动作捕捉 游戏行业要变天
【全球快播报】高校回应考生因航班延误错过复试:通知合规 可按流程重新参加
天天视点!中国火箭回收新进展:每年可节省十几亿元
快看点丨yolov5训练自己的数据集
环球关注:有监督学习——决策树、集成学习
每日播报!定时任务的路径问题
视焦点讯!支持Win7运行最后版本:U盘软件Rufus 3.22正式发布
女子家中开氛围灯外面看如同着火 引来消防员场面十分尴尬
信息:003至薄套壁 杰士邦避孕套0.66元/枚狂促
世界热讯:永安林业:副董事长辞职
今日快看!简单部署halo博客
微速讯:Qt源码阅读(二) moveToThread
AES之CryptoJS加密与C#解密
环球观速讯丨肝帝玩家!《暗黑破坏神4》公测玩家达成全职业满级
男子高速奇葩操作:头上竟然套了一个“车顶”
热点评!股票除权日在什么时候
【环球新视野】软件测试--详细判断电话号码
前端设计模式——计算属性模式
世界速递!PLG SaaS 案例:如何实践外链自动增长策略?
需求分析报告(软件项目)
每日播报!Android中常见的线程池
环球观焦点:阿什莉动捕演员庆祝《生化危机4:重制版》发售 身穿黑丝超吸睛
今日精选:网络爽文改编 《赘婿》动画定档4月23日B站开播
全球球精选!加拿大旅游团费_加拿大旅游费用
小米顶级自研技术!Redmi Note 12 Turbo用上小米影像大脑
世界观点:.NET6+Quartz实现定时任务
当前观察:logback的使用和原理
【新视野】GPT已长出眼睛耳朵 周鸿祎:人工智能将会产生意识
环球看热讯:状态观测器(一)
看点:苏州天使母基金合作子基金接连完成投资
曹德旺谈人工智能:能做饭吃吗?如果大家都去研究会饿死
当前看点!南方新一轮强降雨将上线!北方大部气温“狂飙” 最高飙到25度
今日观点!12款随便挑 太平鸟印花T恤清仓:到手69元
全球观热点:苹果WWDC 2023日期曝光!iOS 17首秀来了:或不再支持iPhone X/8
广东突降冰雹 多车被砸毁容!保险给赔吗?
事关出生证明、免税购物、高铁新路线!4月一大波新规来了
精选!AMD新一代APU曝光:大小核架构终于上了
动态:我国首次实现固态氢能发电并网,“绿电”与“绿氢”灵活转换
易烊千玺代言!九号电动两轮车国内出货突破150万辆
转型电动化 韩系车在中国还有救吗?
老人故意推倒摩托车案胜诉 老人儿子需赔1.6万!车主回应
全球关注:读Java性能权威指南(第2版)笔记28_线程和同步性能中
速讯:孤芳自赏是哪一期蒙面唱将
【全球热闻】“韩国宾利”能拿下中国人吗?
焦点观察:票房破40亿中国影史第10!《流浪地球2》4月14日上线咪咕视频
焦点快看:叙利亚外交部谴责美国对叙发动敌对行动
使用 Linux dd 命令测试磁盘读写性能
国际短信平台接口调用的方法步骤,简单5步快速教程
全球信息:Java之大数加减乘除——构建类
张译包场张颂文的新电影《不止不休》!猫眼评分9.3分
世界快消息!2026年亚运会将不建设运动员村:为了削减开支
焦点资讯:3年来最盛大红毯叫停:邓超激动得像买票进场 胡歌刘亦菲杨幂同框梦回仙剑
当前速看:国内这些城市地标为地球熄灯一小时:有你认识的吗?
小米OPPO和vivo实现突破性跨越!微信聊天记录能互相迁移了
天天微资讯!武汉一小伙考研出分后失眠多日,医生支招制定减压计划
linux中conda虚拟环境使用(便于项目切换)、pip和conda换源
原来熊猫的笑声这么粗犷吗 网友直呼没想到:公鸭嗓笑的像反派
天天讯息:被马斯克16亿垄断的工艺 卡了下游企业的脖子
天天热点评!女孩穿汉服乘公交:颜值惊艳众人
环球视点!液体钙和钙片哪个更容易吸收(液体钙和钙片哪个更好吸收)
python 使用 kafka
世界观点:《暗黑4》与《暗黑3》角色截图对比:女性角色更逼真了
捐100亿建大学 曹德旺:我赚了很多钱但不贪婪 会还给社会
女子摔跤上牙磕进嘴唇1月后才发现 医生惊叹不已:网友直呼心太大
徕卡+双长焦史无前例!小米13 Ultra曝光
焦点信息:Vue——initState【十】
当前信息:国外短信平台收不到验证码,怎么解决?
今日快看!什么叫针灸师
全球热文:红心番石榴吃法?
130余年老字号 非遗工艺 吴裕泰特种级茉莉香毫100g装40元
热资讯!灵隐寺旁小溪中大量放生乌龟死亡被吐槽是伪善 放生已成产业链最高2000元一次
【独家焦点】干旱缓解 新疆最大湖泊变了:阿雅克库木湖30年面积扩大近7成
焦点速讯:WPF 入门基础
周鸿祎与库克共话科技未来:惟一被淘汰的是不会用GPT的人
天天观点:12小时保温保冷 朴原良品316不锈钢保温杯16.9元起
世界快讯:代码漏洞暴露用户支付信息 ChatGPT安全存隐患:官方致歉
世界速讯:聚焦险企负债成本管理 监管座谈会释放调整信号
AMD Yes!Zen4回归骨折价 12核锐龙9 7900到手2549元
学生党福音 Redmi小金刚Note 12 Turbo的NFC卡升级:两大功能合体
当前资讯!mp3格式转换器哪个好_mp3格式转换器
dotnet-csharp
焦点精选!C++ sizeof与strlen,并借此明晰内存对齐
女生靠摆地摊还清百万负债 还有人两周赚1万5、月入万元:摆摊真这么赚钱?
【天天速看料】周鸿祎:中国与GPT-4差距两三年 不存在难以逾越技术障碍
当前热文:Windows OpenGL ES 图像 GPUImageAmatorkaFilter
javascript的基础知识
小彭汽车向小鹏汽车道歉:盘点那些神级模仿的老年代步车
【速看料】《三体》动画今日正式完结!豆瓣评分仅3.8:半数一星差评
焦点关注:998的比亚迪秦PLUS DM-i多能跑?博主极端工况实测:合资还怎么打
当前关注:Office2019永久激活工具_Office2019激活工具神龙版v2023.2
天天快播:What is static and dynamic libraries
[白嫖系列] 白嫖一个永久免费的eu.org域名
速看:76人攻防俱佳夺冠有望,湖人防守第一进攻拉胯,勇士卫冕基本无望
全球新资讯:女子模仿网红穿搭遭对方粉丝网暴!法院判网红连续15天道歉、赔偿
男子喝红牛味道不对发现是累牛引热议:康帅傅、雷碧等山寨货为何层出不穷
资讯推荐:关于aws-s3-bucket-静态网站托管相关的查询-S3.Client.get_bucket_website(**kwargs)