Atributová gramatika

Atributové gramatiky je formalismus v matematické informatice poskytující rozšíření formálních gramatik o přenos informací v rámci přepisovacího pravidla, což umožňuje přenos (např. sémantických) informací z libovolného místa v abstraktním syntaktickém stromě kamkoli jinam, řízeným a formálním způsobem. Ke každému terminálnímu nebo neterminálnímu symbolu gramatiky je možné připojit jeden nebo více atributů, a ke každému přepisovacímu pravidlu jsou přiřazeny tak zvané sémantické funkce, pomocí kterých se při použití tohoto pravidla počítají z některých atributů symbolů použitých v pravidle hodnoty dalších atributů symbolů použitých v pravidle.

Atributové gramatiky umožňují při konstrukci překladačů rozšířit syntaktický analyzátor o možnost přenášet různé doplňující informace během analýzy vstupního řetězce. Atributy mohou být použity pro přiřazení sémantických hodnot syntaktickým konstrukcím (například rozlišit, zda operátor + znamená sčítání celých čísel, sčítání reálných čísel, zřetězení nebo sjednocení množin nebo má jiný význam). +more Atributy také umožňují validovat podmínky, které nejsou přímo vyjádřeny pomocí syntaxe, ale jako doplňující sémantická pravidla přiřazená k jednotlivým pravidlům gramatiky (například kontrolovat typová omezení nebo kontrolovat, zda jsou použité identifikátory deklarovány). Atributové gramatiky lze použít pro převod syntaktického stromu přímo na kód pro určitý stroj nebo do nějaké formy mezijazyka.

Podle toho, zda sémantická funkce slouží pro vyčíslení hodnoty atributu symbolu z levé nebo z pravé strany přepisovacího pravidla, se atributy dělí na syntetizované (funkce vyčísluje atributy symbolu na levé straně pravidla) a zděděné (příp. dědičné). +more Zatímco syntetizované atributy umožňují přenos sémantické informace derivačním stromem vzhůru, zděděné atributy umožňují předávání hodnot z rodičovských uzlů dolů a napříč syntaktickým stromem.

Historie

Za autora atributových gramatik je považován Donald Ervin Knuth, jehož první článek o tomto tématu vyšel v roce 1968. Knuth zmiňuje, že zárodky konceptu atributových gramatik lze dohledat již u Edgara T. +more „Neda“ Ironse, autora programovacího jazyka IMP, a uvádí, že koncept zděděných atributů navrhl během konverzace s Knuthem Peter Wegner.

Příklad

Následující příklad je jednoduchá bezkontextová gramatika, která popisuje jazyk výrazů obsahujících násobení a sčítání celých čísel.

Expr → Expr + Term Expr → Term Term → Term * Factor Term → Factor Factor → "(" Expr ")" Factor → integer

Pro výpočet hodnot výrazů zapsaných podle této gramatiky lze použít následující atributovou gramatiku; tato gramatika používá pouze syntetizované atributy, takže jde o S-atributovanou gramatiku: Expr1 → Expr2 + Term [ Expr1. value = Expr2. +morevalue + Term. value ] Expr → Term [ Expr. value = Term. value ] Term1 → Term2 * Factor [ Term1. value = Term2. value * Factor. value ] Term → Factor [ Term. value = Factor. value ] Factor → "(" Expr ")" [ Factor. value = Expr. value ] Factor → integer [ Factor. value = strToInt(integer. str) ].

Syntetizované atributy

Hodnoty syntetizovaných atributů se počítají pouze z hodnot atributů potomků daného uzlu v derivačním stromě. Protože se nejdříve musí vypočítat hodnoty potomků, jde o šíření hodnot zdola nahoru. +more Pro formální definici syntetizovaného atributu, nechť G= \langle V_n,V_t,P,S \rangle je formální gramatika, kde.

* V_n je množina neterminálních symbolů * V_t je množina terminálních symbolů * P je množina přepisovacích pravidel * S je počáteční symbol

Je-li dán řetězec neterminálních symbolů A, pak jeho atribut a, A.a je syntetizovaným atributem, pokud jsou splněny následující tři podmínky:

* A \rightarrow \alpha \in P (tj. A \rightarrow \alpha je jedním z pravidel v gramatice) * \alpha = \alpha_1 \ldots \alpha_n, \forall i, 1 \leq i \leq n: \alpha_i \in (V_n \cup V_t) (tj. +more každý symbol v těle pravidla je buď neterminál anebo terminál) * A. a = f(\alpha_{j_1}. a_1, \ldots ,\alpha_{j_m}. a_m), kde \{\alpha_{j_1}, \ldots ,\alpha_{j_m}\} \subseteq \{\alpha_1, \ldots ,\alpha_n\} (tj. hodnota atributu závisí pouze na hodnotách atributů symbolů na pravé straně pravidla).

Zděděné atributy

Zděděný atribut uzlu v derivačním stromě je definován pomocí hodnot atributů rodičovských nebo sourozeneckých uzlů. Zděděné atributy jsou vhodné pro vyjádření závislosti konstruktu programovacího jazyka na kontextu, v němž se tento konstrukt objevuje. +more Zděděný atribut může například posloužit pro rozlišení, zda se identifikátor objevil na levé nebo pravé straně přiřazení, aby bylo možné určit, zda se má v generovaném kódu použít adresa nebo hodnota proměnné. Na rozdíl od syntetizovaných atributů se hodnoty zděděných atributů počítají z atributů rodičů nebo sourozenců. Například v přepisovacím pravidle.

: S → ABC

se hodnoty zděděných atributů symbolu A počítají z atributů symbolů S, B a C; hodnoty zděděných atributů symbolu B z atributů symbolů S, A a C; a hodnoty zděděných atributů symbolu C z S, A a B.

Speciální typy atributových gramatik

L-atributované gramatiky jsou atributové gramatiky v nichž lze zděděné atributy vyčíslit v jednom průchodu abstraktním syntaktickým stromem zleva doprava * LR-atributované gramatiky jsou L-atributované gramatiky, v niž lze zděděné atributy vyčíslit také při syntaktické analýze zdola nahoru * ECLR-atributované gramatiky jsou podmnožinou LR-atributovaných gramatik, u nichž lze kde lze optimalizovat vyhodnocování zděděných atributů pomocí tříd ekvivalence * S-atributované gramatiky jsou jednoduchým typem atributových gramatik, které používají pouze syntetizované atributy

Další informace

Článek popisuje, jak formalismus atributových gramatik vnáší prvky aspektově orientovaného programování do funkcionálního programování tím, že pomáhá programovat katamorfismy kompozicionálně. V příkladech používá Attribute Grammar System vytvořený na Univerzitě v Utrechtu. +more Článek na webu věnovanému jazyku Haskel popisuje atributové gramatiky ve vztahu k Haskellu a funkcionálnímu programování.

Odkazy

Poznámky

Reference

Související články

Afixová gramatika * Van Wijngaardenova gramatika * Syntaxí řízený překlad

Externí odkazy

Kategorie:Formální jazyky Kategorie:Konstrukce překladačů Kategorie:Syntaktická analýza