[Из песочницы] Классические парсер-комбинаторы на Python

Парсером называется часть программы, которая из линейной последовательности простых данных строит более сложные структуры данных с учетом некоторой грамматики.

Функциональные языки программирования позволяют описывать функции высших порядков, которые принимают в качестве аргументов и возвращают как результат другие функции.

Парсер-комбинаторы – известная техника создания парсеров, которая использует возможности функциональных языков программирования для динамического построения более сложных парсеров из простых по правилам некоторой грамматики.

На языке 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, но для новичка написание собственной библиотеки парсеров позволит лучше разобраться в процессе парсинга, что зачастую вызывает недоумение.

Let's block ads! (Why?)