Python 之父的解析器系列之六:给 PEG 语法添加动作
花下猫语:Guido 的解析器系列更新了 7 篇,他的生产力真旺盛啊。这对于新的解析器来说是件好事,但对于我来说却是个不小的挑战:需要一定的时间和精力,而我对解析器的知识极为欠缺,也造成了翻译过程的不顺畅。
现在,我把译文提到 Github 上了(guido_blog_translation),希望有热心肠的同学能来帮忙审阅指正,或者认领翻译任务吧。最后,提前祝大家中秋节快乐,阖家团圆,诸事和美。
声明 | 本翻译是出于交流学习的目的,基于 CC BY-NC-SA 4.0 授权协议。为便于阅读,内容略有改动。
如果你在语法规则中还可以添加(某些)语义,那么语法就会更好。特别是对于我正在构建的 Python 解析器,我需要控制每个备选项返回的 AST 节点,因为 AST 的格式已经规定好。
【这是我的 PEG 系列的第 6 部分。其余部分请参阅系列概述】(译注:本系列的译文已在 Github 开源,项目地址:https://github.com/chinesehuazhou/guido_blog_translation)
许多语法都有支持给规则添加动作的约定,通常是 { 花括号 } 内的一段代码块。更确切地说,行动与备选项相关联。动作块中的代码通常与编写编译器的语言相同,如 C 语言,增加一些工具,用于引用备选项中的条目。在 Python 原始的 pgen 中,我没有添加此功能,但对于这个新项目,我希望使用它。
对于在这一系列博客文章中开发的简化版解析器生成器,下面是我们采用的做法。
一般而言,动作的语法如下:
rule: item item item { action 1 } | item item { action 2 }
因为它会使语法变得冗长,所以解析器生成器通常支持跨行分割规则,例如:
rule: item item item { action 1 } | item item { action 2}
它会使语法分析器变得复杂,但可读性更重要,所以我会使用这种方式。
一个永恒的问题是何时执行动作块。在 Yacc / Bison 中,因为没有回溯,一旦规则被解析器识别到,就会执行动作块。每个动作会立即执行,这意味着即使操作具有全局副作用,还是会顺利执行(例如更新符号表或其它编译器数据结构)。
在 PEG 解析器中,因为有无限回溯,我们有其它的选择:
- 延迟所有动作,直到解析完所有内容。这对我的目的没有用,因为我想在解析期间构造一个 AST。
- 只要识别出动作所对应的备选项就执行之,但要求操作代码是幂等的(即无论执行多少次,都具有相同的效果)。这意味着可以执行某个动作,但其结果最终会被丢弃。
- 缓存动作的结果,因此只有第一次在给定位置识别到备选项时,对应的动作才执行。
我要采用第三个选项——正好我们用 packrat 算法缓存东西,所以我们也可以缓存动作的结果。
关于 {花括号} 里面的内容,传统上是使用 C 语言,它约定用 $ 符号来引用已识别的备选项(例如,$1 引用第一个条目),并赋值给 $$ 以指示动作的结果。
在我看来这太老古董了(我记得曾在 Algol-60 中使用对函数名的赋值,来指定返回值),所以我会用一些更 Pythonic 的方式:在括号内,你需要放置一个单一的表达式,它的值是动作的值,而条目的引用则是一些简单的名称,给出着条目的文本。
举个例子,这是一个简单计算器,可作加减法:
start: expr NEWLINE { expr }expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term }term: NUMBER { float(number.string) }
当我们运行时,给定输入 100+50-38-70 ,它会识别出各部分并计算答案,计算成((100+50)-38)-70 ,当然得出结果为 42。
一个小细节:在term的动作中,变量number保存了一个TokenInfo对象,因此该动作必须使用其.string属性来获取字符串形式的标识符。
当一个备选项中多次出现相同的规则名称时,我们该怎么办?对同一备选项中出现的规则,解析器生成器会给出唯一的名称,即在随后出现的规则上添加 1、2 等等。例如:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
它的实现很无聊,所以我请你们 check out 代码 ,自己看看。试试这个:
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
可视化功能现在支持使用左右箭头键来回移动!
本文内容与示例代码的授权协议:CC BY-NC-SA 4.0
译者简介:豌豆花下猫,生于广东毕业于武大,现为苏漂程序员,有一些极客思维,也有一些人文情怀,有一些温度,还有一些态度。
©著作权归作者所有:来自51CTO博客作者mb5fdcaee2972df的原创作品,如需转载,请注明出处,否则将追究法律责任优质文章,推荐阅读:
Python 的整数与 Numpy 的数据溢出
编程语言之问:何时该借用,何时该创造?
GIL 已经被杀死了么?
Python进阶:设计模式之迭代器模式
更多相关文章
- 阅读优秀 Python 开源项目的代码,提升编程技能(GitHub 资源帖推荐)
- 非功能性需求,不要成为项目的坑
- 不仅模糊了Jquery中的一个动作
- 使用jquery tablesorter插件,有一个选中项目的下拉框
- 绑定和解除相同javascript函数的目的是什么?
- “for”属性的目的是什么?
- php 登陆动作详解
- php判断手机浏览还是web浏览,并执行相应的动作
- 无法在Yii中更改项目的文件夹名称