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

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

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

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