Генерация PEG-парсера
Oct 21, 2019 18:33 · 1345 words · 7 minute read
Оригинал: ‘Generating a PEG Parser’ by Guido van Rossum
Теперь, когда я набросал основу самописного парсера, давайте перейдём к генерации его методов из грамматики, как я и обещал. Также покажу как реализовать packrat-парсер с помощью декоратора @memoize.
Содержание серии статей о PEG-парсере в Python
В прошлый раз мы разобрали несколько методов парсера. С некоторыми ограничениями, которые мы снимем чуть позже, их легко генерировать из грамматики автоматически.Нам нужны две вещи: что-то, что читает грамматику и строит соответствующую структуру данных; и что-то, что берёт эту структуру данных и генерирует синтаксический анализатор. Нам также нужны и другие вспомогательные методы, но они не интересны, так что я их опущу.
Итак, мы создаем простой компилятор компилятора. Я немного упрощу грамматическую нотацию до такой степени, чтобы у нас остались только правила и альтернативы; этого на самом деле достаточно для той игрушечной грамматики, которую я использовал в предыдущих частях:
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 # <------------- final result
self.reset(pos)
return None
def rule(self):
pos = self.mark()
if name := self.expect(NAME):
if self.expect(":"):
if alt := self.alternative():
alts = [alt]
apos = self.mark()
while (self.expect("|")
and (alt := self.alternative())):
alts.append(alt)
apos = self.mark()
self.reset(apos)
if self.expect(NEWLINE):
return Rule(name.string, alts)
self.reset(pos)
return None
def alternative(self):
items = []
while item := self.item():
items.append(item)
return items
def item(self):
if name := self.expect(NAME):
return name.string
if string := self.expect(STRING):
return string.string
return None
Обратите внимание на использование ENDMARKER. Там я убеждаюсь, что после последнего правила ничего не осталось (а это может случиться, если в грамматике есть опечатка). Также я указал на место, где метод grammar() возвращает список правил. Всё остальное очень похоже на класс ToyParser из прошлой статьи, поэтому я не буду на нём останавливаться. Просто обратите внимание, что item() возвращает строку, alternative() возвращает список строк, а переменная alts внутри rule() собирает список списков строк. Затем метод 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
Как и в других декораторах, она содержит вложенную функцию, которая заменит (или обернёт) декорируемую, например, метод statement() класса ToyParser. Поскольку оборачиваемая функция является методом, враппер также фактически является методом: его первый аргумент называется self и ссылается на экземпляр ToyParser, для которого вызывается декорированный метод.
Враппер кэширует результат вызова метода для каждой входной позиции - вот почему он называется packrat-парсер! [прим. пер. packrat - “воришка”, однако в рускоязычных источниках этот термин не переводится] Кэш - это словарь словарей, который хранится в экземпляре Parser. Ключ внешнего словаря - позиция в потоке входных данных; я добавил также self.memos = {} в Parser .__ init__() для его инициализации. Внутренние словари добавляются по мере необходимости; их ключи состоят из метода и его аргументов. (В текущем дизайне нет аргументов, но мы могли бы мемоизировать функцию expect(), у которой он есть, весьма тривиально)
Результат работы метода парсера представляется в виде кортежа, поскольку там действительно два значения: собственно результат (для наших сгенерированных методов это Node для совпавшего правила) и указатель на текущую позицию во входном потоке, которую мы получаем из self.mark(). Таким образом, мы кэшируем как возвращаемое значение (res), так и новую позицию (endpos) во внутреннем словаре с мемоизированными значениями. При последующих вызовах того же метода синтаксического анализа с теми же аргументами в той же позиции входных данных мы будем брать их из кэша. Для этого достаточно всего лишь перевести указатель на позицию ввода с помощью self.reset() и посмотреть в кэш.
Также важно кэшировать и отрицательные результаты - на самом деле большинство вызовов будут негативными. В этом случае возвращаемое значение равно None, а позиция ввода не изменяется. Вы можете добавить assert, чтобы проверить это.
Примечание. В Python принято реализовывать кэш в локальной переменной в функции memoize(). В нашем случае так не получится: как я выяснил в самом конце отладки, каждый экземпляр Parser обязан иметь свой собственный кэш. Тем не менее, вы можете избавиться от вложенных словарей, используя (pos, func, args) в качестве ключа.
На следующей неделе я подготовлю код и трейсы, чтобы показать, как всё это на самом деле собирается и выполняется при разборе примера программы. Я всё еще в поисках лучшего способа визуализации совместной работы буфера токенизации, парсера и кэша. Возможно, мне удастся создать анимированный gif в ASCII вместо того, чтобы просто выводить листинги трассировки в виде текста.
Лицензия на эту статью и приведенный код: CC BY-NC-SA 4.0