## Python 之父的解析器系列之五：左递归 PEG 语法 顶原荐

豌豆花下猫

【这是我的 PEG 系列的第 5 部分。其它文章参见这个目录

``````expr: expr '+' term | term
``````

``````def expr():
if expr() and expect('+') and term():
return True
if term():
return True
return False
``````

``````expr: term '+' expr | term
``````

``````expr: term ('+' term)*
``````

``````expr------------+------+
|              \      \
expr--+------+   '+'   term
|    \      \          |
expr   '+'   term        |
|            |         |
term           |         |
|            |         |
'foo'        'bar'     'baz'
``````

``````def expr():
if oracle() and expr() and expect('+') and term():
return True
if term():
return True
return False
``````

``````def expr():
if oracle_expr() and expect('+') and term():
return True
if term():
return True
return False
``````

``````saved_result = None
def oracle_expr():
if saved_result is None:
return False
return saved_result
def expr_wrapper():
global saved_result
saved_result = None
parsed_length = 0
while True:
new_result = expr()
if not new_result:
break
new_parsed_length = <calculate size of new_result>
if new_parsed_length &lt;= parsed_length:
break
saved_result = new_result
parsed_length = new_parsed_length
return saved_result
``````

``````def is_left_recursive(rule):
for alt in rule.alts:
if alt[0] == rule.name:
return True
return False
``````

``````def memoize(func):
def memoize_wrapper(self, *args):
pos = self.mark()
memo = self.memos.get(pos)
if memo is None:
memo = self.memos[pos] = {}

key = (func, args)
if key in memo:
res, endpos = memo[key]
self.reset(endpos)
else:
res = func(self, *args)
endpos = self.mark()
memo[key] = res, endpos
return res
return memoize_wrapper
``````

@memoize 装饰器在每个输入位置记住了前一调用——在输入标记符的（惰性）数组的每个位置，有一个单独的`memo` 字典。memoize_wrapper 函数的前四行与获取正确的`memo` 字典有关。

``````    def memoize_left_rec(func):
def memoize_left_rec_wrapper(self, *args):
pos = self.mark()
memo = self.memos.get(pos)
if memo is None:
memo = self.memos[pos] = {}
key = (func, args)
if key in memo:
res, endpos = memo[key]
self.reset(endpos)
else:
# Prime the cache with a failure.
memo[key] = lastres, lastpos = None, pos
# Loop until no longer parse is obtained.
while True:
self.reset(pos)
res = func(self, *args)
endpos = self.mark()
if endpos &lt;= lastpos:
break
memo[key] = lastres, lastpos = res, endpos
res = lastres
self.reset(lastpos)
return res
return memoize_left_rec_wrapper
``````

``````    @memoize_left_rec
def expr(self):
pos = self.mark()
if ((expr := self.expr()) and
self.expect('+') and
(term := self.term())):
return Node('expr', [expr, term])
self.reset(pos)
if term := self.term():
return Node('term', [term])
self.reset(pos)
return None
``````

``````            # Prime the cache with a failure.
memo[key] = lastres, lastpos = None, pos
``````

### 评论(1)

pyparsing语法解析心得

2012/12/04
5.7K
1
Python 之父考虑重构 Python 解释器​​​​​​​

7 月 22 日，Python 之父 Guido 在 Medium 上发表了他的第一篇博文《PEG Parser》。 在该文中，Guido 说他正在考虑使用 PEG Parser 代替现有的类 LL(1) Parser（名为pgen），来重构 Python 解...

oschina
07/26
10.4K
21
pyPEG 2.9.0 发布，PEG 解析器

pyPEG 2.9.0 实现了一个便携的方法来定义新的样式函数，而不会导致在 Python 2.7 下的语法错误；扩展了 csl() 函数概要，文档方面的小完善并对代码进行了清理。 pyPEG 是一个快速、简单的 Py...

oschina
2012/12/11
512
0
pyPEG 2.6.0 发布，PEG 解析器

pyPEG 2.6.0 发布，该版本在组合时如果判断语法有冲突便会自动增加空格，Gammer 类增加了一个 compose() 方法，同时修复了一些 bug。 pyPEG 是一个快速、简单的 Python 的 PEG 解析器。输出结...

oschina
2012/06/21
439
0

Aaron74
2015/11/03
3.6K
12

CSS3

wytao1995
13分钟前
1
0
Jmeter录制

1. 加HTTP(s) Test Script Recorder 2. 在 recorder下面加reocrding controller 3. 在HTTP(s) Test Script Recorder中设置下面几项 4. browser设置proxy, 注意端口要和step3中jmeter中的一致......

Rebecca_Hu
18分钟前
3
0
DIV+CSS忽悠前端小白

21分钟前
3
0
Win10子系统 linux（Ubuntu18.04） 安装Docker

1）原文件备份 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak 2）编辑源列表文件 sudo vim /etc/apt/sources.list 3）将原来的列表删除，添加如下内容（中科大镜像源） deb http...

jxldjsn
23分钟前
3
0
Ubuntu16.04安装Qt5.12.2

Ubuntu16.04安装Qt5.12.2 第一步：下载文件 https://download.qt.io/official_releases/qt/5.12/5.12.2/ 第二步：安装依赖库 sudo apt-get install build-essential sudo apt-get install li......

shzwork
29分钟前
5
0