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


с. 1

Глава 20. Интерпретатор (Interpreter)

Автор


Константин Йовков

В тази тема

В тази тема ще разгледаме шаблона от поведенчески тип “Интерпретатор” (Interpreter). Този шаблон специфицира начина, по който се оценяват изрази върху даден език, изграден над определена формална граматика. В рамките на темата ще разгледаме отделните компоненти на шаблона, както и особеностите при имплементацията му. Накрая ще изброим неговите предимствата и недостатъци и също така ще представим няколко негови познати приложения и няма да пропуснем да поговорим за допирните му точки с няколко други шаблона.

Клас, Поведенчески

Цел на шаблона


Целта на шаблона “Интерпретатор” (Interpreter) e следната:
За даден език, да се дефинира репрезентация над граматиката, върху която е съставен, заедно с т.нар. интерпретатор, който използва съставената граматическа репрезентация, за да оценява изрази над дадения език. Звучи сложно, но всъщност не е. Като цяло, шаблонът “Интерпретатор”(Interpreter) доста близък до шаблона “Композиция” (Composite), като за връзката между двата може да прочетете по-надолу.

Други наименования


Ограничен език (Little language)

Преводач


Проблем


В процеса на софтуерна разработка понякога се случва да се сблъскаме с проблеми, които изискват създаването на механизъм за задълбочен анализ на съдържанието на входящите данни, както и механизъм, който да обработва вече анализирания вход. В такива случаи могат да се ползват различни транслатори, които да трансформират данните на входа на програмата в някакъв специфичен формат или структура. Могат да се ползват регулярни изрази, чрез които да се провери дали входните низови данни отговарят на някакъв шаблон. Вариантите са много.

Представете си обаче следния проблем: налага ни се да пишем програма, която трябва да пресмята математически изрази, представени в т.нар.“Обратна Полска Нотация” (Reverse Polish Notation). Такива изрази имат следния формат:



  • 3 4 +

Това е представянето на израза „3 + 4” в Обратна Полска Нотация.

  • 4 2 - 10 *

Това е представянето на израза „(4 – 2) * 10” в Обратна Полска Нотация.

  • 4 3 - 2 1 + *

А това е представянето на израза „(4 – 3) * (2 + 1)” в Обратна Полска Нотация.

Как бихме могли да постъпим, за да напишем програма, която оценява изрази, зададени в този формат ? Нещо повече: как бихме могли да направим програмата така, че да се поддържа някаква вътрешна структура за даден израз с променливи, която след това може да се преизползва за оценка на същия израз с вече зададени стойности за променливите.

Съществуват няколко начина и подхода, чрез които да се формулира решение на проблема. Прилагането на шаблона „Интерпретатор”(Interpreter) е един от тях, като освен това е един от едно от най-добрите и доказани подходи, защото позволява гъвкавост при допълнителни бъдещи промени в структурата на изразите и като цяло, не е никак сложен за реализация.

На първо време, да опишем граматиката, с която ще се работим тук:





  • Израз ::= плюс | минус | променлива | число

  • Плюс ::= израз израз +

  • Минус ::= израз израз –

  • Променлива ::= ‘a’ | ‘b’ | ‘c’ | … | ‘z’

  • Цифра ::= ‘0’ | ‘1’| … | ‘9’

  • Число ::= цифра | цифра число

Нека уточним какво значи написаното дотук: Променливи могат да бъдат буквите от ‘a’ до ‘z’. Правата разделителна черта в случая значи ‘или’. И в този ред на мисли, виждаме, че нещо може да се нарича ‘цифра’, ако стойността му е ‘0’ или ‘1’, или ‘2’ и т.н. или ‘9’. По аналогичен начин можете да определите какви видове изрази могат да съществуват върху тази граматика.

И така, искаме да оценяваме изрази, представени в Обратна Полска Нотация и вече разполагаме с граматиката, която описва тази репрезентация. Нека пристъпим към самия „Интерпретатор”(Interpreter).

В общи линии, шаблонът „Интерпретатор”(Interpreter) се състои от няколко участника: Контекст (Context), Абстрактен израз (Abstract Expression), Краен израз (Terminal Expression), Съставен израз (Nonterminal Expression) и Клиент (Client), като за взаимовръзката помежду им може да прочете в раздела „Структура” ([TODO: link to Interpreter - линкът ще сочи към сек­ция „Структура”])

асд
[@author: описание на проблема с подходяща UML клас диаграма]

[@author: описание на проблема с подходяща UML обектна диаграма]

Приложимост


Преди да разгледаме от какво е съставен шаблонът „Интерпретатор” (Interpreter) и как с негова помощ се разрешават някои проблеми, ще разгледаме в кои случаи да се избира точно той. Като цяло, шаблонът „Интерпретатор”(Interpreter) е най-добре приложим в случаите, в които граматиката, върху която е конструиран езикът, не е особено сложна, не е обемна и е лесно модифицируема. Обикновено тежките и големи граматики могат да създадат сериозни затруднения за програмистите, защото за тях ще се налага да се създават голям брой класове и поддържането на йерархията помежду им би била потенциален източник на проблеми. Затова е хубаво шаблонът „Интерпретатор” (Interpreter) да се прилага в ситуации, в които се работи със сравнително прости езици, чиито граматики могат да бъдат лесно представени в дървовиден вид. Повечето имплементации на SQL са добър пример за това.

И тъй като, работейки с този шаблон, пряко обработваме някаква дървовидна структура, е добре да отбележим, че тук ефикасността и бързодействието не са точно нещото, за което трябва да се тревожим и над което трябва да се фокусираме. Разбира се, за едно приложение от истинския живот тези неща са от критично значение, ето защо за постигането им се ползват т.нар. транслатори, които значително опростяват дървовидната структура и чак тогава се извършва реалното действие на шаблона “Интерпретатор” (Interpreter).


Структура


По-долу виждате структурата на шаблона „Интерпретатор” (Interpreter).

Описание


В тази секция ще се запознаем отблизо с него – ще се разкрием кои са компонентите, които го изграждат и ще поговорим за взаимодействието между тях.
Участници

Шаблонът „Интерпретатор” е съставен от пет компонента. По-надолу ще обясним идеята зад всеки един от тях.

  • Абстрактен израз (AbstractExpression)

Дефинира абстрактна операция Interpret, която е обща за всички листа в абстрактното синтактично дърво.

[@author: Да се даде като пример името на класа/интерфейса за абстрактен израз от примера, даден в секция „Проблем“]

  • Краен израз (TerminalExpression)

Имплементира действието на Interpret операцията за крайните символи в граматиката. Необходима е инстанция на такъв обект за всеки краен символ в израза.

[@author: Да се даде като пример името на класа за краен израз (литерал, краен символ) от примера, даден в секция „Проблем“]

  • Съставен израз (NonterminalExpression)

Такъв клас е необходим за всяко едно правило от типа R::=R1R2…Rn в граматиката. Той съдържа инстанции от тип AbstractExpression за всеки от символите от R1 до Rn и имплементира операцията Interpret за некрайните символи в граматиката. Операцията Interpret обикновено се извиква рекурсивно за променливите, представляващи символите от R1 до Rn.

[@author: Да се даде като пример името на класа за некраен (съста­вен n-арен) израз от примера, даден в секция „Проблем“]

  • Контекст (Context)

Съдържа информация, която е глобална за интерпретатора. Например, в Context-a може да се съхраняват изразът, който трябва да се интерпретира, както и резултатът от интерпретацията.

[@author: Да се даде като пример името на класа за контекст от примера, даден в секция „Проблем“]

  • Клиент (Client)

Построява (или приема) абстрактно синтактично дърво, представляващо конкретен израз в езика, дефиниран над граматиката. Абстрактното синтактично дърво обикновено се съставя от инстанции на класовете, представляващи компонентите в шаблона NonterminalExpression и TerminalExpression.

[@author: Да се даде като пример името на класа за клиент от примера, даден в секция „Проблем“]
Взаимодействия

Стартовата точка на процеса на интерпретация на даден израз дава Клиент-ът (Client). В началото той трансформира израза в дървовидна структура, която е съставена от инстанции на крайни(Terminal Expression) и съставни(NonTerminal Expression) изрази (или приема вече изготвена такава). След това се инициализира контекстът (Context). Както вече знаете, контекстът(Context) е сърцевината на шаблона – той пази информация както за вече оценената част от даден израз, така и за тази част от него, която тепърва ще се интерпретира. Както крайните, така и съставните изрази, имплементират класа AbstractExpression и съответно задават собствена логика за операцията Interpret. В смисъла на един рекурсивен подход, операцията Interpret за всеки краен израз фактически представлява едно ново ‘дъно’ на рекурсията, докато операцията Interpret за всеки съставен израз дефинира поредната рекурсивна стъпка. Резултатът и в двата случая се записва и съхранява в контекста (Context).

Оценка на шаблона


Шаблонът Интерпретатор има няколко предимства и недостатъка:

  1. Лесно могат да се отразят промени или разширения на граматиката

Поради причината, че при реализацията на шаблона се използват класове, можем да приложим един от принципите на обектно-ориентираното програмиране, а именно – наследяване, за да променим или разширим граматиката. При такъв сценарий, съществуващите изрази могат да бъдат променени постепенно и дори може да бъдат конструирани нови изрази като вариации на вече съществуващи такива. То дава възможност да се конструира граматиката така, че така бъде гъвкава и устойчива на допълнителни разширения и промени.

  1. Лесно имплементиране на граматиката

Граматиката се имплементира лесно, защото класовете, които дефинират листата в абстрактното синтактично дърво (AST), имат близки една до друга имплементации. Обикновено тези класове имат общ супер-клас, ето защо като структура са доста близки един до друг, а създаването им не е трудно, като често операцията може да бъде автоматизирана с някакъв помощен инструмент.

  1. Сложните граматики се поддържат трудно

Както споменахме малко по-рано, шаблонът “Интерпретатор” (Interpreter) дефинира по поне един клас за всяко правило в граматиката (като е възможно в някои случаи да се налага създаването на повече от един клас за едно правило, но няма да се спираме на тях). По този начин граматиките, които съдържат голям брой правила могат да бъдат доста трудни боравенето с тях и особено по отношение на поддръжката им. Този проблем може да бъде решен с комбинирането на шаблона “Интерпретатор”(Interpreter) с някои други шаблони, но когато граматиката е много сложна за предпочитане са други техники като парсери или транслатори, с помощта на които абстрактното синтактично дървото да се опрости. Все пак, съветваме Ви да избягвате употребата на “Интерпретатор”(Interpreter) в такива ситуации.

  1. Добавяне на нови начини за интерпретиране на изразите [TODO: link to Visitor]]

Шаблонът Интерпретатор улеснява значително процеса по оценяване на даден израз по един нов начин. Например, може да се имплементира поддръжка на `pretty printing` или `type-checking` като се дефинира нова операция в класовете, обработващи изразите над граматиката. В случай, че често се налага да добавяте нови начини за интерпретиране на дадени изрази, обмислете ползването на шаблона „Посетител” (Visitor), който ще спомогне затова да избегнете промените в граматическите класове.


Реализация


Имплементацията на шаблона „Интерпрета­тор“ (Interpreter) всъщност представлява употреба на шаблона „Композиция“ (Composite) [TODO: link to Composite] приложен за представяне на грама­тика на език. Като цяло, при имплементацията на „Интерпретатор” (Interpreter) се състои от няколко стъпки.

  1. Създаване на абстрактно синтактично дърво (АСТ)

    Шаблонът „Интерпретатор” (Interpreter) не дефинира как точно трябва да се създаде абстрактното синтактично дърво над граматиката. Това решение трябва да бъде взето от Вас, програмистите. Тук може да се ползват всякакви подходи за построяването на дървото, като то дори може да бъде предварително създадено и директно да бъде предоставяно на интерпретатор-а. За повече яснота по отношение на тази стъпка, погледнете примерите в края на главата.





  2. Дефиниране на операцията Interpret - употреба на шаблона „Посетител“ (Visitor) [TODO: link to Visitor]]

Операцията Interpret е втората стъпка от процеса по имплементиране на шаблона. Първият вариант за нейното местонахождение е тя да бъде описана в абстрактния клас Expression, след което всеки израз (бил той краен или некраен) да имплементира своето уникално поведение за операцията.

Възможно е обаче и друго – да се ползва шаблонът “Посетител” (Visitor). В този случай операцията Interpret се дефинира в отделна инстанция на имплементацията на шаблона „Посетител”(Visitor). Например, за граматика, описваща някакъв програмен език, ще има много операции върху различни абстрактни синтактични дървета – проверка на типовете, оптимизация, компилация и т.н. В този случай шаблонът „Посетител” е по-добрият избор за това къде да се дефинира операцията Interpret, защото по този начин ще се спести дефиниране на уникално поведение по време на операцията Interpret за всеки клас, представляващ граматиката.





  1. Споделяне на литерали - употреба на шаблона „Ми­ниобект“ (Flyweight) [TODO: link to Flyweight]]

В случаите, в които граматиките, чиито изречения имат множество повтарящи се символи, може да се приложи употреба на шаблона „Миниобект”(Flyweight) и често повтарящите се символи да се преизползват. Граматиките, дефиниращи компютърни програми, могат да са пример за това – в тях често се случва една програмна променлива да присъства на много места из кода.

ТODO: Допълни с пример.


Познати приложения


Шаблонът “Интерпретатор” (Interpreter) има приложения в множество езици, компилатори, транслатори и т.н. Пример за това са някои от компилаторите, разработени върху езика Smalltalk, като SPECTalk, който ползва разглеждания тук шаблон за интерпретиране на описания на файлови формати за програмен вход.

Всъщност, често се получава така, че реализациите на шаблона се ползват от много хора, без те да подозират за него. Да се спрем на езика Java и по-конкретно на пакета java.util.regex. Той съдържа само два класа – java.util.regex.Pattern и java.util.regex.Matcher. Тези два класа предоставят реализация на шаблона „Интерпретатор”(Interpreter), която се ползва за компилиране на регулярни изрази и интерпретиране на други изрази, спрямо даден, вече компилиран регулярен израз.



TODO: малко детайли за самата реализация

Свързани шаблони


Композиция“ (Composite) [TODO: link to Composite]

Както споменахме малко по-рано, шаблоните „Интерпретатор” и “Композиция” са доста подобни един на друг. Разликата идва от това, че имплементацията на „Интерпретатор” (Interpreter) е приложение на имплементацията на „Композиция” (Composite) върху някаква формална граматика. Обикновено, когато се строи абстрактното синтактично дърво на граматиката за един „Интерпретатор”(Interpreter), се прави реализация на шаблона „Композиция”(Composite).


Посетител“ (Visitor) [TODO: link to Visitor]

Шаблонът “Посетител”(Visitor) също може да взаимодейства с шаблона „Интерпретатор”(Interpreter), защото може да се използва за поддръжка на поведението на всяко ‘листо’ в абстрактното синтактично дърво.


Миниобект“ (Flyweight) [TODO: link to Flyweight]

Миниобект”(Flyweight) е третият шаблон, който може да се работи успешно в колаборация с „Интерпретатор”(Interpreter). Той може да се ползва за целта да се опише как да се споделят и преизползват крайни изрази (TerminalExpression) в рамките на абстрактното синтактично дърво.


Итератор“ (Iterator) [TODO: link to Iterator]

Когато правите реализация на „Интерпретатор”(Interpreter) вземете под внимание и шаблонът „Итератор”(Iterator), защото той може да се ползва от вашия „Интерпретатор”(Interpreter) за обхождане не дървовидната структура, най-вече в случаите, в които рекурсивният подход (например) изисква и отнема солидно количество ресурси.



Пример: ... (Java)


Нека разгледаме следния проблем. Искаме да напишем програма, която конвертира римски числа в арабски. Например, подавайки на входа на програмата на числото „LXII” (което е по-правилно да разглеждаме като низ) да получим отговор арабското число ‘62’.

С други думи казано, целта ни е да напишем програма, която да интерпретира съдържанието на даден низ (който ще наричаме ‘римско число’) в арабско число, на чиято стойност съответства единствено и само даденият низ (и обратното).

Да направим анализ с какво разполагаме и да помислим как да постъпим ?

Имаме сравнително малка и не особено сложна граматика – римските числа се изразяват с буквите ‘I’, ‘V’, ‘X’, ‘L’ и ‘C’ и трябва да напишем програма, която транслира валидните символните комбинации между тях в съответстващите им арабски числа.

Нека го направим с помощта на шаблона „Интерпретатор”(Interpreter). Първо ще си дефинираме контекста. Той ще представлява един обикновен клас, който ще съдържа тази част от римския израз, която остава да бъде интерпретирана, както и арабското число, което се е получило от вече интерпретираната в даден момент част. Дефинираме подходящи accessor-методи за полетата за вход (римското число) и изход (арабското число), за да можем да увеличаваме стойността на входа и да намаляваме дължината на изхода.


Context.java

public class Context {


private String input;

private int output;
public Context(String input) {

this.input = input;

}
public String getInput() {



return input;

}
public void setInput(String input) {



this.input = input;

}
public int getOutput() {



return output;

}
public void setOutput(int output) {



this.output = output;

}

}


След това, нека дефинираме абстрактната операция Interpret. За целта ще си направим абстрактен клас Expression.java, който ще дефинира метод interpret(Context context), в чието тяло ще се прави обръщение към няколко абстрактни метода. Реалната работа, която ще се извърши от тях, ще бъде описана в наследниците на класа Expression.

Видовете ‘Expression’ ще бъдат четири типа – например, OneExpression.java, който ще определя по ключовото поведение, когато се работи с числа от 1 до 10. В случая, ключови са моментите, в които трябва да се определят числата 4 и 9, защото тяхното римско представяне е с два символа, а числото 5 се представя с един, но абсолютно уникален символ.

Другите три типа Expression ще описват поведението на интерпретатора с числа между 10 и 99 (TenExpression), числа между 100 и 1000 (HundredExpression). Засега нашият „Интерпретатор”(Interpreter) няма да поддържа превод на римски репрезентации на числа, по-големи от 1000.




Expression.java

public abstract class Expression {

public abstract String one();
public abstract String four();
public abstract String five();
public abstract String nine();
public abstract int multiplier();

public void interpret(Context context) {

if (context.getInput().length() == 0) {

return;

}
if (context.getInput().startsWith(nine())) {

context.setOutput(context.getOutput() + (9 * multiplier()));

context.setInput(context.getInput().substring(2));

} else if (context.getInput().startsWith(four())) {

context.setOutput(context.getOutput() + (4 * multiplier()));

context.setInput(context.getInput().substring(2));

} else if (context.getInput().startsWith(five())) {

context.setOutput(context.getOutput() + (5 * multiplier()));

context.setInput(context.getInput().substring(1));

}
while (context.getInput().startsWith(one())) {

context.setOutput(context.getOutput() + (1 * multiplier()));

context.setInput(context.getInput().substring(1));

}

}



}

Важно е да се отбележи, че в нашия случай, нямаме крайни изрази. Всички видове изрази тук са съставни, защото те са състав от буквеното съдържание на граматиката. Тъй като тук нямаме разни разделители или оператори върху изрази за интерпретиране, няма да има нужда да дефинираме крайни изрази.

Класът OneExpression изглежда така:


OneExpression.java

public class OneExpression extends Expression {

public String one() {

return "I";

}
public String four() {



return "IV";

}
public String five() {



return "V";

}
public String nine() {



return "IX";

}
public int multiplier() {



return 1;

}

}


Както виждате, тук задаваме строго определено поведение за римските числа от 1 до 9, включително, като това включва: как ще се интерпретира числата 1, 4, 5 и 9 и какъв ще е множителят, ако римското числото с дължина 1 е префикс на друго римско число и трябва да пресметнем крайния резултат.


Класовете TenExpression.java и HundredExpression.java изглеждат по аналогичен начин. Те дефинират съответно


TenExpression.java

public class TenExpression extends Expression {

public String one() {

return "X";

}
public String four() {



return "XL";

}
public String five() {



return "L";

}
public String nine() {



return "XC";

}
public int multiplier() {



return 10;

}

}






HundredExpression.java

public class HundredExpression extends Expression {

public String one() {

return "C";

}
public String four() {



return "CD";

}
public String five() {



return "D";

}
public String nine() {



return "CM";

}
public int multiplier() {



return 100;

}

}


На практика дотук дефинирахме елементите на абстрактното синтактично дърво, а сега е време да построим самото дърво. Както вече знаете, един възможен начин за неговото изграждане е то да се построи в клиента (Client), след което същият този Client да се обърне към имплементациите на операцията Interpret(Context context) и да трансформира римско число в арабско. Ето и самият клиент.

Много е важно тук да поговорим за последователността на вкарване на листата (видовете Expression) в дървото. Както виждате, първо вкарваме инстанция на HundredExpression.java, след това такава на TenExpression.java и чак накрая инстанция на OneExpression.java. Последователността е важна, защото в следващият по-надолу цикъл видовете листа се обхождат едно по едно и защото при на всяка стъпка на самата интерпретация на римско число е важно да се интерпретира възможно най-дългият префикс от оставащата част от римското число.

Може да експериментирате и да размените последователността на поставяне на изразите в дървото. Ще се убедите, че резултатите след това ще са некоректни.




Client.java

public class Client {

public static void main(String[] args) {

String roman = "LXII";

Context context = new Context(roman);

// Build the 'parse tree'

ArrayList tree = new ArrayList();

tree.add(new HundredExpression());

tree.add(new TenExpression());

tree.add(new OneExpression());


// Interpret

Iterator iterator = tree.iterator();



while (iterator.hasNext()) {

Expression exp = iterator.next();

exp.interpret(context);

}

System.out.println(roman + " = " + Integer.toString(context.getOutput()));



}

}




Упражнения


  1. Кога се прилага шаблонът „Интерпретатор“ (Interpreter) [TODO: link to Interpreter]?

  2. Обяснете ролята на всеки от класовете, участващи в шаблона „Ин­терпретатор“ (Interpreter) [TODO: link to Interpreter].

  3. Кой структурен шаблон се използва за представяне структурата на израз от езика? [TODO: link to Interpreter - линкът ще сочи към сек­ция „Реализация”]

  4. Допълнителни задачи

    1. Интерпретатор на булеви изрази.

Решения и упътвания


[@author: решения и упътвания на поставените задачи в „Упражнения”]


с. 1

скачать файл