# 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 =
if new_parsed_length <= 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 <= 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