Інтерпретатор - Куток програміста

Намір

Для необхідної мови, визначення представлення для її граматики разом з інтепретатором, який використовує представлення для розпізнавання речень у мові.

Мотивація

Якщо певний тип проблеми трапляється доволі часто, в такому разі, ефективніше виразити її у вигляді речень простої мови. Ви можете побудувати інтерпретатор, який вирішує проблему, розпізнаючи речення. Наприклад, пошук рядків, які відповідають певному шаблону, являється поширеним завданням. Регулярні вирази являються стандартною мовою шаблонів для рядків символів. Краще, щоб алгоритми пошуку могли інтерпретувати регулярні вирази, ніж будувати специфічні алгоритми для співставлення кожного шаблона з рядком. Шаблон Інтерпретатор описує, як визначити граматику для простих мов, які представляють речення у мові, і інтерпретувати їх самостійно. У цьому прикладі, шаблон описує як визначити граматику для регулярних виразів, як представити певний регулярний вираз, і як інтерпретувати цей регулярний вираз. Припустимо, що наступні граматичні правила визначають регулярні вирази:

вираз ::= літерал | альтернатива | послідовність | повторення | '(' вираз ')' 
альтернатива ::= вираз '|' вираз
послідовність ::= вираз '&' вираз
повторення ::= вираз '*' 
літерал ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*

Символ вираз, являється початковим символом, і літерали являються простими символами, які визначають прості слова. Шаблон Інтерпретатор використовує клас для представлення кожного граматичного правила. Символи з правої сторони від правил являються примірниками змінних цих класів. Вищевказана граматика представляється наступними класами: абстрактний клас RegularExpression і його чотири потомки LiteralExpression, AlternationExpression, SequenceExpression і RepetitionExpression. Останні чотири класи визначають змінні які утримують підвирази.

Кожен регулярний вираз визначений цією граматикою представляється абстрактним синтаксичним деревом, виконаним з примірників цих класів. Наприклад, абстрактне дерево синтаксису

представляє наступний регулярний вираз

raining & (dogs | cats) *

Ми можемо створити інтерпретатор для цього регулярного виразу, визначаючи операцію Interpret для кожного дочірнього класу RegularExpression. Операція Interpret отримує в якості аргументу контекст у якому інтерпретувати вираз. Контекст містить вхідний рядок символів і інформацію про те, скільки символів було розпізнано до цього моменту. Кожен потомок класу RegularExpression реалізовує метод Interpret для розпізнавання частини вхідного рядка, базуючись на поточному контексті. Наприклад:

LiteralExpression перевірить чи вхідний рядок співпадає з літеральним виразом, який він містить,
AlternationExpression перевірить чи вхідний рядок співпадає з будь-яким з його альтернатив,
RepetitionExpression перевірятиме, чи вхідний рядок містить множинні копії виразу, які він повторює,

і так далі.

Застосовуваність

Використовуйте шаблон Інтерпретатор коли існує мова для інтерпретації, і ви можете представити вирази мовою у вигляді абстрактного синтаксичного дерева. Шаблон Інтерпретатор працює коли:

граматика являється простою. Для складних граматик, ієрархія класів стає великою і не управляємою. Засоби у вигляді генераторів парсерів являються кращою альтернативою для таких випадків. Вони можуть інтерпретувати вирази без побудови абстрактних синтаксичних дерев, що може зберегти пам'ять і час.
Ефективність не являється критичною. Найбільш ефективні інтерпретатори зазвичай не являються реалізованими прямо за допомогою абстрактних синтаксичних дерев. Наприклад, регулярні вирази зазвичай часто перетворюються на машини. Але навіть тоді, транслятор може бути реалізованим за допомогою Інтерпретатора, отож все-одно застосовується даний шаблон.

Структура

Учасники

AbstractExpression (RegularExpression)
- оголошує абстрактну операцію Interpret, яка являється загальною для усіх вузлів у дереві абстрактного синтаксису.
TerminalExpression (LiteralExpression)
- реалізовує операцію Interpret, яка асоціюється з системними символами граматики; вимагається примірник для кожного системного символу у реченні.
NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions)
- один такий клас вимагається для кожного правила вигляду R ::= R1 R2 ... Rn у граматиці; підтримує примірники змінних типу AbstractExpression для кожного символу починаючи з R1 і закінчуючи Rn.
- Реалізовує операцію Interpret для несистемних символів у граматиці. Операція Interpret зазвичай викликає себе рекурсивно на змінних представлених в починаючи з R1 і закінчуючи Rn.
Context
- містить інформацію яка є глобальною для інтерпретатора.
Client
- Будує (або йому передається) абстрактний синтаксичне дерево, яке представляє певне речення у мові, яку визначає граматика. Абстрактний синтаксичне дерево складається з примірників класів NonterminalExpression і TerminalExpression.
- Викликає операцію Interpret.

Співпрацювання

Клієнт будує (або йому передається) речення у вигляді абстрактного дерева синтаксису примірників класів NonterminalExpression і TerminalExpression. Після чого клієнт ініціалізує контекст і викликає операцію Interpret.
Кожен вузол типу NonterminalExpression визначає метод Interpret у термінах кожного підвиразу. Операція Interpret кожного класу TerminalExpression визначає базовий випадок у рекурсії.
Операція Interpret у кожному вузлі використовує контекст для збереження і доступу до стану процесу інтерпретації.

Наслідки

Шаблон Інтерпретатор має наступні переваги і недоліки:

Легко змінити і розширювати граматику. Через те, що шаблон використовує класи для представлення граматичних правил, ви можете використовувати успадковуваність для зміни чи розширення граматики. Існуючі вирази можуть бути редагованими, і нові вирази можуть визначатись як варіації відносно старих.
Реалізовувати граматику також легко. Класи, які визначають вузли у абстрактному дереві синтаксису мають подібну реалізацію. Ці класи легко написати, і часто їхнє генерування може бути автоматизоване за допомогою компілятора або генератора парсерів.
Складні граматики важко підтримувати. Шаблон Інтерпретатор визначає хоча б один клас для кожного правила у граматиці (граматичні правила, визначені використовуючи форму BNF, можуть потребувати множинних класів). Отже граматики, які містять багато правил, можуть виявитись важкими в підтримці і управлінні. Інші шаблони проектування можуть бути застосованими для пом'якшення проблеми (перегляньте секцію Реалізація). Але часто граматика являється складною, інші техніки на подобі парсерів або генераторів компілятора являються більш правильними.
Додавання нових способів для інтерпретування виразів. Шаблон Інтерпретатор полегшує оцінку виразу новим способом. Наприклад, ви можете підтримувати вирази перевірки вводу символів, визначаючи нову операцію на класах виразів. Якщо ви продовжуєте створення нових шляхів інтерпретування виразів, тоді перегляньте шаблон Відвідувач для запобігання зміни граматичних класів.

Реалізація

Шаблони Інтерпретатор і Композитор поділяють багато проблем реалізації. Наступні проблеми є специфічними для шаблону Інтерпретатор:

Створення абстрактного синтаксичного дерева. Шаблон Інтерпретатор не об'яснює як створити абстрактне дерево синтаксису. Тобто він не розповідає як виконувати парсинг. Абстрактне дерево синтаксису може бути створеним за допомогою табличного парсеру, за допомогою рекурсивно-спадаючого парсеру або власними силами клієнта.
Визначення операції Interpret. Ви не маєте визначати операцію Interpret у класах виразів. Якщо доводиться часто створювати новий інтерпретатор, тоді краще використовувати шаблон Відвідувач для вкладання інтерпретатора у окремий об'єкт “відвідувача”. Наприклад, граматика для мови програмування буде мати занадто багато операцій над абстрактним деревом синтаксису, на подобі перевірки типів, оптимізацію, генерування коду і так далі. Буде більш ймовірне використання відвідувача для запобігання цих операцій на кожному класі граматики.
Зберігання системних символів за допомогою шаблону Легка Вага. Граматики, чиї речення містять велику кількість системних символів можуть отримати вигоду від розподілення однієї копії даних символів. Граматики для комп'ютерних програм являються хорошими прикладами — кожна змінна програми буде з'являтися у багатьох місцях коду. У прикладі секції Мотивація, речення може мати системний символ dog (який змодельований за допомогою класу theLiteralExpression), який з'являється велику кількість разів.

Системні вузли зазвичай не зберігають інформацію про їхнє розміщення у абстрактному синтаксичному дереві. Батьківські класи передають їм будь-який контекст, який необхідний їм для інтерпретації. Оскільки існує різниця між розподіленими (внутрішніми) станами і зовнішніми, застосовується шаблон Легка Вага. Наприклад, кожний примірник класу LiteralExpression для символу “dog” отримує контекст, який містить підрядки, які були співставленими до поточного моменту. І кожен примірник LiteralExpression виконує однакову роботу у операції Interpret — він перевіряє чи наступна частина вводу містить рядок “док” - неважливо де поточний примірник з'являється у дереві.

Приклад коду

Ось два приклади. Перший являється повним прикладом у Smaltalk для перевірки чи послідовність співпадає з регулярним виразом. Наступний приклад являється С++ програмою для оцінки бульових виразів. Тестувач регулярних виразів перевіряє чи символьний рядок співпадає з потрібним регулярним виразом. Регулярний вираз визначається наступною граматикою:

вираз ::= літерал | альтернатива | послідовність | повторення | '(' вираз ')' 
альтернатива ::= вираз '|' вираз
послідовність ::= вираз '&' вираз
повторення ::= вираз 'repeat' 
літерал ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*

Дана граматика являється невеликою модифікацією граматики з прикладу секції Мотивація. Ми змінили конкретний синтаксис регулярних виразів, через те, що символ “*” не може бути суфіксною операцією у Smalltalk. Отож ми використовуємо повторення замість нього. Няприклад, регулярний вираз

(('dog ' | 'cat ') repeat & 'weather')

співпадає з ввідним рядком "dog dog cat weather". Для реалізації парсера, ми визначаємо п'ять класів, які описані в блоку Мотивація даного шаблону. Клас SequenceExpression має примірники змінних expression1 and expression2 для його потомків абстрактного синтаксичного дерева. AlternationExpression зберігає його альтернативи у примірниках змінних variablesalternative1 і alternative2, поки RepetitionExpression утримує вираз, який він повторює у його змінній repetition. LiteralExpression має примірник змінної, яка утримує список об'єктів (зазвичай символів). Вона утримує літеральний примірник рядка символів, які повинні зійтись з ввідною послідовністю символів. Операція match реалізовує інтерпретатор для регулярного виразу. Кожен з класів, який визначає абстрактне синтаксичне дерево реалізовує цю операцію. Вона отримує ввідний стан inputState у вигляді аргументу, який представляє поточний стан процесу співставлення. Цей поточний стан характеризується набором ввідних потоків, які представляють множину вхідних даних, які регулярний вираз може прийняти до поточного моменту. Поточний стан являється найбільш важливим для операції повторення. Наприклад, якщо регулярний вираз мав вигляд:

'a' repeat

в такому разі інтерпретатор може співставити “а”, “аа”, “ааа” і так далі. Якщо він мав би вигляд 'a' repeat & 'bc' тоді він може співставити “abc”, “aabc”, “aaabc” і так далі. Але якщо регулярний вираз мав би наступний вигляд:

'a' repeat & 'abc'

в такому разі співставлення рядка “aabc” через регулярний вираз “'a' repeat” спричинить два ввідних потоки, один, який співставив один символ потоку і інший, який співставив два символи. Потік, який прийняв тільки один символ співставить іншу послідовність “abc”. Тепер ми розглянемо визначення методу match для кожного класу, який визначає регулярний вираз. Визначення для SequenceExpression співставляє кожний з його дочірніх виразів у послідовності. Зазвичай він буде видаляти рядки, з його inputStaste.

match: inputState 
	^ expression2 match: (expression1 match: inputState)

Клас AlternationExpression буде повертати стан, який складається з об'єднання станів з інших альтернатив. Визначення матоду match для AlternationExpression має вигляд:

match: inputState 
	| finalState | 
	finalState := alternative1 match: inputState. 
	finalState addAll: (alternative2 match: inputState). 
	^ finalState

Операція match для RepetitionExpressiontries для знаходження стільки повторень, як це можливо:

match: inputState 
	| aState finalState | 
	aState := inputState. 
	finalState := inputState copy. 
	[aState isEmpty] 
		whileFalse: 
			[aState := repetition match: aState. 
			finalState addAll: aState]. 
		^ finalState

Цей вихідний стан зазвичай містить більше станів, ніж вхідний стан, через те, що RepetitionExpression може співставляти один, два або множинні випадки повторень з вхідного стану. Вихідний стан представляє усі ці можливості, дозволяючи дочірнім елементам регулярного виразу вирішити, який стан являється коректним. І на кінець, визначення методу match для LiteralExpression намагається, співставити його компоненти з кожним можливим вхідним потоком. Він зберігає тільки ці вхідні потоки які співпадають:

match: inputState 
| finalState tStream | 
finalState := Set new. 
inputState 
	do: 
	[:stream | tStream := stream copy. 
		(tStream nextAvailable: 
		components size 
		) = components 
		ifTrue: [finalState add: tStream] 
	]. 
	^ finalState

Наступне повідомлення Available розширює вхідний потік. Зверніть увагу на те, як повернений стан, містить копії вхідного потоку, запевняючи, що співставлення літералу ніколи не змінить вхідний потік. Це являється важливим, тому що кожна альтернатива примірника AlternationExpression повинна бачити ідентичні копії ввідного потоку. Тепер коли ми визначили класи, які виготовляють абстрактне синтаксичне дерево, ми можемо описувати як він буде побудований. Ми визначемо декілька операцій для класів RegularExpression, отож оцінка виразу Smalltalk буде продукувати абстрактне синтаксичне дерево для відповідного регулярного виразу. Це дозволяє нам використовувати вбудований Smalltalk компілятор у вигляді парсера для регулярних виразів. Для побудови абстрактного синтаксичного дерева, нам потрібно визначити “|”, “repeat” і “&” у вигляді операцій над RegularExpression. Ці операції визначаються у класі RegularExpression наступним чином:

& aNode 
	^ SequenceExpression new 
		expression1: self expression2: aNode asRExp 
repeat 
	^ RepetitionExpression new repetition: self 
	| aNode 
		^ AlternationExpression new 
		alternative1: self alternative2: aNode asRExp
asRExp 
	^ self

Операція asRExp перетворюватиме літерали у примірника класу RegularExpression. Ці операції визначені у класі String:

& aNode 
	^ SequenceExpression new 
		expression1: self asRExp expression2: aNode asRExp 
repeat 
	^ RepetitionExpression new repetition: self 
| aNode 
	^ AlternationExpression new 
		alternative1: self asRExp alternative2: aNode asRExp 
asRExp 
	^ LiteralExpression new components: self

Якщо ми визначемо ці операції вище у класовій ієрархії (SequenceableCollection у Smalltalk-80, IndexedCollection у Smalltalk/V), тоді вони будуть також визначеними для класів на подобі Array і OrderedCollection. Це дозволить регулярному виразу співставляти послідовності будь-яких об'єктів. Наступний приклад являється системою для маніпулювання і оцінки бульових виразів, реалізованою у С++. Системні символи у цій мові являються бульовими змінними, тобто такими, які містять true або false. Не системні символи представляють вирази, які містять операції and, or i andnot. Граматика наступна:

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, оцінює бульовий вираз у контексті, який присвоює true або false для кожної змінної. Друга операція, Replace, продукує новий бульовий вираз, заміною змінної на вираз. Replace показує як шаблон Інтерпретатор може бути використаний не тільки для оцінки виразів. У цьому випадку, він маніпулює виразом самостійно. Ми показали тут тільки деталі класів BooleanExp,VariableExp і AndExp. Класи OrExp і NotExp являються подібними до AndExp. Клас Constant представляє бульові константи. Клас BooleanExp визначає інтерфейс для усіх класів, які визначають бульовий вираз:

class BooleanExp { 
public: 
	BooleanExp(); 
	virtual ~BooleanExp(); 
	virtual bool Evaluate(Context&) = 0; 
	virtual BooleanExp* Replace(const char*, BooleanExp&) = 0; 
	virtual BooleanExp* Copy() const = 0; 
} ;

Клас Context визначає співставлення між змінними і булевими значеннями, які ми представимо за допомогою С++ констант true і false. Клас Context має наступний інтерфейс:

class Context { 
public: 
	bool Lookup(const char*) const; 
	void Assign(VariableExp*, bool); 
} ;

Клас VariableExp представляє названу змінну:

class VariableExp : public BooleanExp { 
public: 
	VariableExp(const char*); 
	virtual ~VariableExp(); 
	virtual bool Evaluate(Context&); 
	virtual BooleanExp* Replace(const char*, BooleanExp&); 
	virtual BooleanExp* Copy() const; 
private: 
	char* _name; 
} ;

Конструктор отримує ім'я змінної в якості аргументу:

VariableExp::VariableExp (const char* name) { 
	_name = strdup(name); 
}

Оцінка змінної повертає її значення відносно поточного контексту.

bool VariableExp::Evaluate (Context& aContext) { 
	return aContext.Lookup(_name); 
}

Копіювання змінної повертає новий примірник VariableExp:

BooleanExp* VariableExp::Copy () const { 
	return new VariableExp(_name); 
}

Для заміни змінної у виразі, ми перевіряємо, щоб побачити чи змінна має таке ж ім'я як та, ім'я якої було передано в якості аргументу:

BooleanExp* VariableExp::Replace ( const char* name, BooleanExp& exp ) { 
	if (strcmp(name, _name) == 0) { 
		return exp.Copy(); 
	} else { 
		return new VariableExp(_name); 
	} 
}

Клас AndExp представляє вираз, який складається з операції “І” між двома бульовими виразами.

class AndExp : public BooleanExp { 
public: 
	AndExp(BooleanExp*, BooleanExp*); 
	virtual ~ AndExp(); 
	virtual bool Evaluate(Context&); 
	virtual BooleanExp* Replace(const char*, BooleanExp&); 
	virtual BooleanExp* Copy() const; 
private: 
	BooleanExp* _operand1; 
	BooleanExp* _operand2; 
} ; 

AndExp::AndExp (BooleanExp* op1, BooleanExp* op2) 
{ 
	_operand1 = op1; 
	_operand2 = op2; 
}

Оцінка виразу AndExp розраховує його операнди і повертає логічне “І” результату.

bool AndExp::Evaluate (Context& aContext) {
	return _operand1->Evaluate(aContext) && _operand2->Evaluate(aContext);
}

Клас AndExp реалізовує операції Copy i Replace за допомогою рекурсивних викликів над її операндами:

BooleanExp* AndExp::Copy () const
{
	return new AndExp(_operand1->Copy(), _operand2->Copy());
}
BooleanExp* AndExp::Replace (const char* name, BooleanExp& exp) {
	return new AndExp(
			_operand1->Replace(name, exp),
			_operand2->Replace(name, exp)
	) ;
}

Тепер ми можемо визначити булевий вираз

true and x) or (y and (not x))

і оцінити його хибність чи справедливість відносно змінних х і у:

BooleanExp* expression ;
Context context ; 

VariableExp* x = new VariableExp("X") ; 
VariableExp* y = new VariableExp("Y") ;

expression = new OrExp(
	new AndExp(new Constant(true), x),
	new AndExp(y, new NotExp(x))
) ;

context.Assign(x, false) ;
context.Assign(y, true) ;
bool result = expression->Evaluate(context) ;

Значенням поточного виразу являється true для поточних значень х та у. Ми можемо перерахувати значення виразу, використовуючи інші присвоєння до змінних, просто змінюючи контекст. На кінець, ми можемо замінити змінну на новий вираз і повторно прорахувати його:

VariableExp* z = new VariableExp("Z") ;
NotExp not_z(z) ;  
 
BooleanExp* replacement = expression->Replace("Y", not_z) ;
context.Assign(z, true) ;
result = replacement->Evaluate(context) ;

Приклад ілюструє важливий аспект відносно шаблону Інтерпретатор: велика кількість типів операцій можуть “інтерпретувати” речення. Для трьох операцій визначених для BooleanExp, операція Evaluate найкращим чином підходить для нашої ідеї про те, що інтерпретатор повинен робити — інтерпретувати програму або вираз і повертати простий результат. Однак, Replace також можна розглядати як інтерпретатор. Він являється інтерпретатором чий контекст являється ім'ям змінної, яка замінюється разом з виразом, на який вона замінюється, і результатом якого є інший вираз. Навіть Copy може виступати у ролі інтерпретатора, як такий, що немає контексту. Може здаватись дивним прийняття методів Replase i Copy за інтерпретаторів, тому що вони є просто базові операції на деревах. Приклади шаблона Відвідувач ілюструє як усі ці операції можуть бути переробленими у окремі “інтерпретатори”-відвідувачі, тобто показує глибоку схожість. Шаблон Інтерпретатор являється більшим ніж просто операції, які поширені по класовій ієрархії, яку використовує шаблон Композитор. Ми розглядаємо метод Evaluate інтерпретатором тому, що ми думаємо про класову ієрархію BooleanExp як про таку, що відображає мову. У подібній класовій ієрархії для відображення запчастин, ми малоймовірно будемо розглядати операції на подобі Weight i Copy у якості інтерпретаторів, незважаючи на те, що вони поширюються крізь класову ієрархію, яку використовує шаблон Композитор. Ми просто не думаємо про запчастини як про мову. Це питання перспективи. Якщо ми б почали створювати граматику запчастин, в такому разі ми могли б розглядати операції над запчастинами як спосіб інтерпретувати мову.

Відомі використання

Шаблон інтерпретатор широко використовується у компіляторах, які реалізовані за допомогою об'єктно-орієнтованих мов програмування, якими являються компілятори Smalltalk. SPECTalk використовує шаблон для інтерпретування описів ввідних форматів файлів. Підсистема вирішування обмежень QOCA використовує його для оцінки обмежень. У найбільш загальній формі (тобто операції передані по ієрархії класів на подобі шаблону Композитор), майже кожне використання шаблону Композитор буде також містити шаблон Інтерпретатор. Але шаблон Інтерпретатор повинен застосовуватись до випадків, у яких ви бажаєте думати про ієрархію класів як про мову.

Споріднені шаблони

Композитор: абстрактне дерево синтаксису являється примірником шаблону Композитор. Легка Вага: показує як розподіляти системні символи у абстрактному дереві синтаксису. Ітератор: інтерпретатор може використовувати Ітератор для перебору структури. Відвідувач: може бути використаним для підтримки поведінки у кожному вузлі у абстрактному дереві синтаксису одного класу.