Атрибутни преводни граматики

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

Например, искаме не само да изградим дърво за анализ на аритметични изрази, но и да изчислим стойността на този израз. Може би дори без изграждане на самото дърво за анализ.

Този подход се наричасинтактично контролиран превод.

Съдържание

Синтактично контролиран превод[редактиране]

Определение:

Насочена към синтаксис дефиницияе граматика без контекст с атрибути и правила. Атрибутите са свързани с граматически символи, а правилата са свързани с продукции.

Определение:

Насочен към синтаксис превод(английски синтаксисно насочен превод)е превод, при който някои действия се извършват незабавно по време на анализирането на низ, без да се използва междинно представяне под формата на дърво за анализ.

Синтактично контролираният превод въвежда два нови обекта:атрибутизнак за превод.

Определение:

Атрибут(англ. attribute)- допълнителни данни, свързани с граматически символи. Ако $X$ е знак и$a$ е един от неговите атрибути, тогава стойността на $a$ в някакъв възел в дървото за анализ с етикет $X$ се записва като $X.a$. Ако възлите на дървото за разбор са имплементирани като записи или обекти, тогава $X$ атрибутите могат да бъдат имплементирани като полета с данни в записи, представляващи $X$ възли. Атрибутите могат да бъдат от всякакъв вид: числа, типове, справочни таблици или низове.

Определение:

Дърво на анализ, във всеки възел на който атрибутите вече са изчислени, се наричаанотирано(английски анотирано), а процесът на изчисляване на тези атрибути се наричаанотиранена дървото на анализ.

Определение:

Превеждащият символе нетерминал, който се разширява до $\varepsilon$ и в момента на разширяване изпълнява действието, свързано с него. Действията се изписват във фигурни скоби до знака за превод.

Ще разгледаме като пример граматиката за аритметични изрази с операторите $+$ и $*$:

$ S \to E \\ E \to E + T \mid T \\ T \to T * F \mid F \\ F \to n \mid (E) $

Заслужава да се отбележи, че няма гаранция, че има дори един ред на обхождане на дървото за анализ, който оценява всички атрибути във възлите. Помислете например за следните нетерминали $A$ и $B$:

Продуктови семантични правила

$A \до B$	$A.s = B.i \\ B.i = A.s+1$

Тези правила са циклични: невъзможно е да се оцени $A.s$ във възел или $B.i$ в дъщерен възел, без да се знае стойността на другия атрибут. След това ще разгледаме два класа синтактично контролирани граматики, за които редът на оценка на атрибута може да бъде недвусмислено определен.

Синтезируеми атрибути[редактиране]

Определение:

Атрибут, чиято стойност зависи от стойностите на атрибутите на децата на този възел или от други атрибути на този възел, тогава атрибутът се наричасинтезиран(англ. synthesized attribute).

Определение:

Граматиката се наричаS-приписана дефиниция(англ. S-attributed definition), ако само операциите за присвояване на стойности на други атрибути се извършват с атрибути и само атрибутите на този излъчващ символ са достъпни вътре в символите за превод. Тоест в граматиката се използват само синтезирани атрибути. Дървото за разбор за такава граматика винаги може да бъде анотирано чрез следване на семантичните правила отдолу нагоре, от листа до корени.

Пример за граматика на S-атрибут[редактиране]

Нека напишем синтактично контролирана дефиниция за граматиката на аритметичните изрази с операторите $+$ и $*$ (тук $\$ и $\$ са символи за превод. Ако един и същ нетерминал се среща няколко пъти в продукция, ние ще добавим индекси към нея, броейки от началото на продукцията.):

Продукти Семантични правила Обяснения

$S \към E$	$S.val=E.val$
$E_0 \до E_1 + T\ \$	$ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $	Във къдрави скоби — действия на знака за превод ADD. $op_1$, $op_2$ и $res$ са атрибути на знаци за превод.
$E \към T$	$E.val=T.val$
$T_0 \до T_1 * F \ \$	$MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$	Във къдрави скоби — действия на знака за превод MUL. $op_1$, $op_2$ и $res$ са атрибути на знаци за превод.
$T \към F$	$T.val=F.val$
$F \до n$	$F.val=n.val$
$F \към (E)$	$F.val=E.val$

В нашия пример можете да видите, че $val$ зависи само от децата в дървото за анализ, което означава, че е синтезиран атрибут. Резултатът от множителя ($MUL.res$) зависи само от атрибутите на самия множител ($MUL.op_1$ и $MUL.op_2$), което означава, че той също може да се синтезира (подобно на суматора $ADD$).

След такъв анализ $S.val$ ще съдържа изчислената стойност на израза. Можете например веднага да го отпечатате, като добавите правилото $\$ към него.

Наследени атрибути[редактиране]

Определение:

Атрибут, чиято стойност зависи от стойностите на родствените или родителските атрибути на възела, се наричанаследен атрибут(англ. inherited attribute).

Определение:

Една граматика се наричаL-приписана дефиниция(англ. L-attributed definition), ако стойностите на наследените атрибути зависят само от родителите и братята отляво (тоест не зависят от стойностите на атрибутите на братята отдясно).

Пример за граматика на L-атрибут[редактиране]

$ D \to TL \\ T \to int \mid real \\ L \to L,id \mid id $

Нека напишем продукциите (с превеждащи символи) и свързваме семантични правила с тях (тук $\$ е превеждащ символ. Ако един и същ нетерминал се среща няколко пъти в продукцията, ще добавим индекси към нея, броейки от началото на продукцията.):

Продуктови семантични правила

$D \в TL$	$L.inh = T.type$
$T \to int$	$T.type = цяло число$
$T \to real$	$T.type = real$
$L_0 \до L_1,id\ \$	$L_1.inh = L0.inh \\ ENTRY.key= >
$L \към id\ \$	$ENTRY ключ= >

Пример за работа с атрибути при низходящ анализ [редактиране]

Помислете за работа с атрибути на примера на LL(1) граматиката на аритметични изрази, която вече е анализирана по-рано и разширете кода на анализатора за нея:

$ E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to * FT' \mid \varepsilon \\ F \to n \mid (E) $

В тази реализация рекурсивните функции от нетерминали получават като вход (ако е необходимо) наследените атрибути на възела и връщат възлите на дървото за анализ, чиито атрибути съдържат резултата от съответния подизраз. Въпреки това, този код може лесно да бъде модифициран, така че да оценява само стойността на израза и да не изгражда дървото за анализ. Както виждаме, $val$ е синтезиран атрибут, $acc$ е наследен атрибут, $ADD$ е знак за превод. Линиите, които отговарят за работата с атрибути, са маркирани в синьо.

Тук [math]\mathtt[/math] е структура със следната форма:

Функциите за $T$ и $T'$ се конструират по подобен начин.

Атрибути в ANTLR[редактиране]

Публичният ANTLR парсер генератор [1] поддържа синтактично контролирана дефиниция.

Помислете за ANTLR пример за същата граматика на аритметични изрази с операторите [math]+,\ *[/math] , скоби и изхода на резултата от израза.

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

Началният нетерминал отпечатва резултата:

Продукцията за нетерминалния израз дефинира върната стойност ( [intval]). Този атрибут е достъпен във формата $expr.value. Семантичните правила са записани във къдрави скоби.

Анализирани нетерминаливръща резултата, оценен в поддървото (връща [int val]) като техен синтезиран атрибут, чийто процес на оценяване е описан във фигурни скоби < $val = $exprp.val; >.

Наследените атрибути се предават на нетерминала като параметър (exprP[$term.val]).

Технически подробности за ANTLR, правила за лексикалния анализатор:

">

---