Привет, хабровчане!

Я Дима, Python-разработчик из 21YARD, сервиса поиска строительных подрядчиков.

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

Когда использовать

Интерпретатор используют, когда нужно обрабатывать лексические конструкции с определенными грамматическими правилами. Как пример — регулярные выражения.

Примеры ситуаций, в которых паттерн полезен:

• когда нужно разработать язык для описания операций или поведения;

• когда часто приходится обрабатывать сложные выражения;

• когда грамматика системы часто дополняется новыми правилами.

Интерпретатор позволяет легко добавлять новые правила и символы в грамматику языка. Это делает систему гибкой и расширяемой. Также интерпретатор упрощает обработку сложных выражений: позволяет разбивать сложные выражения на простые части и обрабатывать их поэтапно.

Концепции в основе

В основе интерпретатора лежат три основные концепции:

• лексический процессор: анализирует выражение и создает из него токены. Токен - это объект, который хранит значение литерала и его тип;

• обработчик токенов: строит абстрактное синтаксического дерево из токенов. Дерево строится в соответствии с приоритетом операций в выражении. Корень дерева - последняя операция в выражении;

• сам интерпретатор: интерпретирует выражение пользователя. Если в выражении нет ошибок, обрабатывает его. В противном случае сообщает об ошибке.

Реализация

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

Интерпретатор будет поддерживать:

• Базовые арифметические операции: сложение (+), вычитание (-), умножение (*), деление (/), возведение в степень (^);

• Выполнение операций с учетом приоритета;

• Возможность использовать скобки, чтобы задать приоритет операций;

• Базовые математические функции, такие как sin, cos, tan, log, sqrt и exp;

• Переменные: пользователь сможет определять переменные, присваивать им значения и использовать их в последующих операциях;

• Обработку ошибок.

Лексический анализ выражения

Опишем типы токенов, которые определяют грамматику языка выражения (src/enums.py):

class TokenTypesEnum(str, Enum):
	NUMBER = 'number'
	PLUS = 'plus'
	MINUS = 'minus'
	STAR = 'star'
	SLASH = 'slash'
	CARET = 'caret'
	LEFT_PARENTHESIS = 'left_parenthesis'
	RIGHT_PARENTHESIS = 'right_parenthesis'
	EOF = 'EOF'

Создадим класс токена, который будет хранить литерал и его тип (src/tokens.py):

@dataclass
class Token:
	type: TokenTypesEnum
	literal: str

	def __str__(self) -> str:
    	return f'{self.__class__.__name__}({self.type}, {self.literal})'

Необходимо разделить математическое выражение на токены. Для этого нужно определить грамматические правила. Используем для этой цели RegEx - регулярные выражения (src/config.py):

LEXICAL_RULES: Dict[TokenTypesEnum, str] = {
	TokenTypesEnum.NUMBER: r'(\d+(\.\d+)?)',
	TokenTypesEnum.PLUS: r'(\+)',
	TokenTypesEnum.MINUS: r'(\-)',
	TokenTypesEnum.STAR: r'(\*)',
	TokenTypesEnum.SLASH: r'(/)',
	TokenTypesEnum.CARET: r'(\^)',
	TokenTypesEnum.LEFT_PARENTHESIS: r'(\()',
	TokenTypesEnum.RIGHT_PARENTHESIS: r'(\))'
}

Математическое выражение нужно преобразовать в набор токенов. Для этого реализуем лексический процессор (src/lexical_processor.py):

class LexicalProcessor(Processor):

	def __init__(self) -> None:
    	self._expression: str = ''
    	self._results: List[Token] = []

	def process_expression(self, expression: str) -> List[Token]:
    	"""
    	Processes expression and returns the list of tokens generated from expression, if expression is valid.
    	"""

    	# Initializes for each new expression processing:
    	self._expression = expression
    	self._results = []

    	self._extract_regex_pattern_from_expression()

    	# Add a token symbolizing the end of the line for further operations on the preprocessed expression:
    	self._results.append(
        	Token(
            	literal='',
            	type=TokenTypesEnum.EOF
        	)
    	)

    	return self._results

	def _extract_regex_pattern_from_expression(self) -> None:
    	"""
    	Extracts the RegEx pattern from expression, starting from the beginning.
    	If one of RegEx patterns is found in the expression, the corresponding token will be created.
    	In other case, expression is not valid and ExpressionSyntaxError will be raised.

    	After token is created, the expression is reduced by the characters used for tokenization
    	and processed recursively.
    	"""

    	while len(self._expression) > 0:
        	max_rule: TokenTypesEnum = TokenTypesEnum.EOF
        	max_lit: str = ''
        	self._expression = self._expression.strip()

        	# Finding the longest part of an expression using RegEx:
        	for rule in LEXICAL_RULES.keys():
            	regex_pattern: re.Pattern[str] = re.compile(pattern=LEXICAL_RULES[rule])
            	regex_match: Optional[re.Match[str]] = regex_pattern.match(string=self._expression)
            	if (regex_match is not None) and (len(regex_match.group(0)) > len(max_lit)):
                	max_lit = regex_match.group(0)
                	max_rule = rule

        	if max_rule == TokenTypesEnum.EOF:
            	raise ExpressionSyntaxError()

        	self._expression = self._expression[len(max_lit):]  # Reduce the expression by the processed part
        	self._results.append(
            	Token(
                	literal=max_lit,
                	type=max_rule
            	)
        	)

Метод self._extract_regex_pattern_from_expression удаляет пробелы с обеих сторон выражения. Затем он обрабатывает первый литерал в выражении, определяя его тип с помощью грамматических правил. Если литерал не соответствует ни одному из правил - значит выражение неправильное и будет вызвана ошибка. Если выражение корректное - будет создан новый токен, а выражение обрезано на обработанную часть. Оставшаяся часть выражения повторно обрабатывается.

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

Обработка токенов

Цель обработки токенов - создание абстрактного синтаксического дерева на их основе. Дерево строится в соответствии с приоритетами в математическом выражении.

Введем классы дерева, выражения и конкретных типов возможных выражений (src/expressions.py):

dataclass
class TreeNode:
	"""
	Abstract Syntax Tree.
	"""

	pass


@dataclass
class Expression(TreeNode):
	pass


@dataclass
class UnaryOperation(Expression):
	"""
	-(2 + 3), where minus is operation and (2 + 3) is an expression.
	"""

	operation: str
	expression: Expression


@dataclass
class BinaryOperation(Expression):
	"""
	1 * 2 + 3 * 3, where "1 * 2" is left expression, "+" is operation and "3 * 3" is right expression.
	"""

	operation: str
	left: Expression
	right: Expression


@dataclass
class Number(Expression):
	value: float

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

Реализуем обработчик токенов, который строит абстрактное синтаксическое дерево (src/tokens_parser.py):

class TokensParser(Parser):
	"""
	Creates Abstract Syntax Tree according to operations priority in provided expression.

	program := computation
	computation := term ( (PLUS | MINUS) term )*
	term := unary ( (STAR | SLASH ) unary )*
	unary := PLUS unary | MINUS unary | exponentiation
	exponentiation := atom CARET unary | atom
	atom := LEFT_PARENTHESIS computation RIGHT_PARENTHESIS | number
	number := INT
	"""

	def __init__(self) -> None:
    	self._tokens: List[Token] = []
    	self._next_token_index: int = 0

	def parse(self, tokens: List[Token]) -> Expression:
    	"""
    	Parses the expression, created by user.
    	"""

    	# Initializes for each new parsing process:
    	self._next_token_index = 0
    	self._tokens = tokens

    	computation: Expression = self._parse_computation()
    	self._get_next_token(expected_token_type=TokenTypesEnum.EOF)
    	return computation

	def _parse_computation(self) -> Expression:
    	result: Expression = self._parse_term()
    	while (next_token_type := self._get_next_token_type()) in {TokenTypesEnum.PLUS, TokenTypesEnum.MINUS}:
        	operation: str = OPERATIONS[next_token_type]
        	self._get_next_token(expected_token_type=next_token_type)
        	right: Expression = self._parse_term()
        	result = BinaryOperation(operation=operation, left=result, right=right)

    	return result

	def _parse_term(self) -> Expression:
    	"""
    	Parses an expression with multiplications and divisions.
    	"""

    	result: Expression = self._parse_unary()
    	while (next_token_type := self._get_next_token_type()) in {TokenTypesEnum.STAR, TokenTypesEnum.SLASH}:
        	operation: str = OPERATIONS[next_token_type]
        	self._get_next_token(expected_token_type=next_token_type)
        	right: Expression = self._parse_unary()
        	result = BinaryOperation(operation=operation, left=result, right=right)

    	return result

	def _parse_unary(self) -> Expression:
    	"""
    	Parses a unary operator.
    	"""

    	if (next_token_type := self._get_next_token_type()) in {TokenTypesEnum.PLUS, TokenTypesEnum.MINUS}:
        	operation: str = OPERATIONS[next_token_type]
        	self._get_next_token(expected_token_type=next_token_type)
        	expression: Expression = self._parse_unary()
        	return UnaryOperation(operation=operation, expression=expression)
    	else:  # No unary operators in sight.
        	return self._parse_exponentiation()

	def _parse_exponentiation(self) -> Expression:
    	"""
    	Parses a caret operator.
    	"""

    	expression: Expression = self._parse_atom()
    	next_token_type: TokenTypesEnum = self._get_next_token_type()
    	if next_token_type == TokenTypesEnum.CARET:
        	self._get_next_token(expected_token_type=TokenTypesEnum.CARET)
        	right: Expression = self._parse_unary()
        	expression = BinaryOperation(operation=OPERATIONS[next_token_type], left=expression, right=right)

    	return expression

	def _parse_atom(self) -> Expression:
    	"""
    	Parses a parenthesised expression or a number.
    	"""

    	expression: Expression
    	if self._get_next_token_type() == TokenTypesEnum.LEFT_PARENTHESIS:
        	self._get_next_token(expected_token_type=TokenTypesEnum.LEFT_PARENTHESIS)
        	expression = self._parse_computation()
        	self._get_next_token(expected_token_type=TokenTypesEnum.RIGHT_PARENTHESIS)
    	else:
        	expression = self._parse_number()

    	return expression

	def _parse_number(self) -> Number:
    	return Number(float(self._get_next_token(expected_token_type=TokenTypesEnum.NUMBER).literal))

	def _get_next_token(self, expected_token_type: TokenTypesEnum) -> Token:
    	"""
    	Returns next token if token's type matches expected token type.

    	In other case raises error.
    	"""

    	next_token: Token = self._tokens[self._next_token_index]
    	self._next_token_index += 1

    	if next_token.type != expected_token_type:
        	raise ParseError(f'Expected {expected_token_type}, but received {next_token!r}.')

    	return next_token

	def _get_next_token_type(self) -> TokenTypesEnum:
    	"""
    	Checks type of upcoming token without consuming it.
    	"""

    	return self._tokens[self._next_token_index].type

Приоритезация операций и ожидание следующего типа токена - основа обработки. Если получен не тот токен, который ожидался, будет вызвана ошибка.

Интерпретатор

Интерпретатор работает с лексическим обработчиком, парсером токенов и командами через абстракции. Это позволяет менять реализацию этих объектов, без необходимости изменения кода самого интерпретатора (src/interfaces.py и src/commands/interfaces.py):

class Parser(ABC):

	@abstractmethod
	def parse(self, tokens: List[Token]) -> Expression:
    	raise NotImplementedError


class Processor(ABC):

	@abstractmethod
	def process_expression(self, expression: str) -> List[Token]:
    	raise NotImplementedError

class BaseCommand(ABC):

	def __init__(self, a: float, b: float) -> None:
    	self._a: float = a
    	self._b: float = b

	@abstractmethod
	def execute(self) -> float:
    	raise NotImplementedError


class MathCommand(ABC):

	def __init__(self, value: float) -> None:
    	self._value: float = value

	@abstractmethod
	def execute(self) -> float:
    	raise NotImplementedError

Каждая из команд представлена отдельным объектом и является упрощенной версией паттерна Комманда (src/commands/base_commands.py и src/commands/math_commands.py):

class MultiplyCommand(BaseCommand):

	def execute(self) -> float:
    	return self._a * self._b


class DivideCommand(BaseCommand):

	def execute(self) -> float:
    	try:
        	return self._a / self._b
    	except ZeroDivisionError:
        	raise CustomZeroDivisionError()


class SubtractCommand(BaseCommand):

	def execute(self) -> float:
    	return self._a - self._b


class AddCommand(BaseCommand):

	def execute(self) -> float:
    	return self._a + self._b


class ExponentialCommand(BaseCommand):

	def execute(self) -> float:
    	return self._a ** self._b

class SqrtCommand(MathCommand):

	def execute(self) -> float:
    	return math.sqrt(self._value)


class SinCommand(MathCommand):

	def execute(self) -> float:
    	return math.sin(self._value)


class CosCommand(MathCommand):

	def execute(self) -> float:
    	return math.cos(self._value)


class LogCommand(MathCommand):

	def execute(self) -> float:
    	return math.log(self._value)


class TanCommand(MathCommand):

	def execute(self) -> float:
    	return math.tan(self._value)


class ExpCommand(MathCommand):

	def execute(self) -> float:
    	return math.exp(self._value)

Свяжем команды с символами, которые представляют их в математическом выражении (src/config.py):

BASE_COMMANDS: Dict[str, Type[BaseCommand]] = {
	'+': AddCommand,
	'-': SubtractCommand,
	'*': MultiplyCommand,
	'/': DivideCommand,
	'^': ExponentialCommand,
}

MATH_COMMANDS: Dict[str, Type[MathCommand]] = {
	'sin': SinCommand,
	'cos': CosCommand,
	'tan': TanCommand,
	'log': LogCommand,
	'exp': ExpCommand,
	'sqrt': SqrtCommand,
}

Работа интерпретатора математических выражений реализуется через следующие шаги:

1. Получить пользовательский ввод;

2. Убедиться, что пользовательский ввод корректен, или уведомить пользователя об ошибке. Корректный пользовательский ввод содержит переменную, знак присваивания и выражение для присвоения. Название переменной состоит только из букв;

3. Заменить все переменные в выражении на их значение. Это возможно, если переменные существуют в хранилище и были вычислены ранее в на основе других выражений пользователя;

4. Вычислить значения математических функций и заменить их в выражении на полученное значение. Аргумент для математической функции вычисляется в шагах №5, №6 и №7;

5. Преобразовать выражение в набор токенов с помощью лексического процессора;

6. Построить синтаксическое дерево на основе токенов с помощью обработчика токенов;

7. Рекурсивно в восходящем порядке вычислить значение каждого узла дерева и получить финальное значение выражения.

Реализуем класс интерпретатора, который выполняет все перечисленные шаги в нужном порядке (src/interpreter.py):

class MathOperationsInterpreter:

	def __init__(
        	self,
        	interpreter_base_commands: Dict[str, Type[BaseCommand]],
        	interpreter_math_commands: Dict[str, Type[MathCommand]],
        	parser: Parser,
        	lexical_processor: Processor
	) -> None:

    	self._base_commands: Dict[str, Type[BaseCommand]] = interpreter_base_commands
    	self._math_commands: Dict[str, Type[MathCommand]] = interpreter_math_commands
    	self._parser: Parser = parser
    	self._lexical_processor: Processor = lexical_processor

    	# Storage for executed expressions, which can be user in future expressions:
    	self._user_variables: Dict[str, float] = {}

	def interpret(self, user_input: str) -> None:
    	"""
    	1) Receives user input and checks it validity;
    	2) Interprets the expression in the user input and executes it;
    	3) Assigns executed result of the expression to a given variable.
    	"""

    	try:
        	key: str
        	expression: str
        	key, expression = self._validate_user_input(user_input=user_input.lower())

        	expression_result: float = self._execute(expression=expression)
        	self._user_variables[key] = expression_result
    	except (
            	ParseError,
            	ExpressionSyntaxError,
            	IncorrectVariableAssignmentError,
            	UnknownExpressionTypeError,
            	CustomZeroDivisionError
    	) as e:
        	print(e)

	def _validate_user_input(self, user_input: str) -> Tuple[str, str]:
    	"""
    	Validates user input. If input is invalid, raises IncorrectVariableAssignmentError.

    	User input must contain a variable, an assignment sign, and an assignment expression.
    	Variable must contain only alphabetic characters.

    	Examples of correct user input are:
    	1) "x = 2";
    	2) "x= 2";
    	3) "x=2";
    	"""

    	user_input_sep: str = ' '
    	values: List[str] = user_input.split(user_input_sep)

    	# Check, if input is "variable = expression":
    	user_variable: str
    	expression: str
    	equal_sign: str = '='
    	if values[0].endswith(equal_sign):
        	user_variable = values[0][: -1]  # Variable name without "=" symbol
        	expression = user_input_sep.join(values[1:])
    	elif len(values) == 1 and equal_sign in values[0]:
        	use_var_index: int = values[0].find(equal_sign)
        	user_variable = values[0][: use_var_index]
        	expression = values[0][use_var_index + 1:]
    	elif values[1] == equal_sign:
        	user_variable = values[0]
        	expression = user_input_sep.join(values[2:])
    	else:
        	raise IncorrectVariableAssignmentError()

    	if not user_variable.isalpha():
        	raise IncorrectVariableAssignmentError()

    	expression = self._substitute_user_variables(expression=expression)
    	return user_variable, expression

	def _substitute_user_variables(self, expression: str) -> str:
    	"""
    	Substitutes already interpreted variable in expression if exists.
    	"""

    	for key in self._user_variables.keys():
        	if key in expression:
            	expression = expression.replace(key, str(self._user_variables[key]))

    	return expression

	def _execute(self, expression: str) -> float:
    	"""
    	1) All basic mathematical functions, such as sin, cos, tan, log, sqrt and exp,
    	are executed if any in the expression;
    	2) Generates tokens from the expression for parsing purpose;
    	3) Creates AST (Abstract Syntax Tree) on tokens basis;
    	4) Recursively calculates the value of a parsed expression based on the AST.
    	"""

    	expression = self._execute_math_operations(expression=expression)
    	tokens: List[Token] = self._lexical_processor.process_expression(expression=expression)

    	try:
        	operations_tree: TreeNode = self._parser.parse(tokens=tokens)
    	except ParseError:
        	raise ExpressionSyntaxError()

    	return self._calculate_node_value(node=operations_tree)

	def _execute_math_operations(self, expression: str) -> str:
    	"""
    	Searches for a math function in expression.
    	If such function is found, calculates its value and replaces the subexpression related to the
    	math function with the calculated value.

    	Example:
    	:param expression: "sqrt(25) + 5 * 2"
    	:return: "5.0 + 5 * 2"
    	"""

    	for math_command in self._math_commands.keys():
        	math_command_index: int = expression.find(math_command)
        	if math_command_index != -1:  # Not found
            	math_command_expression: str
            	postfix: str
            	math_command_expression, postfix = self._extract_expression_from_parentless(
                	expression=expression[math_command_index + len(math_command):]
            	)

            	command = self._math_commands[math_command](
                	value=self._execute(
                    	expression=math_command_expression
                	)
            	)

            	prefix: str = expression[: math_command_index]
            	expression = prefix + str(command.execute()) + postfix

    	return expression

	@staticmethod
	def _extract_expression_from_parentless(expression: str) -> Tuple[str, str]:
    	"""
    	Extracts subexpression from parentless in original expression for math functions purposes.
    	If original expression is not valid or there is no parentless in it, raises ExpressionSyntaxError.
    	Returns extracted subexpression and the remaining part of original expression.

    	Example:
    	:param expression: "(5 + 2) * 3"
    	:return: ("5 + 2", " * 3")
    	"""

    	opening_parenthesis: str = '('
    	closing_parenthesis: str = ')'
    	if not expression.startswith(opening_parenthesis):
        	raise ExpressionSyntaxError()

    	# Starting from -1, because it's index and will be straightaway incremented
    	# at first iteration of for loop below:
    	parentless_expression_end_index: int = -1

    	parentless_stack: List[str] = []
    	for index in range(len(expression)):
        	parentless_expression_end_index += 1
        	symbol: str = expression[index]
        	if symbol == opening_parenthesis:
            	parentless_stack.append(symbol)
        	elif symbol == closing_parenthesis:
            	parentless_stack.pop(0)

        	if len(parentless_stack) == 0:
            	break

    	if len(parentless_stack) != 0:
        	raise ExpressionSyntaxError()

    	# Expression and postfix should be without parentless from original expression:
    	parentless_expression: str = expression[1: parentless_expression_end_index]
    	postfix: str = expression[parentless_expression_end_index + 1:]
    	return parentless_expression, postfix

	def _calculate_node_value(self, node: TreeNode) -> float:
    	"""
    	1) Gets an AST tree node, which is one of next types: UnaryOperation, BinaryOperation or Number;
    	2) If node is a Number type - returns it, else recursively calculates expression, stored in node.
    	"""

    	command: BaseCommand
    	if isinstance(node, UnaryOperation):
        	command = self._base_commands[node.operation](
            	a=0,  # Unary operation has only one part of expression
            	b=self._calculate_node_value(node=node.expression)
        	)

        	return command.execute()
    	elif isinstance(node, BinaryOperation):
        	command = self._base_commands[node.operation](
            	a=self._calculate_node_value(node=node.left),
            	b=self._calculate_node_value(node=node.right)
        	)

        	return command.execute()
    	elif isinstance(node, Number):
        	return node.value
    	else:
        	raise UnknownExpressionTypeError()

	def get_result(self) -> Optional[float]:
    	"""
    	Returns the value for a result variable if it exists.

    	This variable signals that all expressions have been interpreted and variable storage is no longer required.
    	"""

    	result: Optional[float] = self._user_variables.get(RESULT_VARIABLE)
    	if result:
        	self._user_variables.clear()

    	return result

Чтобы получить результат выражения с использованием всех переменных - финальное выражение должно быть присвоено переменной result.

Услышимся в следующих выпусках.
Буду благодарен поддержке и конструктивной критике!