[Из песочницы] Классические парсер-комбинаторы на Python
Парсером называется часть программы, которая из линейной последовательности простых данных строит более сложные структуры данных с учетом некоторой грамматики.
Определение класса Tree:
Опишем базовый класс, от которого будут наследоваться все парсеры:
Парсер Atom принимает один элемент и сопоставляет его с элементом во входной последовательности. В случае успеха возвращает лист, ассоциированный с этим элементом.
Парсер Concat принимает на вход два парсера. Сначала применяется левый парсер, затем — правый. Если он отрабатывает успешно, результат будет содержать лево- или право-ассоциативное дерево. Если один из них не разобрал свою часть последовательности, то вся комбинация возвращает неудачу.
Опишем парсер альтернативы. Парсер Alt принимает на вход два парсера. Он отрабатывает успешно, если успешно отработал левый или правый парсер.
Опишем опциональный парсер Opt. Если его аргумент отработал успешно, то возвращает результат, иначе все равно возвращает успех, но с заданным значением по умолчанию.
Парсер повторения Repeat работает пока не «сломается». Если аргумент не сработал ни разу, это тоже считается успехом.
Парсер Prog последовательно применяет, преданные ему, парсеры и возвращает результат указанного (по умолчанию последнего).
Парсер Lazy используется для описания рекурсивных парсеров. Он принимает на вход функцию без аргументов, которая возвращает парсер. Это связано с тем, что на момент описания парсер еще не определен и не может ссылаться на себя непосредственно.
Парсер LExp в некоторых случаях позволяет обойти левую рекурсию (к примеру, при разборе лево-ассоциативных операторов). Принимает на вход три парсера: для разбора левого элемента, разделителя и правого элемента. При отсутствии очередного разделителя возвращает результат.
Описанные выше, парсер-комбинаторы предоставляют удобный и гибкий инструментарий для создания парсеров. Конечно они не сравнятся с такими известными библиотеками, как Boost.Spirit, но для новичка написание собственной библиотеки парсеров позволит лучше разобраться в процессе парсинга, что зачастую вызывает недоумение.
Функциональные языки программирования позволяют описывать функции высших порядков, которые принимают в качестве аргументов и возвращают как результат другие функции.
Парсер-комбинаторы — известная техника создания парсеров, которая использует возможности функциональных языков программирования для динамического построения более сложных парсеров из простых по правилам некоторой грамматики.
На языке Python классические парсер-комбинаторы можно описать следующим образом. Определение парсеров будет осуществляется посредством описания классов. Каждый класс будет переопределять метод __call__, который и будет выполнять всю работу.
На вход парсеры будут принимать линейную последовательность некоторых данных (это может быть набор символов, токенов и т. п.) и начальную позицию, с которой следует начать разбор.
В качестве результата разбора будет возвращаться объект типа Res, который, в случае успеха, будет содержать часть разобранного AST (abstract syntax tree) и следующую позицию во входной последовательности, иначе — позицию элемента, который вызвал ошибку.
Определение класса Res:
class Res:
def __init__(self, subtree, pos):
self.subtree = subtre
self.pos = pos
def __str__(self):
return '(' + ', '.join((str(self.subtree), str(self.pos))) + ')'
def __bool__(self):
return self.subtree != None
Определение класса Tree:
class Tree:
def __init__(self, root = None, children = None):
self.root = root
if children == None:
self.children = []
else:
self.children = children
def __str__(self):
r = str(self.root)
c = ', '.join(str(c) for c in self.children)
if c:
r = '[' + r + ', ' + c + ']'
return r
Опишем базовый класс, от которого будут наследоваться все парсеры:
import abc
class Parser(metaclass = abc.ABCMeta):
@abc.abstractmethod
def __call__(self):
pass
def __lshift__(self, other): # переопределение оператора <<
return Concat(self, other, 1)
def __rshift__(self, other): # переопределение оператора >>
return Concat(self, other, 0)
def __or__(self, other): # переопределение оператора |
return Alt(self, other)
Парсер Atom принимает один элемент и сопоставляет его с элементом во входной последовательности. В случае успеха возвращает лист, ассоциированный с этим элементом.
class Atom(Parser):
def __init__(self, token):
self.token = token
def __call__(self, tokens, pos = 0):
if pos != len(tokens) and self.token == tokens[pos]:
return Res(Tree(tokens[pos]), pos + 1)
return Res(None, pos)
Парсер Concat принимает на вход два парсера. Сначала применяется левый парсер, затем — правый. Если он отрабатывает успешно, результат будет содержать лево- или право-ассоциативное дерево. Если один из них не разобрал свою часть последовательности, то вся комбинация возвращает неудачу.
class Concat(Parser):
def __init__(self, left, right, F = 0):
self.left = left
self.right = right
self.F = F # если F == 0 строиться лево-ассоциативное дерево, иначе – право-ассоциативное
def __call__(self, tokens, pos = 0):
left_res = self.left(tokens, pos)
if left_res:
right_res = self.right(tokens, left_res.pos)
if right_res:
if self.F == 0:
right_res.subtree.children.insert(0, left_res.subtree)
return right_res
left_res.subtree.children.append(right_res.subtree)
return Res(left_res.subtree, right_res.pos)
return right_res
return left_res
Опишем парсер альтернативы. Парсер Alt принимает на вход два парсера. Он отрабатывает успешно, если успешно отработал левый или правый парсер.
class Alt(Parser):
def __init__(self, left, right):
self.left = left
self.right = right
def __call__(self, tokens, pos = 0):
left_res = self.left(tokens, pos)
if left_res:
return left_res
right_res = self.right(tokens, pos)
if right_res:
return right_res
if left_res.pos > right_res.pos:
return left_res
return right_res
Опишем опциональный парсер Opt. Если его аргумент отработал успешно, то возвращает результат, иначе все равно возвращает успех, но с заданным значением по умолчанию.
class Opt(Parser):
def __init__(self, parser, default = None):
self.parser = parser
def __call__(self, tokens, pos = 0):
res = self.parser(tokens, pos)
if res:
return res
return Res(Tree(default), pos)
Парсер повторения Repeat работает пока не «сломается». Если аргумент не сработал ни разу, это тоже считается успехом.
class Repeat(Parser):
def __init__(self, root, parser, F = 0):
self.root = root
self.parser = parser
self.F = F
def __call__(self, tokens, pos = 0):
tree = Tree(self.root)
while True:
res = self.parser(tokens, pos)
if not res:
break
if self.F == 0:
tree.children.append(res.subtree)
else:
tree.children.insert(0, res.subtree)
pos = res.pos
return Res(tree, pos)
Парсер Prog последовательно применяет, преданные ему, парсеры и возвращает результат указанного (по умолчанию последнего).
class Prog(Parser):
def __init__(self, parser, *others, N = -1):
self.parser = parser
self.others = others
self.N = N
def __call__(self, tokens, pos = 0):
i = 1 + len(self.others) + self.N if self.N < 0 else self.N
if i < 0 or i > len(self.others):
raise IndexError
res = self.parser(tokens, pos)
if not res:
return res
t = res
error = 0
j = 1
for parser in self.others:
res = parser(tokens, res.pos)
if not res:
error = 1
break
if j == i:
t = res
j += 1
if error:
return res
return Res(t.subtree, res.pos)
Парсер Lazy используется для описания рекурсивных парсеров. Он принимает на вход функцию без аргументов, которая возвращает парсер. Это связано с тем, что на момент описания парсер еще не определен и не может ссылаться на себя непосредственно.
class Lazy(Parser):
def __init__(self, parser_func):
self.parser_func = parser_func
self.parser = None
def __call__(self, tokens, pos = 0):
if not self.parser:
self.parser = self.parser_func()
return self.parser(tokens, pos)
Парсер LExp в некоторых случаях позволяет обойти левую рекурсию (к примеру, при разборе лево-ассоциативных операторов). Принимает на вход три парсера: для разбора левого элемента, разделителя и правого элемента. При отсутствии очередного разделителя возвращает результат.
class LExp(Parser):
def __init__(self, first, sep, parser):
self.first = first
self.sep = sep
self.parser = parser
def __call__(self, tokens, pos = 0):
left_res = self.first(tokens, pos)
if not left_res:
return left_res
error = 0
while True:
sep_res = self.sep(tokens, left_res.pos)
if not sep_res:
break
right_res = self.parser(tokens, sep_res.pos)
if not right_res:
error = 1
break
sep_res.subtree.children.append(right_res.subtree)
sep_res.subtree.children.insert(0, left_res.subtree)
left_res = Res(sep_res.subtree, right_res.pos)
if error:
return right_res
return left_res
Описанные выше, парсер-комбинаторы предоставляют удобный и гибкий инструментарий для создания парсеров. Конечно они не сравнятся с такими известными библиотеками, как Boost.Spirit, но для новичка написание собственной библиотеки парсеров позволит лучше разобраться в процессе парсинга, что зачастую вызывает недоумение.
