Кратко и по делу — как решать задачу «парсер математических выражений с приоритетом операций» в парадигмах: процедурной, ООП, функциональной и логической (Prolog). Для каждой: какие абстракции, как управляют состоянием и как тестируют.
Общее ядро задачи (без кода): лексер → парсер → AST → эвальюатор; приоритеты операций и ассоциативность реализуются в парсере (или при постфиксной трансформации).
Парадигма процедурная
- Подход: пошаговый алгоритм, явно управляемые структуры данных. Часто используют алгоритм «shunting‑yard» или рекурсивный нисходящий парсер, реализованный как набор функций.
- Абстракции:
- функции: tokenize(input), parse(tokens), to_postfix(tokens) или parse_expr(level).
- простые структуры: стек для операторов, очередь для выхода, узел AST как запись (tuple/struct).
- Управление состоянием:
- мутабельные структуры (стек, индекс текущего токена), глобальные/передаваемые по ссылке состояния.
- состояние явно изменяется инструкциями (push/pop, advance()).
- Тестирование:
- модульные тесты для функций (tokenize, to_postfix, eval).
- интеграционные тесты: вход → ожидаемая постфиксная строка или значение.
- фуззинг / генерация выражений для проверки корректности приоритетов.
- Короткая схема (псевдо):
- to_postfix: пока есть токены: если число → вывод; если оператор → сравнить приоритеты со стеком; и т.д.
Объектно‑ориентированная
- Подход: моделирование предметной области через объекты и их взаимодействие.
- Абстракции:
- классы Tokenizer, Parser, Evaluator, Token, ASTNode и наследники (NumberNode, BinaryOpNode).
- методы инкапсулируют операции (Parser.parse(), Node.evaluate()).
- паттерн Visitor для обхода AST (eval, pretty-print).
- Управление состоянием:
- состояние хранится в полях объектов (тек. позиция в токенах, стек внутри парсера).
- изменение через методы; состояние локализовано в экземпляре.
- возможны мутабельные объекты (Parser переиспользуем) или immutable‑варианты (создавать новые AST).
- Тестирование:
- юнит‑тесты методов классов (mock Tokenizer для Parser).
- тесты на поведение объектов (парсер строит ожидаемое дерево; Visitor возвращает правильное значение).
- интеграционные тесты и тесты контрактов (инварианты объектов).
- Достоинство: легко расширять (новые узлы, новые операторы через наследование).
Функциональная
- Подход: чистые функции, композиция, избежание мутаций. Часто используют парсер‑комбинаторы или рекурсивные функции с возвращаемым остатком входа.
- Абстракции:
- парсер как значение: Parser = input -> [(result, rest)] (или Maybe/Result).
- набор комбинаторов: seq, alt, many, map, then.
- AST как неизменяемые структуры (алгебраические типы).
- Управление состоянием:
- состояние (позиция, оставшийся ввод) передаётся явно в возвращаемых значениях, не мутируется.
- когда нужен локальный «мутабельный» эффект — используют монады состояния либо чистую рекурсию.
- чистота функций упрощает параллелизм и кеширование.
- Тестирование:
- property‑based тестирование (QuickCheck): свойства (например, парсинг → эвальюация = вычисление прямого значения).
- простые unit‑тесты для комбинаторов и отдельных парсеров.
- легче делать гарантии о побочных эффектах и сравнивать функции.
- Пример стиля: парсер выражения = chainl1(termParser, addOpParser) — композиция комбинаторов.
Логическая (Prolog)
- Подход: описывают грамматику и отношения через правила; Prolog выполняет поиск/унификацию/откат.
- Абстракции:
- DCG (Definite Clause Grammars) для грамматики: expr --> term, expr_tail, и т.п.
- представление AST как термов: plus(Left, Right), times(...), number(N).
- правила оценки: eval(plus(A,B), V) :- eval(A,VA), eval(B,VB), V is VA + VB.
- Управление состоянием:
- нет явной мутации; состояние — отношения между аргументами предикатов и текущим остатком токенов.
- backtracking автоматически пробует альтернативы; переменные логические (ставятся через унификацию).
- Тестирование:
- набор фактов/целей: ?- phrase(expr(AST), Tokens), AST == expected.
- проверка целей eval(AST, Value).
- удобно задавать примеры как набор запросов; использовать встроённые тест‑фреймворки Prolog.
- Особенности: обработка неоднозначностей и попыток — естественна; priority реализуются через структуру правил (разделение уровнями: expr → term / expr_tail).
Сравнительная сводка (ключевые различия)
- Абстракции:
- процедурная: функции и простые структуры.
- ООП: объекты/классы/методы + наследование/паттерны.
- функциональная: парсер‑комбинаторы, алгебраические типы, композиция функций.
- логическая: грамматика в виде правил, термы как AST.
- Управление состоянием:
- процедурная/ООП: мутация (стек, позиция).
- функциональная: явная передача состояния, неизменяемость; при необходимости — монады.
- Prolog: логические переменные и остаток входа; backtracking вместо явной мутации.
- Тестирование:
- процедурная: unit + интеграция + фуззинг.
- ООП: unit на методы/классы, mock‑объекты, контрактные тесты.
- функциональная: property‑based тесты + unit тесты (легко тестировать чистые функции).
- логическая: тесты целей/фактов, проверка DCG и eval‑правил.
Короткая рекомендация
- Нужна простота и скорость разработки — процедурный shunting‑yard.
- Планируете расширяемость и сложные AST‑операции — ООП с Visitor.
- Хотите формальные свойства, легкое тестирование и композицию — функциональные парсер‑комбинаторы.
- Нужны декларативная спецификация грамматики и мощный поиск/неоднозначность — Prolog / DCG.
Если нужно, могу привести минимальный пример (псевдо) кода в одной из парадигм.