Интерпретатор (Interpreter)
реализации: java, количество: 8
реализации(исходники)
+добавить
Интерпретатор - паттерн поведения объектов, реализующий динамические алгоритмы с помощью декларативного описания. codelab.ru оригинал источник codelab.ru
Условия, Задача, Назначение
В ряде случаев приложение на разных этапах выполнения использует одни и те же алгоритмы обработки данных, или, точнее, многие алгоритмы функционирования приложения строятся из более простых, элементарных неизменяющихся под-алгоритмов. оригинал codelab.ru codelab.ru источникПаттерн-интерпретатор именно это и предлагает. Подход можно отнести к декларативному программированию: мы имеем лишь полноценные классы для всех элементарных составляющих, далее на декларативном уровне (в виде любых грамматических инструкций, правил и т.д.) мы составляем лишь схему их сборки, расположения и взаимодействия – в результате получая совершенно новую функциональность, не создавая никаких новых классов.источник codelab.ru codelab.ru оригинал
Можно сказать, этим мы определяем некий интерпретируемый язык и класс-интерпретатора, который будет заниматься его распознаванием, инстанцированием в соответствии с этим определенных объектов и определением их взаимоотношений.
Т.е. для установленного языка определяется представление его грамматики, а также интерпретатор предложений этого языка.
Мотивация
Если некоторая задача возникает часто, то имеет смысл представить ее конкретные проявления в виде предложений на простом языке. Затем можно будет создать интерпретатор, который решает задачу, анализируя предложения этого языка. источник codelab.ru codelab.ru оригинал codelab.ru codelab.ru оригинал источник
источник оригинал codelab.ru codelab.ru
- LiteralExpression проверяет, соответствует ли входная строка литералу, который хранится в объекте подкласса. оригинал codelab.ru источник codelab.ru
- AlternationExpression проверяет, соответствует ли строка одной из альтернатив. источник codelab.ru codelab.ru оригинал
- RepetitionExpression проверяет, если в строке повторяющиеся вхождения выражения, совпадающего с тем, что хранится в объекте. codelab.ru оригинал источник codelab.ru
И так далее. оригинал источник codelab.ru codelab.ru
Очевидно, что все это выполняется рекурсивно, теоретически без ограничения глубины вложенности разных выражений друг в друга. источник codelab.ru codelab.ru оригинал
Признаки применения, использования паттерна Интерпретатор (Interpreter)
Используйте паттерн-интерпретатор, когда есть язык для интерпретации, предложения которого можно представить в виде абстрактных синтаксических деревьев. Лучше всего этот паттерн работает, когда: codelab.ru codelab.ru оригинал источник- Грамматика достаточно проста.
Для сложных грамматик иерархия классов становится слишком громоздкой и неуправляемой. В таких случаях лучше применять генераторы синтаксических анализаторов, поскольку они могут интерпретировать выражения, не строя абстрактных синтаксических деревьев, что экономит память, а возможно, и время. оригинал codelab.ru источник codelab.ru - Эффективность не является главным критерием.
Наиболее эффективные интерпретаторы обычно не работают непосредственно с деревьями, а сначала транслируют их в другую форму. Так, регулярное выражение часто преобразуют в конечный автомат. Но даже в этом случае сам транслятор можно реализовать с помощью данного паттерна интерпретатор. codelab.ru оригинал codelab.ru источник
Решение
codelab.ru оригинал codelab.ru источник codelab.ru codelab.ru источник оригинал
Участники паттерна Интерпретатор (Interpreter)
codelab.ru codelab.ru оригинал источник- AbstractExpression (RegularExpression) - абстрактное выражение.
Объявляет абстрактную операцию Interpret, общую для всех узлов в абстрактном синтаксическом дереве. источник оригинал codelab.ru codelab.ru - TerminalExpression (LiteralExpression) – терминальное (конечное, неделимое, элементарное) выражение.
Реализует операцию Interpret для терминальных символов грамматики. Для каждого терминального символа – необходим отдельный экземпляр в предложении. источник оригинал codelab.ru codelab.ru - NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions) - нетерминальное выражение.
По одному такому классу требуется для каждого грамматического правила:
R :: = Rl R2... Rn.
Хранит переменные экземпляра типа AbstractExpression для каждого символа от Rl до Rn. Реализует операцию Interpret для нетерминальных символов грамматики. Эта операция рекурсивно вызывает себя же для переменных, представляющих Rl R2... Rn. источник codelab.ru оригинал codelab.ru - Context – контекст.
Содержит информацию, глобальную по отношению к интерпретатору. источник codelab.ru codelab.ru оригинал - Client – клиент.
Строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее отдельное предложение на языке с данной грамматикой. Дерево составлено из экземпляров классов Nonterminal-Expression.Вызывает операцию Interpret и Terminal-Expression. источник codelab.ru codelab.ru оригинал
Схема использования паттерна Интерпретатор (Interpreter)
Клиент строит (или получает в готовом виде) предложение в виде абстрактного объектного синтаксического дерева, в узлах которого находятся объекты классов NonterminalExpression и Terminal-Expression. Затем клиент инициализирует контекст и вызывает операцию Interpret у самого верхнего узла NonterminalExpression-а. codelab.ru источник codelab.ru оригиналОперации Interpret в каждом узле используют контекст для сохранения и доступа к состоянию интерпретатора. codelab.ru источник оригинал codelab.ru
Вопросы, касающиеся реализации паттерна Интерпретатор (Interpreter)
У реализаций паттернов интерпретатор и компоновщик есть много общего. Следующие вопросы относятся только к интерпретатору: оригинал codelab.ru codelab.ru источник- Создание абстрактного синтаксического дерева.
Паттерн интерпретатор не поясняет, как создавать дерево, то есть разбор выражения не входит в его задачу. Создать дерево разбора может таблично-управляемый или написанный вручную (обычно методом рекурсивного спуска) анализатор, а также сам клиент. источник codelab.ru оригинал codelab.ru - Определение операции Interpret.
Определять операцию Interpret в классах выражений необязательно. Если создавать новые интерпретаторы приходится часто, то лучше воспользоваться паттерном посетитель и поместить операцию Interpret в отдельный объект-посетитель. Например, для грамматики языка программирования будет нужно определить много операций над абстрактными синтаксическими деревьями: проверку типов, оптимизацию, генерацию кода и т.д. Лучше, конечно, использовать посетителя и не определять эти операции в каждом классе грамматики. источник оригинал codelab.ru codelab.ru - Разделение терминальных символов с помощью паттерна приспособленец.
Для грамматик, предложения которых содержат много вхождений одного и того же терминального символа, может оказаться полезным разделение этого символа, т.е. совместное его использование. Хорошим примером служат грамматики компьютерных программ, поскольку в них каждая переменная встречается в коде многократно. В примере из раздела Мотивация терминальный символ dog (для моделирования которого используется класс LiteralExpression) может попадаться много раз.
В терминальных узлах обычно не хранится информация о положении в абстрактном синтаксическом дереве. Необходимый для интерпретации контекст предоставляют им родительские узлы. Налицо различие между разделяемым (внутренним) и передаваемым (внешним) состояниями, так что вполне применим паттерн приспособленец.
Например, каждый экземпляр класса LiteralExpression для dog получает контекст, состоящий из уже просмотренной части строки. И каждый такой экземпляр делает в своей операции Interpret одно и то же - проверяет, содержит ли остаток входной строки слово dog, - безотносительно к тому, в каком месте дерева этот экземпляр встречается. оригинал codelab.ru источник codelab.ru
- Грамматику легко изменять и расширять.
Поскольку для представления грамматических правил в паттерне используются классы, то для изменения - или расширения грамматики можно применять наследование. Существующие выражения можно модифицировать постепенно, а новые определять как вариации старых (компоновка, агрегация старых). codelab.ru codelab.ru оригинал источник - Простая реализация грамматики.
Реализации классов, описывающих узлы абстрактного синтаксического дерева, похожи. Такие классы легко кодировать, а зачастую их может автоматически сгенерировать компилятор или генератор синтаксических анализаторов. codelab.ru оригинал codelab.ru источник
- Сложные грамматики трудно сопровождать.
В паттерне интерпретатор определяется по меньшей мере один класс для каждого правила грамматики (для правил, определенных с помощью формы Бэкуса-Наура – BNF, может понадобиться и более одного класса). Поэтому сопровождение грамматики с большим числом правил иногда оказывается трудной задачей. Для ее решения могут быть применены другие паттерны. Но если грамматика очень сложна, лучше прибегнуть к другим методам, например, воспользоваться генератором компиляторов или синтаксических анализаторов. codelab.ru codelab.ru оригинал источник - Добавление новых способов интерпретации выражений.
Паттерн интерпретатор позволяет легко изменить способ вычисления выражений. Например, реализовать красивую печать выражения вместо проверки входящих в него типов можно, просто определив новую функциональность операции Interpret в классах выражений.
Ну а если вам приходится часто создавать новые способы интерпретации выражений, подумайте о применении паттерна посетитель. Это поможет избежать изменения классов, описывающих грамматику. codelab.ru codelab.ru источник оригинал
Пример
Рассмотрим систему для манипулирования и вычисления булевых выражений. Терминальными символами (TerminalExpression-ы) в этом языке являются булевы переменные, то есть константы true и false. Нетерминальные символы (NonterminalExpression) представляют выражения, содержащие операторы and, or и not. Приведем определение грамматики (упрощая задачу, мы здесь игнорируем приоритеты выполнения операторов и предполагаем, что их учет возложен на объект, строящий дерево разбора): источник оригинал codelab.ru codelab.ruAndExp ::= BooleanExp 'and' BooleanExp
OrExp : : = BooleanExp ' or ' BooleanExp
NotExp ::= 'not' BooleanExp
Constant ::= “true” | “false”
VariableExp ::= “A” | “B” | ... |”X'”| “Y” | “Z” codelab.ru codelab.ru оригинал источник
Здесь мы подробно опишем только классы BooleanExp, VariableExp и AndExp. Классы OrExp и NotExp аналогичны классу AndExp. Класс Constant представляет булевы константы: Constant. codelab.ru источник codelab.ru оригинал
Известные применения паттерна Интерпретатор (Interpreter)
Паттерн интерпретатор широко используется в компиляторах, реализованных с помощью объектно-ориентированных языков, например в компиляторах Smalltalk. В языке SPECTalk этот паттерн применяется для интерпретации форматов входных файлов. В библиотеке QOCA для разрешения ограничений он применяется для вычисления ограничений. codelab.ru оригинал источник codelab.ruНо применять паттерн интерпретатор лучше в тех случаях, когда иерархию классов можно представлять себе как описание языка на декларативном. оригинал источник codelab.ru codelab.ru
Родственные паттерны
Реализации: java(8) +добавить реализацию
1) Constant.java, code #492[автор:this]
2) BooleanExp.java, code #493[автор:this]
3) Context.java, code #494[автор:this]
4) VariableExp.java, code #495[автор:this]
5) AndExp.java, code #496[автор:this]
6) OrExp.java, code #497[автор:this]
7) NotExp.java, code #498[автор:this]
8) Expression1.java, code #499[автор:this]