仅出于对PEG的部分理解的启发，我决定尝试实施它。 结果可能不是通用PEG解析器中最好的-已有很多（例如，TatSu用Python编写并生成Python代码）-但这是理解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
当然，这是一个过于简单的示例：它忽略了重要的细节，例如，什么输入该函数的输入以及执行结果将是什么。
让我们从参数开始。 经典解析器使用单独的令牌生成器，它将输入（文本文件或行）拆分为一系列令牌，例如关键字，标识符（名称），数字和运算符。 PEG解析器（像其他现代解析器一样，如ANTLR）通常将令牌化和解析结合在一起，但是对于我的项目，我决定保留单独的令牌化器。
Python标记化非常复杂，因此我不想在PEG规则上实现它。 例如，您应该跟踪缩进（这需要在令牌生成器内部堆叠）； 用Python处理换行符也很有趣（除了包含在相应括号中的换行符，它们非常重要）。 许多类型的字符串也会引起一些复杂性。 简而言之，我对现有的Python标记器没有任何抱怨，因此我想保持现状。 顺便说一句，CPython有两个标记器：内部的一个由解析器使用，它是用C编写的，而标准的库是一个用纯Python实现的精确副本。 这将在我的项目中派上用场。
典型的令牌生成器通常具有一个简单的接口，该接口由单个get_token()函数组成。 每次，它返回输入序列中的下一个标记，分析一组字符。 CPython的tokenize模块也不例外：其核心API是一次生成一个令牌的生成器。 每个令牌都是TypeInfo类型的对象，该对象具有多个字段，其中最重要的是令牌的类型（例如NAME ， NUMBER ， STRING ），其字符串值是其组成的字符集（例如abc ， 42或"Hello, world" 。 也有其他字段。 例如，对于输入流中的令牌索引，这在错误消息中很有用。
令牌的一种特殊类型是ENDMARKER ，它指示已到达输入文件的末尾。 如果您忽略生成器并尝试获取下一个令牌，则生成器将崩溃。
但是我分心了。 我们如何实现无限收益？ 回滚令牌列表要求您能够记住源代码中的位置并从该位置重新进行分析。 tokenizer API不允许我们移动其指针，但是您可以将令牌流捕获到数组中并从那里播放，我们将这样做。 您也可以使用itertools.tee()重复此操作，但是如果您查看文档中的警告，则在我们的情况下这可能不太有效。
我想您可以先标记所有输入到列表中，然后将其用作解析器的输入。 但是，如果文件末尾有一个无效的令牌（例如，结尾的引号缺失的行），并且文件中还存在语法错误，那么首先您将从令牌生成器收到一条错误消息。 我认为这对用户不利，因为语法错误可能是无效行的主要原因。 因此，我对令牌生成器的要求略有不同，特别是应将其实现为惰性列表。
核心API非常简单。 令牌生成器对象封装令牌数组和该数组中的位置。 他有三种主要方法：
get_token()返回下一个令牌，移动指针（或者，如果我们在令牌缓冲区的末尾，则从源中读取下一个令牌）；mark()返回缓冲区中的当前位置；reset(pos)设置缓冲区中的位置（必须从mark()获得参数）。
我们添加了一个辅助函数peek_token() ，该函数返回下一个标记，而不移动缓冲区中的位置。
这是Tokenizer类的基础：
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
这里，为简单起见，省略了一些内容（例如，方法和实例变量的名称必须以下划线开头），但这只是Tokenizer API的原型。
解析器还必须成为一个类，以便statement() ， expr()等。 可以实现为方法。 标记生成器将成为实例变量，但我不希望解析器方法直接调用get_token() -相反，我们在Parser类中实现了wait()方法，该方法可以像解析器方法一样成功或失败。 wait()函数的参数是预期的令牌：字符串（例如+ ）或令牌的类型（例如NAME ）。 返回值的类型并不重要，我将在讨论解析器的工作结果之后再返回它。
现在让语法规则函数仅返回True或False 。 这对理论计算机科学很有用（解析器回答问题“这是语言中的有效字符串吗？”），但对我们而言不是。 我们的任务是创建一个AST。 因此，让我们重写此代码，以便每个分析方法成功时都返回Node对象，失败时则返回None 。
Node类可以非常简单：
class Node: def __init__(self, type, children): self.type = type self.children = children
在这里， type确定AST节点的类型（例如， add或if ），后代是节点和令牌（ TokenInfo实例）的列表。 这足以使编译器生成代码或执行其他分析，例如整理或静态类型检查。 尽管将来我想更改AST的显示方式。
为了适合此方案， expect()方法必须在成功时返回TokenInfo对象，而在失败时返回None 。 为了能够回滚到以前的标记，我将对mark()和reset()方法的调用进行了包装（此处的API不变）。 这是发生了什么：
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
再一次：我省略了一些细节，但这已经是正常工作的代码。
现在，我需要介绍解析器方法的一项重要要求。 每个人都应该返回Node ，将令牌生成器放置在他们所识别的语法规则的最后一个令牌之后； None或保留令牌生成器的位置不变。 如果解析器方法读取多个令牌然后掉落，则它必须恢复令牌生成器的位置。 为此，需要使用mark()和reset() 。 请注意， expect()也遵守此规则。
因此，这是实际解析器的草图。 在这里，我使用Python 3.8（ := ）中的walrus运算符：
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
我省略了一些方法的实现，以便读者有机会练习自己。 这确实比仅阅读有关如何实现这种解析器的方法更好。 最后，我们将根据语法自动生成此类代码。 常量（例如NAME和NUMBER是从标准库的token模块中导入的。 这进一步将我们与Python标记器的当前实现联系在一起。 如果我们要创建通用的PEG解析器，则必须找到避免这种情况的方法。
另请注意，我有点被骗。 expr方法必须为左递归，但我使解析器为右递归，因为递归下降解析器不适用于左递归语法规则。 这个问题可以解决，但仍然是一些科学研究的主题，我想单独谈一谈。 请记住，此实现与我们的简化语法并非100％一致。
到目前为止，我希望您理解的关键事项：
- 语法规则对应于解析器方法，当语法规则引用另一个规则时，它将调用另一个规则的方法。
- 当令牌的序列可以不同地解释时，相应的解析器方法将被依次调用。
- 当语法规则引用标记时，该方法将调用
expect()函数。 - 如果解析器在当前位置成功识别出其语法规则，则返回相应的AST节点； 如果他不能识别语法规则，则返回
None 。 - 解析器方法在使用一个或多个令牌（直接或间接调用另一种成功的解析方法）后停止解析时，应显式重置令牌生成器的位置。 这不仅适用于拒绝一个选项以继续进行下一个选项的情况，而且适用于整个分析都被拒绝的情况。
如果所有解析方法都遵循这些规则，则无需将它们包装在mark()和reset()调用中。 这可以通过归纳证明。
此外，尝试使用上下文管理器和with语句摆脱对mark()和reset()的显式调用的尝试很诱人，但是它不起作用：如果成功，则不应调用reset() ！ 作为进一步的解决方案，您可以尝试对控制流使用异常，以便上下文管理器知道是否应重置令牌生成器（我认为TatSu正在执行类似的操作）。 例如，如下所示：
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
尤其是， atom()用于识别方括号中的表达式的if的小阶梯可以写成：
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
但是在我看来，这也太“神奇了”-阅读此类代码时，您应该记住，每种解析方法（包括wait() ）都可能引发异常。 并且上下文管理器在with语句中捕获并忽略了此异常。 尽管可以实现（通过从__exit__返回True ），但这是非常不寻常的。 但是，我的最终目标是用C而不是Python生成代码，并且在C中没有with语句来更改控制流。
无论如何，这是以下部分的一些主题：
- 从语法生成解析器方法；
- packrat解析（记忆）；
- EBNF功能，例如
(x | y) ， [xy ...] ， x* ， x+ ; - 跟踪（用于调试解析器或语法）；
- PEG特性，例如前瞻和剪切；
- 如何处理左递归规则；
- C代码生成
本文和引用代码的许可： CC BY-NC-SA 4.0