没有合适的资源?快使用搜索试试~ 我知道了~
(给Python开发者加星标,提升Python技能) 翻译:豌豆花下猫 (本文来自作者投稿) 译注:Python 之父在 Medium 上开了博客,现在写了两篇文章,本文是第二篇的译文。前一篇的译文 在此 ,宣布了将要用 PEG 解析器来替换当前的 pgen 解析器。 本文主要介绍了构建一个 PEG 解析器的大体思路,并介绍了一些基本的语法规则。根据 Python 之父的描述,这个 PEG 解析器还是一个很笼统的实验品,而他也预告了,将会在以后的系列文章中丰富这个解析器。 阅读这篇文章就像在读一篇教程,虽然很难看懂,但是感觉很奇妙:我们竟然可以见证 Python 之父如何考虑问题、如何作设计、
资源推荐
资源详情
资源评论
Python 之父:构建一个之父:构建一个 PEG 解析器解析器
(给Python开发者加星标,提升Python技能)
翻译:豌豆花下猫 (本文来自作者投稿)
译注:译注:Python 之父在 Medium 上开了博客,现在写了两篇文章,本文是第二篇的译文。前一篇的译文 在此在此 ,宣布了将要用 PEG 解析器来替换当前的 pgen 解析器。
本文主要介绍了构建一个 PEG 解析器的大体思路,并介绍了一些基本的语法规则。根据 Python 之父的描述,这个 PEG 解析器还是一个很笼统的实验品,而他也预告了,将会在以后的系列文章中丰富
这个解析器。
阅读这篇文章就像在读一篇教程,虽然很难看懂,但是感觉很奇妙:我们竟然可以见证 Python 之父如何考虑问题、如何作设计、如何一点一点地丰富功能、并且传授出来。这种机会非常难得啊!
我会持续跟进后续文章的翻译,由于能力有限,可能翻译中有不到位之处,恳请读者们批评指正。
仅仅理解了 PEG 解析器的小部分,我就受到了启发,决定自己构建一个。结果可能不是一个很棒的通用型的 PEG 解析器生成器——这类生成器已经有很多了(例如 TatSu,写于 Python,生成 Python
代码)——但这是一个学习 PEG 的好办法,推进了我的目标,即用由 PEG 语法构建的解析器替换 CPython 的解析器。
在本文中,通过展示一个简单的手写解析器,我为如何理解解析器的工作原理奠定了基础。通过展示一个简单的手写解析器,我为如何理解解析器的工作原理奠定了基础。
(顺便说一句,作为一个实验,我不会在文中到处放参考链接。如果你有什么不明白的东西,请 Google 之 :-)
最常见的 PEG 解析方式是使用可以无限回溯的递归下降解析器。
以上周文章中的玩具语言为例:
statement: assignment | expr | if_statement
expr: expr '+' term | expr '-' term | term
term: term '*' atom | term '/' atom | atom
atom: NAME | NUMBER | '(' expr ')'
assignment: target '=' expr
target: NAME
if_statement: 'if' expr ':' statement
这种语言中超级抽象的递归下降解析器将为每个符号定义一个函数,该函数会尝试调用与备选项相对应的函数。
例如,对于statement,我们有如下函数:
def statement():
if assignment():
return True
if expr():
return True
if if_statement():
return True
return False
当然这是极其简化的版本:没有考虑解析器中必要的输入及输出。
我们就从输入端开始讲吧。
经典解析器使用单独的标记生成器,来将输入(文本文件或字符串)分解成一系列的标记,例如关键字、标识符(名称)、数字与运算符。
(译注:标记生成器,即 tokenizer,用于生成标记 token。以下简称为“标记器”)
PEG 解析器(像其它现代解析器,如 ANTLR)通常会把标记与解析过程统一。但是对于我的项目,我选择保留单独的标记器。
对 Python 做标记太复杂了,我不想拘泥于 PEG 的形式来重新实现。
例如,你必须得记录缩进(这需要在标记器内使用堆栈),而且在 Python 中处理换行很有趣(它们很重要,除了在匹配的括号内)。字符串的多种引号也会增加复杂性。
简而言之,我不抱怨 Python 现有的标记器,所以我想保留它。(CPython 有两个标记器,一个是解析器在内部使用的,写于 C,另一个在标准库中,用纯 Python 重写。它对我的项目很有帮助。)
经典的标记器通常具有一个简单的接口,供你作函数调用,例如 get_token(),它返回输入内容中的下一个标记,每次消费掉几个字符。
tokenize 模块对它作了进一步简化:它的基础 API 是一个生成器,每次生成(yield)一个标记。
每个标记都是一个 TypeInfo 对象,它有几个字段,其中最重要之一表示的是标记的类型(例如 NAME 、NUMBER 、STRING),还有一个很重要的是字符串值,表示该标记所包含的字符(例如 abc 、42 或者 "hello world")。还有的字段会指明每个标记出现在输入文件中的坐标,这对于报告错误很有用。
有一个特殊的标记类型是 ENDMARKER ,它表示的是抵达了输入文件的末尾。如果你忽略它,并尝试获取下一个标记,则生成器会终结。
离题了,回归正题。我们如何实现无限回溯呢?我们如何实现无限回溯呢?
回溯要求你能记住源码中的位置,并且能够从该处重新解析。标记器的 API 不允许我们重置它的输入指针,但相对容易的是,将标记流装入一个数组中,并在那里做指针重置,所以我们就这样做。(你同样可以使用itertools.tee()来做,但是根据文档中的警告,在我们这种情况下,效率可能较低。)
我猜你可能会先将整个输入内容标记到一个 Python 列表里,将其作为解析器的输入,但这意味着如果在文件末尾处存在着无效的标记(例如一个字符串缺少结束的引号),而在文件前面还有语法错误,那你首先会收到的是关于标记错误的信息。
我觉得这是种糟糕的用户体验,因为这个语法错误有可能是导致字符串残缺的根本原因。
所以我的设计是按需标记,所用的列表是惰性列表。所以我的设计是按需标记,所用的列表是惰性列表。
资源评论
weixin_38677260
- 粉丝: 3
- 资源: 918
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功