Python 之父的解析器系列之四:可视化 PEG 解析
原题 | Visualizing PEG Parsing
作者 | Guido van Rossum(Python之父)
译者 | 豌豆花下猫(“Python猫”公众号作者)
声明 | 本翻译是出于交流学习的目的,基于 CC BY-NC-SA 4.0 授权协议。为便于阅读,内容略有改动。
上周我展示了一个简单的 PEG 解析器生成器。本周我将展示生成的解析器在解析程序时实际执行的操作。我深入研究了 ASCII 艺术的复古世界,特别是一个名为“curses”的库,它可以在 Linux 和 Mac 的 Python 标准库中找到,也可以作为 Windows 的附加组件。
【这是我的 PEG 系列的第 4 部分。见第1部分,第2部分,第3部分,第5部分 】(译注:对应的译文,第1篇、第2篇、第3篇、第5篇待译 )
让我们来看看可视化已取得的进展。截图里的屏幕被分隔为三个部分,分别是简单的 ASCII 字符,以及用连字符划出的线:
- 上部分显示了解析器的调用堆栈,你可能还记得它是一个具有无限回溯的递归下降解析器。我将在下面解释如何阅读它。
- 中间的单行部分展示了标记符缓冲区的内容,光标指向下一个要解析的标记符。
- 在底部,我们呈现 packrat 解析算法使用的记忆缓存。它的条目类似于一些解析器堆栈条目(具有结果的条目)。
阅读此图表时,要注意的主要事项是:顶部和底部部分的缩进线与标记符缓冲区相对应。(译注:最好看一下后面的 gif 动图,再往下看这部分内容。)
- 前两行(以
statement
和assignment
开头)表示尚未返回的解析方法调用,并且当标记位置处在第一个标记符('aap' )之前时调用。 - 接下来的两行(以
expr
和term
开头)与标记符'cat'
的开头垂直对齐,后者是调用相应解析方法的地方。 - 堆栈部分所显示的第五行和最后一行是一个
expect('/')
调用,它返回 None 。它是在标记符'+'
处被调用的。
缓存部分的条目的缩进也对应着标记符缓冲区的位置。例如,在底部,我们看到有负数缓存条目(negative cache entries)在标记符缓冲区的开头查找标记符'if'
以及规则if_statement
。我们还发现标记符'='
和NAME
(特别是'cat'
)所成功缓存的条目,它们与将来的输入位置相对应。
在显示出来的解析器堆栈和缓存中,已返回的调用被显示成function(args) -> result
。有时解析器堆栈也会显示几个已返回的方法——我这样做是为了减少显示时的“跳跃性”。
(说到“跳跃”,顶部显示的解析器堆栈会在一个调用被添加到堆栈时,向上移动,而当从堆栈中弹出一个调用时,它则向下移动。似乎我们的眼睛跟随这样的动作不会有太大问题——至少我没有。这很可能因为我们大脑中有一块区域是用于跟踪移动的物体。:-)
缓存被可视化为一种 LRU 缓存,最近使用过的缓存条目位于顶部,较少使用的项目则向屏幕底部掉落。(我在之前的帖子中展示的 packrat 解析器原型不使用 LRU,但它可能是改善其内存使用的好策略。)
让我们看一下解析堆栈在显示时的更多一些细节。前四个条目对应于尚未返回的解析方法,每一行显示了语法中的一行。带下划线的条目会引起下一次调用。
在这种情况下,我们看到我们处于 statement 的第二种选择,也即 assignment,并且在该规则中我们处于第三项,即 expr。在 expr 规则中,我们只是在第一个可选项的第一个条目(term '+' expr
);而在 term 规则中,我们处在最后的选项(atom
)。
在那之后,我们看到导致第二个选项(atom '/' term
)失败的结果:expect('/') - > None
用 '+' 标记符缩进。当我们将可视化向前移动时,我们会看到它沉入缓存中。
但当然了,你肯定宁愿自己看动画!我已经录制了示例程序的完整解析。你也可以自己玩代码,但请注意,这只是一个临时的黑科技。
当你在观看录制的GIF时,可能会感到有些迷惑,有时下一个标记符还未显示(例如,在最开始时,堆栈在标记符'aap'
被显示之前,就增长了几个条目)。
这正是解析器所看到的:标记符缓冲区被延迟地填充,并且在解析器通过调用 expect() 来请求它们之前,并不会扫描标记符。一旦标记符出现在缓冲区中,它就会保留在那里,即便在解析器回溯时也如此。
标记符缓冲区中的光标向左跳跃,显示了回溯过程;该动图中有很多次出现这种现象。你还可以在 gif 中观察到缓存填充,解析器在那不会进行额外的递归调用。(发现这种情况时,我应该加以强调,但我没时间了。)
下周我将进一步开发解析器,很可能会添加我对左递归语法规则的实现。(它们很棒!)
致谢:录制时所用的ttygif
(Ilia Choly 开发) 和 ttyrec
(Matthew Jording 开发)。
本文内容、示例代码和图片的授权协议:CC BY-NC-SA 4.0
英文原文:https://medium.com/@gvanrossum_83706/visualizing-peg-parsing-93a36f259423
作者简介: Guido van Rossum,Python 的创造者,一直是“终身仁慈独裁者”,直到 2018 年 7 月 12 日退位。目前,他是新的最高决策层的五位成员之一,依然活跃在社区中。本文出自他在 Medium 开博客所写的解析器系列,该系列仍在连载中,每周日更新。
译者简介: 豌豆花下猫,生于广东毕业于武大,现为苏漂程序员,有一些极客思维,也有一些人文情怀,有一些温度,还有一些态度。公众号:「Python猫」(python_cat)。
公众号【Python猫】, 本号连载优质的系列文章,有喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等等,欢迎关注哦。

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Istio 太复杂?KubeSphere基于Ingress-Nginx实现灰度发布
在 Bookinfo 微服务的灰度发布示例 中,KubeSphere 基于 Istio 对 Bookinfo 微服务示例应用实现了灰度发布。有用户表示自己的项目还没有上 Istio,要如何实现灰度发布? 在 Ingress-Nginx (0.21.0 版本) 中,引入了一个新的 Canary 功能,可用于为网关入口配置多个后端服务,还可以使用指定的 annotation 来控制多个后端服务之间的流量分配。 KubeSphere 在 2.0.2 的版本 中,升级了项目网关 (Ingress Controller) 版本至 0.24.1,支持基于 Ingress-Nginx 的灰度发布。 上一篇文章已经对灰度发布的几个应用场景进行了详细介绍,本文将直接介绍和演示基于 KubeSphere 使用应用路由 (Ingress) 和项目网关 (Ingress Controller) 实现灰度发布。 说明: 本文用到的示例 yaml 源文件及代码已上传至 GitHub,可 clone 至本地方便参考。 Ingress-Nginx Annotation 简介 KubeSphere 基于 Nginx I...
- 下一篇
go 学习笔记之万万没想到宠物店竟然催生出面向接口编程?
到底是要猫还是要狗 在上篇文章中,我们编撰了一则简短的小故事用于讲解了什么是面向对象的继承特性以及 Go 语言是如何实现这种继承语义的,这一节我们将继续探讨新的场景,希望能顺便讲解面向对象的接口概念. 为了照顾到没有看过上一节文章的读取,这里再简述一下上节文章关于买宠物的故事,如需详细了解,请自行翻阅历史文章进行查看. A: 猫是一种宠物,淘气可爱会卖萌,看家本领抓老鼠,偶尔还会喵喵喵. B: 狗是一种宠物,忠实听话能看家,嗅觉灵敏会破案,一言不合汪汪汪. C: 我想要买一个宠物,文能卖萌,武可退敌,明个一早给我送来吧! 于是,第二天,A和B各自带着自己的宠物来拜见C,并附上各自的理由,说的头头是道,C总觉得有些哪里不对,可一时间又无言反驳,只能悻悻收下了猫和狗,白白多花了一份钱! 这则故事很简单,但同时也暴露出一个问题,那就是在这场交易中,卖家实际上亏了,明明只是想买一个宠物,结果却买了两个! 当然,在上篇文中最后也给出了解决方案,那就是将猫和狗进行抽象封装,共性的部分提取成宠物,个性的部分才是猫和狗. 如此一来,顾客买宠物时要么买的是猫,要么面对是狗,具体买的是什么宠物是由顾客自己...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- 设置Eclipse缩进为4个空格,增强代码规范
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7设置SWAP分区,小内存服务器的救世主
- Docker安装Oracle12C,快速搭建Oracle学习环境