CodeLAB
на главную карта сайта обратная связь
каталог | задачи | паттерны | исходники | стат | форумы | ссылки
 гость
искать в
Главная >> Каталог задач >> Паттерны >> Поведения >> Интерпретатор (Interpreter)

<< назад
распечатать обсудить >>


Интерпретатор (Interpreter)
реализации: java, количество: 8

Aвтор: this
Дата: 05.10.2007
Просмотров: 57997
Рейтинг: 0/0,0(0)
+
реализации(исходники) +добавить

Имя

«Паттерн
Interpreter» codelab.ru источник оригинал codelab.ru

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

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

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

Мотивация

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

codelab.ru codelab.ru оригинал источник

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

оригинал codelab.ru источник codelab.ru

 - представляет выражение: оригинал codelab.ru источник codelab.ru
raining & (dogs | cats) * оригинал codelab.ru источник codelab.ru
Мы можем создать интерпретатор регулярных выражений, определив в каждом подклассе RegularExpression операцию Interpret, принимающую в качестве аргумента контекст, где нужно интерпретировать выражение. Контекст состоит из входной строки и информации о том, как далеко по ней мы уже продвинулись. codelab.ru codelab.ru источник оригинал
В каждом подклассе RegularExpression операция Interpret производит сопоставление с оставшейся частью входной строки. Например: источник 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 источник оригинал

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

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

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

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

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

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

Пример

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

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” codelab.ru оригинал codelab.ru источник
Определим две операции над булевыми выражениями. Первая - Evaluate - вычисляет выражение в контексте, где каждой переменной присваивается истинное или ложное значение. Вторая - Replace - порождает новое булево выражение, заменяя новым выражением некоторую переменную (т.е. все ее вхождения). Эта операция демонстрирует, что паттерн интерпретатор можно использовать не только для вычисления выражений; в данном случае он манипулирует самим выражением. источник codelab.ru codelab.ru оригинал

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

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

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

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

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

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

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

Обычно вместе с паттерном интерпретатор используется компоновщик: абстрактное синтаксическое дерево - это пример применения паттерна компоновщик. codelab.ru оригинал источник codelab.ru
Далее - приспособленец показывает варианты совместного использования терминальных символов в абстрактном синтаксическом дереве. 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]


<< назад наверх
распечатать обсудить >>

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.035383 секунд
Количество запросов к БД: 14, gzip: 20.9kb/105.7kb(81%)