279 lines
9.3 KiB
Python
279 lines
9.3 KiB
Python
"""Токенизатор и синтаксический анализатор -> AST (см. ast.py).
|
|
|
|
После токенизации строится дерево узлов; выложением занимается
|
|
ast.Evaluator. Разделение на «парсер -> AST -> eval» позволяет повторно
|
|
выводить выражения, хранить переменные в env и изолировать ошибки.
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
import re
|
|
|
|
from nodes import (
|
|
ASTError,
|
|
BinaryNode,
|
|
CallNode,
|
|
IdNode,
|
|
Node,
|
|
NumNode,
|
|
PostfixPercentNode,
|
|
PowNode,
|
|
SyntaxError_,
|
|
UnaryNode,
|
|
)
|
|
|
|
# Backward-compat: TokenizerError устарел, используйте ASTError
|
|
TokenizerError = ASTError
|
|
|
|
|
|
class _TokenType:
|
|
NUMBER = "NUMBER"
|
|
PLUS = "+"
|
|
MINUS = "-"
|
|
STAR = "*"
|
|
SLASH = "/"
|
|
FLOORDIV = "//"
|
|
POW = "**"
|
|
PERCENT = "%"
|
|
LPAREN = "("
|
|
RPAREN = ")"
|
|
COMMA = ","
|
|
ID = "ID"
|
|
|
|
|
|
_TWO_CHAR_OPS = {"**": _TokenType.POW, "//": _TokenType.FLOORDIV}
|
|
|
|
# одиночные операторы/скобки/запятая: символ -> тип токена
|
|
_SINGLE_CHAR_OPS = {
|
|
"+": _TokenType.PLUS,
|
|
"-": _TokenType.MINUS,
|
|
"*": _TokenType.STAR,
|
|
"/": _TokenType.SLASH,
|
|
"(": _TokenType.LPAREN,
|
|
")": _TokenType.RPAREN,
|
|
"%": _TokenType.PERCENT,
|
|
",": _TokenType.COMMA,
|
|
}
|
|
|
|
_NUM_RE = re.compile(
|
|
r"[0-9][0-9_]*(?:\.[0-9_]*)?(?:[eE][+-]?[0-9]+)?"
|
|
r"|\.[0-9][0-9_]*(?:[eE][+-]?[0-9]+)?"
|
|
)
|
|
_ID_RE = re.compile(r"[A-Za-z_][A-Za-z0-9_]*")
|
|
|
|
# имена известных функций (для диагностических сообщений: «требует скобок»)
|
|
KNOWN_FUNCS: frozenset[str] = frozenset({
|
|
"sqrt", "abs", "exp", "ln", "log", "log2", "log10",
|
|
"round", "floor", "ceil", "sin", "cos", "tan",
|
|
"asin", "acos", "atan",
|
|
})
|
|
KNOWN_CONSTS: frozenset[str] = frozenset({"pi", "e", "tau", "inf"})
|
|
|
|
|
|
class Token:
|
|
__slots__ = ("type", "value")
|
|
|
|
def __init__(self, type: str, value=None):
|
|
self.type = type
|
|
self.value = value
|
|
|
|
def __repr__(self) -> str:
|
|
return f"Token({self.type!r}, {self.value!r})"
|
|
|
|
|
|
def tokenize(text: str) -> list[Token]:
|
|
tokens: list[Token] = []
|
|
i = 0
|
|
n = len(text)
|
|
while i < n:
|
|
ch = text[i]
|
|
if ch.isspace():
|
|
i += 1
|
|
continue
|
|
m = _NUM_RE.match(text, i)
|
|
if m:
|
|
num_str = m.group()
|
|
try:
|
|
tokens.append(Token(_TokenType.NUMBER, float(num_str)))
|
|
except ValueError:
|
|
raise SyntaxError_(f"Некорректное число: {num_str!r}") from None
|
|
i = m.end()
|
|
continue
|
|
m = _ID_RE.match(text, i)
|
|
if m:
|
|
tokens.append(Token(_TokenType.ID, m.group().lower()))
|
|
i = m.end()
|
|
continue
|
|
two = text[i:i + 2]
|
|
if two in _TWO_CHAR_OPS:
|
|
tokens.append(Token(_TWO_CHAR_OPS[two]))
|
|
i += 2
|
|
continue
|
|
if ch in _SINGLE_CHAR_OPS:
|
|
tokens.append(Token(_SINGLE_CHAR_OPS[ch]))
|
|
i += 1
|
|
continue
|
|
raise SyntaxError_(f"Недопустимый символ: {ch!r} (позиция {i + 1})")
|
|
return tokens
|
|
|
|
|
|
class Parser:
|
|
"""Простой рекурсивный спуск по токенам -> AST."""
|
|
|
|
def __init__(self, tokens: list[Token]):
|
|
self.tokens = tokens
|
|
self.pos = 0
|
|
|
|
def _peek(self) -> Token | None:
|
|
return self.tokens[self.pos] if self.pos < len(self.tokens) else None
|
|
|
|
def _next_starts_operand(self) -> bool:
|
|
nxt = (self.tokens[self.pos + 1]
|
|
if self.pos + 1 < len(self.tokens) else None)
|
|
if nxt is None:
|
|
return False
|
|
return nxt.type in (_TokenType.NUMBER, _TokenType.LPAREN, _TokenType.ID)
|
|
|
|
def _advance(self) -> Token:
|
|
tok = self._peek()
|
|
if tok is None:
|
|
raise SyntaxError_("Неожиданный конец выражения")
|
|
self.pos += 1
|
|
return tok
|
|
|
|
def parse(self) -> Node:
|
|
if not self.tokens:
|
|
raise SyntaxError_("Пустое выражение")
|
|
node = self._expr()
|
|
if self.pos != len(self.tokens):
|
|
raise SyntaxError_("Лишние токены в выражении")
|
|
return node
|
|
|
|
def _expr(self) -> Node:
|
|
left = self._term()
|
|
while True:
|
|
tok = self._peek()
|
|
if tok and tok.type in (_TokenType.PLUS, _TokenType.MINUS):
|
|
op = tok.type
|
|
self._advance()
|
|
right = self._term()
|
|
left = BinaryNode(op, left, right)
|
|
else:
|
|
return left
|
|
|
|
def _term(self) -> Node:
|
|
left = self._factor()
|
|
while True:
|
|
tok = self._peek()
|
|
if tok and tok.type in (_TokenType.STAR, _TokenType.SLASH,
|
|
_TokenType.FLOORDIV):
|
|
op = tok.type
|
|
self._advance()
|
|
right = self._factor()
|
|
left = BinaryNode(op, left, right)
|
|
elif tok and tok.type == _TokenType.PERCENT and self._next_starts_operand():
|
|
self._advance()
|
|
right = self._factor()
|
|
left = BinaryNode("%", left, right)
|
|
else:
|
|
return left
|
|
|
|
def _factor(self) -> Node:
|
|
tok = self._peek()
|
|
if tok and tok.type in (_TokenType.PLUS, _TokenType.MINUS):
|
|
self._advance()
|
|
return UnaryNode(self._factor(), tok.type == _TokenType.MINUS)
|
|
return self._power()
|
|
|
|
def _power(self) -> Node:
|
|
base = self._postfix()
|
|
tok = self._peek()
|
|
if tok and tok.type == _TokenType.POW:
|
|
self._advance()
|
|
exponent = self._factor()
|
|
return PowNode(base, exponent)
|
|
return base
|
|
|
|
def _postfix(self) -> Node:
|
|
node = self._atom()
|
|
while True:
|
|
tok = self._peek()
|
|
if tok and tok.type == _TokenType.PERCENT and not self._next_starts_operand():
|
|
self._advance()
|
|
node = PostfixPercentNode(node)
|
|
else:
|
|
return node
|
|
|
|
def _atom(self) -> Node:
|
|
tok = self._peek()
|
|
if tok is None:
|
|
raise SyntaxError_("Неожиданный конец выражения")
|
|
if tok.type == _TokenType.NUMBER:
|
|
self._advance()
|
|
return NumNode(tok.value or 0.0)
|
|
if tok.type == _TokenType.ID:
|
|
self._advance() # съедаем идентификатор, иначе nxt снова указал бы на него
|
|
name = tok.value or ""
|
|
nxt = self._peek()
|
|
if nxt and nxt.type == _TokenType.LPAREN:
|
|
return self._call(name)
|
|
if name in KNOWN_FUNCS:
|
|
raise SyntaxError_(f"Функция '{name}' требует скобок: {name}(...)")
|
|
return IdNode(name)
|
|
if tok.type == _TokenType.LPAREN:
|
|
self._advance()
|
|
node = self._expr()
|
|
close = self._peek()
|
|
if not close or close.type != _TokenType.RPAREN:
|
|
raise SyntaxError_("Не хватает закрывающей скобки ')'")
|
|
self._advance()
|
|
return node
|
|
raise SyntaxError_("Ожидалось число, константа, функция или скобку")
|
|
|
|
def _call(self, name: str) -> Node:
|
|
func_arities = {
|
|
"sqrt": (1,), "abs": (1,), "exp": (1,), "ln": (1,),
|
|
"log": (1, 2), "log2": (1,), "log10": (1,), "round": (1, 2),
|
|
"floor": (1,), "ceil": (1,), "sin": (1,), "cos": (1,), "tan": (1,),
|
|
"asin": (1,), "acos": (1,), "atan": (1,),
|
|
}
|
|
if name not in func_arities:
|
|
raise SyntaxError_(f"Неизвестная функция: {name!r}")
|
|
self._advance() # '('
|
|
tok = self._peek()
|
|
if tok and tok.type == _TokenType.RPAREN:
|
|
self._advance()
|
|
raise SyntaxError_(f"'{name}' требует аргументов")
|
|
args: list[Node] = []
|
|
while True:
|
|
args.append(self._expr())
|
|
tok = self._peek()
|
|
if tok and tok.type == _TokenType.COMMA:
|
|
self._advance()
|
|
continue
|
|
break
|
|
close = self._peek()
|
|
if not close or close.type != _TokenType.RPAREN:
|
|
raise SyntaxError_(f"Не хватает закрывающей скобки ')' в '{name}'")
|
|
self._advance()
|
|
if len(args) not in func_arities[name]:
|
|
expected = "/".join(str(a) for a in func_arities[name])
|
|
raise SyntaxError_(
|
|
f"'{name}': ожидалось аргументов {expected},"
|
|
f" получено {len(args)}"
|
|
)
|
|
return CallNode(name, args)
|
|
|
|
|
|
def build_ast(expression: str) -> Node:
|
|
"""Токенизирует и строит AST.
|
|
|
|
Raises SyntaxError_ (в т.ч. позиционные сообщения) при некорректном вводе.
|
|
"""
|
|
tokens = tokenize(expression)
|
|
return Parser(tokens).parse()
|
|
|
|
|
|
def repr_ast(node: Node) -> str:
|
|
"""Повторный вывод выражения из AST (для досуга/отладки)."""
|
|
return repr(node)
|