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