Парсером называется часть программы, которая из линейной последовательности простых данных строит более сложные структуры данных с учетом некоторой грамматики.
Функциональные языки программирования позволяют описывать функции высших порядков, которые принимают в качестве аргументов и возвращают как результат другие функции.
Парсер-комбинаторы – известная техника создания парсеров, которая использует возможности функциональных языков программирования для динамического построения более сложных парсеров из простых по правилам некоторой грамматики.
На языке 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, но для новичка написание собственной библиотеки парсеров позволит лучше разобраться в процессе парсинга, что зачастую вызывает недоумение.
Автор: Arhin
