CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Относительный путь к файлу. (39742 hits)
#Интерактивная, динамическая подгрузка картинок. (69845 hits)
#"Липкие" окна. (32175 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (69733 hits)
#Добавление истории операций(undo&redo) в компонент. (39981 hits)
#Сравнение алгоритмов сортировки массива. (182120 hits)
#Утилиты. (114409 hits)
#Пирамидальная сортировка. (203701 hits)
#Поразрядная сортировка, общий принцип. (130615 hits)
#Рисование тора. (34735 hits)
#Переключатель в кириллицу. (32811 hits)
#Рисование Фрактала (листьев папоротника). (53157 hits)
#Вставка новой записи в таблицу БД. (36576 hits)
#Выборка всех записей таблицы. (33510 hits)
#Вычисление медианы заданной выборки. (49212 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (116821 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (46434 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (38880 hits)
#Выборка конкретной записи из таблицы. (32845 hits)
#Случайный выбор элемента при неизвестном их количестве. (36694 hits)


Главная >> Каталог задач >> Паттерны >> Поведения >> Интерпретатор (Interpreter)

Интерпретатор (Interpreter)

Aвтор:
Дата:
Просмотров: 148034
реализации(java: 8шт...) +добавить

Имя

«Паттерн
Interpreter»

Интерпретатор - паттерн поведения объектов, реализующий динамические алгоритмы с помощью декларативного описания.

Условия, Задача, Назначение

В ряде случаев приложение на разных этапах выполнения использует одни и те же алгоритмы обработки данных, или, точнее, многие алгоритмы функционирования приложения строятся из более простых, элементарных неизменяющихся под-алгоритмов.
В этом случае во избежание дублирования кода, можно просто вынести все эти элементарные алгоритмы (составляющие) – каждый в свой отдельный класс и далее разложить на них все большие участки, т.е. скомпоновать из них все остальные большие алгоритмы обработки. Только в этом случае для каждой новой функциональности по-прежнему надо будет писать новые классы компоновщики, стоящиеся из отдельных маленьких участков.
На самом деле здесь было бы неплохо составлять лишь некоторую схему компоновки новых алгоритмов этими элементарными составляющими и далее передавать ее в некоторый строитель (что-то вроде паттерна-строитель), который и собирал бы на основе этого полноценную архитектуру данного алгоритма.
Паттерн-интерпретатор именно это и предлагает. Подход можно отнести к декларативному программированию: мы имеем лишь полноценные классы для всех элементарных составляющих, далее на декларативном уровне (в виде любых грамматических инструкций, правил и т.д.) мы составляем лишь схему их сборки, расположения и взаимодействия – в результате получая совершенно новую функциональность, не создавая никаких новых классов.
Можно сказать, этим мы определяем некий интерпретируемый язык и класс-интерпретатора, который будет заниматься его распознаванием, инстанцированием в соответствии с этим определенных объектов и определением их взаимоотношений.
Т.е. для установленного языка определяется представление его грамматики, а также интерпретатор предложений этого языка.

Мотивация

Если некоторая задача возникает часто, то имеет смысл представить ее конкретные проявления в виде предложений на простом языке. Затем можно будет создать интерпретатор, который решает задачу, анализируя предложения этого языка.
Например, поиск строк по образцу - весьма распространенная задача. Регулярные выражения - это стандартный язык для задания образцов поиска. Вместо того чтобы программировать специализированные алгоритмы для сопоставления строк с каждым образцом, не проще ли построить алгоритм поиска так, чтобы он мог интерпретировать регулярное выражение, описывающее множество строк-образцов?
Паттерн интерпретатор определяет грамматику простого языка, представляет предложения на этом языке и интерпретирует их. Для приведенного примера паттерн описывает определение грамматики и интерпретации языка регулярных выражений.
Предположим, что они описаны следующей грамматикой:
expression  ::= literal | alternation | sequence | repetition | '(' expression ')'
alternation ::= expression | expression
sequence    ::= expression & expression
repetition   ::= expression *
literal : := 'a' | 'b' | 'c' | . . . { 'a' | 'b' | 'c' | ... }*
где expression - это составной символ, a literal - терминальный символ, определяющий простые слова.
Паттерн интерпретатор использует класс для представления каждого правила грамматики. Символы в правой части правила - это переменные экземпляров таких классов. Для представления приведенной выше грамматики требуется всего 5 классов: абстрактный класс RegularExpression и четыре его подкласса LiteralExpression, AlternationExpression, SequenceExpression и RepetitionExpression. В последних 3 подклассах определены переменные для хранения подвыражений:

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

 - представляет выражение:
raining & (dogs | cats) *
Мы можем создать интерпретатор регулярных выражений, определив в каждом подклассе RegularExpression операцию Interpret, принимающую в качестве аргумента контекст, где нужно интерпретировать выражение. Контекст состоит из входной строки и информации о том, как далеко по ней мы уже продвинулись.
В каждом подклассе RegularExpression операция Interpret производит сопоставление с оставшейся частью входной строки. Например:
  • LiteralExpression проверяет, соответствует ли входная строка литералу, который хранится в объекте подкласса.
  • AlternationExpression проверяет, соответствует ли строка одной из альтернатив.
  • RepetitionExpression проверяет, если в строке повторяющиеся вхождения выражения, совпадающего с тем, что хранится в объекте.

И так далее.

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

Признаки применения, использования паттерна Интерпретатор (Interpreter)

Используйте паттерн-интерпретатор, когда есть язык для интерпретации, предложения которого можно представить в виде абстрактных синтаксических деревьев. Лучше всего этот паттерн работает, когда:
  • Грамматика достаточно проста.
    Для сложных грамматик иерархия классов становится слишком громоздкой и неуправляемой. В таких случаях лучше применять генераторы синтаксических анализаторов, поскольку они могут интерпретировать выражения, не строя абстрактных синтаксических деревьев, что экономит память, а возможно, и время.
  • Эффективность не является главным критерием.
    Наиболее эффективные интерпретаторы обычно не работают непосредственно с деревьями, а сначала транслируют их в другую форму. Так, регулярное выражение часто преобразуют в конечный автомат. Но даже в этом случае сам транслятор можно реализовать с помощью данного паттерна интерпретатор.

Решение

Участники паттерна Интерпретатор (Interpreter)

  1. AbstractExpression (RegularExpression) - абстрактное выражение.
    Объявляет абстрактную операцию Interpret, общую для всех узлов в абстрактном синтаксическом дереве.
  2. TerminalExpression (LiteralExpression) – терминальное (конечное, неделимое, элементарное) выражение.
    Реализует операцию Interpret для терминальных символов грамматики. Для каждого терминального символа – необходим отдельный экземпляр в предложении.
  3. NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions) - нетерминальное выражение.
    По одному такому классу требуется для каждого грамматического правила:
    R :: = Rl R2... Rn.
    Хранит переменные экземпляра типа AbstractExpression для каждого символа от Rl до Rn. Реализует операцию Interpret для нетерминальных символов грамматики. Эта операция рекурсивно вызывает себя же для переменных, представляющих Rl R2... Rn.
  4. Context – контекст.
    Содержит информацию, глобальную по отношению к интерпретатору.
  5. Client – клиент.
    Строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее отдельное предложение на языке с данной грамматикой. Дерево составлено из экземпляров классов Nonterminal-Expression.Вызывает операцию Interpret и Terminal-Expression.

Схема использования паттерна Интерпретатор (Interpreter)

Клиент строит (или получает в готовом виде) предложение в виде абстрактного объектного синтаксического дерева, в узлах которого находятся объекты классов NonterminalExpression и Terminal-Expression. Затем клиент инициализирует контекст и вызывает операцию Interpret у самого верхнего узла NonterminalExpression.
Далее в каждом узле вида NonterminalExpression вызов операции Interpret запускает операции Interpret для каждого подвыражения. Для класса TerminalExpression операция Interpret определяет базу рекурсии, т.е. конечную точку рекурсии.

Операции Interpret в каждом узле используют контекст для сохранения и доступа к состоянию интерпретатора.

Вопросы, касающиеся реализации паттерна Интерпретатор (Interpreter)

У реализаций паттернов интерпретатор и компоновщик есть много общего. Следующие вопросы относятся только к интерпретатору:
  1. Создание абстрактного синтаксического дерева.
    Паттерн интерпретатор не поясняет, как создавать дерево, то есть разбор выражения не входит в его задачу. Создать дерево разбора может таблично-управляемый или написанный вручную (обычно методом рекурсивного спуска) анализатор, а также сам клиент.
  2. Определение операции Interpret.
    Определять операцию Interpret в классах выражений необязательно. Если создавать новые интерпретаторы приходится часто, то лучше воспользоваться паттерном посетитель и поместить операцию Interpret в отдельный объект-посетитель. Например, для грамматики языка программирования будет нужно определить много операций над абстрактными синтаксическими деревьями: проверку типов, оптимизацию, генерацию кода и т.д. Лучше, конечно, использовать посетителя и не определять эти операции в каждом классе грамматики.
  3. Разделение терминальных символов с помощью паттерна приспособленец.
    Для грамматик, предложения которых содержат много вхождений одного и того же терминального символа, может оказаться полезным разделение этого символа, т.е. совместное его использование. Хорошим примером служат грамматики компьютерных программ, поскольку в них каждая переменная встречается в коде многократно. В примере из раздела Мотивация терминальный символ dog (для моделирования которого используется класс LiteralExpression) может попадаться много раз.
    В терминальных узлах обычно не хранится информация о положении в абстрактном синтаксическом дереве. Необходимый для интерпретации контекст предоставляют им родительские узлы. Налицо различие между разделяемым (внутренним) и передаваемым (внешним) состояниями, так что вполне применим паттерн приспособленец.
    Например, каждый экземпляр класса LiteralExpression для dog получает контекст, состоящий из уже просмотренной части строки. И каждый такой экземпляр делает в своей операции Interpret одно и то же - проверяет, содержит ли остаток входной строки слово dog, - безотносительно к тому, в каком месте дерева этот экземпляр встречается.
У паттерна интерпретатор есть следующие достоинства и недостатки:
Достоинства >>
  1. Грамматику легко изменять и расширять.
    Поскольку для представления грамматических правил в паттерне используются классы, то для изменения - или расширения грамматики можно применять наследование. Существующие выражения можно модифицировать постепенно, а новые определять как вариации старых (компоновка, агрегация старых).
  2. Простая реализация грамматики.
    Реализации классов, описывающих узлы абстрактного синтаксического дерева, похожи. Такие классы легко кодировать, а зачастую их может автоматически сгенерировать компилятор или генератор синтаксических анализаторов.
Недостатки >>
  1. Сложные грамматики трудно сопровождать.
    В паттерне интерпретатор определяется по меньшей мере один класс для каждого правила грамматики (для правил, определенных с помощью формы Бэкуса-Наура – BNF, может понадобиться и более одного класса). Поэтому сопровождение грамматики с большим числом правил иногда оказывается трудной задачей. Для ее решения могут быть применены другие паттерны. Но если грамматика очень сложна, лучше прибегнуть к другим методам, например, воспользоваться генератором компиляторов или синтаксических анализаторов.
  2. Добавление новых способов интерпретации выражений.
    Паттерн интерпретатор позволяет легко изменить способ вычисления выражений. Например, реализовать красивую печать выражения вместо проверки входящих в него типов можно, просто определив новую функциональность операции Interpret в классах выражений.
    Ну а если вам приходится часто создавать новые способы интерпретации выражений, подумайте о применении паттерна посетитель. Это поможет избежать изменения классов, описывающих грамматику.

Пример

Рассмотрим систему для манипулирования и вычисления булевых выражений. Терминальными символами (TerminalExpression-ы) в этом языке являются булевы переменные, то есть константы true и false. Нетерминальные символы (NonterminalExpression) представляют выражения, содержащие операторы and, or и not. Приведем определение грамматики (упрощая задачу, мы здесь игнорируем приоритеты выполнения операторов и предполагаем, что их учет возложен на объект, строящий дерево разбора):

BooleanExp ::= VariableExp | Constant | OrExp | AndExp | NotExp | “(“ BooleanExp “)”
AndExp ::= BooleanExp 'and' BooleanExp
OrExp : : = BooleanExp ' or ' BooleanExp
NotExp ::= 'not' BooleanExp
Constant ::= “true” | “false”
VariableExp ::= “A” | “B” | ... |”X'”| “Y” | “Z”
Определим две операции над булевыми выражениями. Первая - Evaluate - вычисляет выражение в контексте, где каждой переменной присваивается истинное или ложное значение. Вторая - Replace - порождает новое булево выражение, заменяя новым выражением некоторую переменную (т.е. все ее вхождения). Эта операция демонстрирует, что паттерн интерпретатор можно использовать не только для вычисления выражений; в данном случае он манипулирует самим выражением.

Здесь мы подробно опишем только классы BooleanExp, VariableExp и AndExp. Классы OrExp и NotExp аналогичны классу AndExp. Класс Constant представляет булевы константы: Constant.

BooleanExp определяет интерфейс всех классов, которые описывают булевы выражения: BooleanExp.
Интерфейс Context определяет отображение между переменными и булевыми значениями, которые в языке Java представляются константами true и false. Т.е. выступает в роли среды, содержащей все определенные пользователем булевы переменные: Context.
Класс VariableExp представляет именованную переменную: VariableExp.
Класс AndExp представляет выражение, получающееся в результате применения операции логического И к двум булевым выражениям: AndExp.
Класс OrExp представляет результат применения логического ИЛИ к 2 булевым выражениям: OrExp.
Класс NotExp представляет логическое отрицание: NotExp.
Теперь наглядно можем составить интерпретацию логического выражения. Пусть нужно рассчитать:
(true and x) orand (not x))
Код интерпретатора примет вид: Expression1(Часть 1).
С такими значениями х и у выражение равно true. Чтобы вычислить его при других значениях переменных, достаточно просто изменить контекст, т.е. поменять значения переменных в этом контексте.
И, наконец, мы можем заменить переменную у новым выражением и повторить вычисление: Expression1 (Часть 2).
 
При этом важно отметить, что данный пример использования интерпретатора, когда мы вручную инстанцируем т.н. составные части интерпретатора, затем их запускаем – мало используется на практике. Смысл интерпретатора – принять на вход декларативное выражение в самом элементарном виде (строки т.е.) – транслировать его (распарсить специальным функционалом «транслятора»), инстанцировать соответствующие объекты в определенных взаимоотношениях по этой схеме – и запустить что-то вроде того же Evaluete. Здесь для простоты примера мы опускаем реализацию транслятора, которая имеет слабое отношение к объяснению архитектуры паттерна интерпретатор.
 
На этом примере проиллюстрирована важная особенность паттерна интерпретатор: «интерпретация» предложения может означать самые разные действия.
Из трех операций, определенных в классе BooleanExp, Evaluate наиболее близка к нашему интуитивному представлению о том, что интерпретатор должен интерпретировать программу или выражение и возвращать простой результат.
Но и операцию Replace можно считать интерпретатором. Его контекстом является имя заменяемой переменной и подставляемое вместо него выражение, а результатом служит новое выражение. Даже операцию Сору допустимо рассматривать как интерпретатор с пустым контекстом. Трактовка операций Replace и Сору как интерпретаторов может показаться странной, поскольку это всего лишь базовые операции над деревом. Примеры в описании паттерна посетитель демонстрируют, что все три операции разрешается вынести в отдельный объект-посетитель «интерпретатор», тогда аналогия станет более очевидной.
Паттерн интерпретатор - это нечто большее, чем распределение некоторой операции по иерархии классов, составленной с помощью паттерна компоновщик.
Мы рассматриваем операцию Evaluate как интерпретатор, поскольку иерархию классов BooleanExp мыслим себе как представление некоторого языка. Если бы у нас была аналогичная иерархия для представления агрегатов автомобиля, то вряд ли мы стали бы считать такие операции, как Weight (вес) и Сору (копирование), интерпретаторами, несмотря на то что они распределены по всей иерархии классов, - просто мы не воспринимаем агрегаты автомобиля как язык. Тут все дело в точке зрения: опубликуй мы грамматику агрегатов автомобиля, операции над ними можно было трактовать как способы интерпретации соответствующего языка.
 
 

Известные применения паттерна Интерпретатор (Interpreter)

Паттерн интерпретатор широко используется в компиляторах, реализованных с помощью объектно-ориентированных языков, например в компиляторах Smalltalk. В языке SPECTalk этот паттерн применяется для интерпретации форматов входных файлов. В библиотеке QOCA для разрешения ограничений он применяется для вычисления ограничений.

Если рассматривать данный паттерн в самом общем виде (то есть как операцию, распределенную по иерархии классов, основанной на паттерне компоновщик), то почти любое применение компоновщика содержит и интерпретатор.

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

Родственные паттерны

Обычно вместе с паттерном интерпретатор используется компоновщик: абстрактное синтаксическое дерево - это пример применения паттерна компоновщик.
Далее - приспособленец показывает варианты совместного использования терминальных символов в абстрактном синтаксическом дереве.
Итератор: интерпретатор может пользоваться итератором для обхода структуры.
Посетителя можно использовать для инкапсуляции в одном классе поведения каждого узла абстрактного синтаксического дерева.

Реализации:

java(8)   +добавить

1) Constant.java на java, code #492[автор:this]
2) BooleanExp.java на java, code #493[автор:this]
3) Context.java на java, code #494[автор:this]
4) VariableExp.java на java, code #495[автор:this]
5) AndExp.java на java, code #496[автор:this]
6) OrExp.java на java, code #497[автор:this]
7) NotExp.java на java, code #498[автор:this]
8) Expression1.java на java, code #499[автор:this]