现在，我已经概述了专有解析器的基础，让我们继续按照我的承诺，从语法生成其方法。 我还将展示如何使用@memoize装饰器实现packrat解析器。
上一次，我们研究了一些解析器方法。 由于有些限制我们稍后会删除，因此很容易自动从语法中生成它们。
我们需要两件事：读取语法并建立适当数据结构的东西； 以及采用此数据结构并生成解析器的对象。 我们还需要其他辅助方法，但是它们并不有趣，因此我将省略它们。
因此，我们正在创建一个简单的编译器编译器。 我将在某种程度上简化语法符号，使其仅具有规则和替代方式。 这实际上足以满足我在前面各部分中使用的玩具语法：
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
使用完整的符号，我们可以将语法描述为：
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
这是我们的第一个元语法（语法为语法），解析器生成器将为元编译器（编译器为将程序从一种语言翻译为另一种语言的程序；元编译器为输入为语法的编译器，并且输出是解析器）。
描述元语法的一种简单方法是仅使用内置数据类型：规则的右侧是元素列表的列表，每个元素列表都可以只是一个字符串。 （顺便说一下，我们可以通过检查第一个字符是否是引号来分隔NAME和STRING ）
对于规则，我使用简单的Rule类，整个语法是此类对象的列表。 这是Rule类，不包括__repr__和__eq__ ：
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
这是使用它的GrammarParser类：
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
注意ENDMARKER的使用。 在那里，我确保在最后一条规则之后没有剩下任何东西（如果语法中有错字，可能会发生这种情况）。 我还指出了grammar()方法返回规则列表的地方。 其他所有内容都与上一篇文章中的ToyParser类非常相似，因此我将不再ToyParser 。 只需注意item()返回一个字符串， alternative()返回一个字符串列表， rule()内的变量alts收集一个字符串列表列表。 然后， rule()方法组合规则（字符串）的名称，并将其转换为Rule对象。
如果我们将此算法应用于玩具语法，则grammar()方法将返回以下规则列表：
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
现在我们有了元编译器的解析部分，让我们创建一个代码生成器。 它们一起构成了基本的元编译器：
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
这段代码很丑陋，但是可以（有点）起作用，将来我仍然会重写它。
for alt in rule.alts内的某些行可能需要说明：对于替代方案中的每个元素，我们选择3个选项之一：
- 如果元素是字符串文字，例如
'+' ，则生成self.expect('+') - 如果元素是完全大写的，例如
NAME ，则生成(name := self.expect(NAME)) - 否则，例如，如果它是
expr ，则我们生成(expr := self.expr())
如果一个变体中有多个具有相同名称的元素（例如， term '-' term ），那么我们在第二个变量中添加一个数字。 这里还有一个小错误，我将在下一集中纠正。
这是他工作的结果（整个班级会很无聊）。 不必担心需要多余的if (True and ... )代码，以便每个生成的条件都可以以and开头。 Python字节编译器对此进行了优化。
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
请注意@memoize装饰器：我将其引入到另一个主题：使用备忘录使生成的解析器足够快。
这是实现此装饰器的memoize()函数：
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
与其他装饰器一样，它包含一个嵌套函数，该函数替换（或包装）一个装饰函数，例如ToyParser类的statement()方法。 由于要包装的函数是一个方法，因此包装器实际上也是一个方法：其包装的第一个参数称为self并引用为其调用装饰方法的ToyParser实例。
包装器为每个输入位置缓存方法调用的结果-这就是为什么它被称为packrat解析器！ [大约 反式 packrat是“小偷”，但未在俄语语言中翻译此术语。] Cache是字典的字典，存储在Parser实例中。 外部词典的关键字是输入数据流中的位置。 我还添加了self.memos = {}到Parser .__ init__()进行初始化。 根据需要添加内部词典； 它们的键由一个方法及其参数组成。 （当前设计中没有参数，但是我们可以记住带有一个的Expect expect()函数，这是非常琐碎的）
解析器方法的结果以元组的形式表示，因为实际上有两个值：结果本身（对于我们生成的方法，这是匹配规则的Node ）和一个指向输入流中当前位置的指针，这是我们从self.mark() 。 因此，我们在内部字典中使用返回值来缓存返回值（ res ）和新位置（ endpos ）。 在随后使用相同参数在相同输入位置调用相同解析方法的情况下，我们将从缓存中获取它们。 为此，只需使用self.reset()将指针移至输入位置，然后查看缓存即可。
缓存负面结果也很重要-实际上，大多数调用将是负面的。 在这种情况下，返回值为None ，并且输入位置不变。 您可以添加assert来检查。
注意事项 在Python中，习惯上在memoize()函数的局部变量中实现缓存。 在我们的例子中，这是行不通的：正如我在调试结束时发现的那样，每个Parser实例必须具有自己的缓存。 但是，您可以使用（ pos ， func ， args ）作为键来消除嵌套字典。
下周，我将准备代码和跟踪记录，以显示在解析示例程序时如何实际组装和执行所有这些操作。 我仍在寻找一种更好的方法来可视化标记化缓冲区，解析器和缓存的协作。 也许我将能够以ASCII格式创建动画gif，而不仅仅是将跟踪列表显示为文本。
本文和引用代码的许可： CC BY-NC-SA 4.0