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.^[1] 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). 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é). 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.^[2] Knuth zmiňuje, že zárodky konceptu atributových gramatik lze dohledat již u Edgara T. „Neda“ Ironse,^[3] autora programovacího jazyka IMP, a uvádí, že koncept zděděných atributů navrhl během konverzace s Knuthem Peter Wegner.^[4]

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.value + 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. Pro formální definici syntetizovaného atributu, nechť ${\displaystyle G=\langle V_{n},V_{t},P,S\rangle }$ je formální gramatika, kde

• ${\displaystyle V_{n}}$ je množina neterminálních symbolů
• ${\displaystyle V_{t}}$ je množina terminálních symbolů
• ${\displaystyle P}$ je množina přepisovacích pravidel
• ${\displaystyle S}$ je počáteční symbol

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

• ${\displaystyle A\rightarrow \alpha \in P}$ (tj. ${\displaystyle A\rightarrow \alpha }$ je jedním z pravidel v gramatice)
• ${\displaystyle \alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})}$ (tj. každý symbol v těle pravidla je buď neterminál anebo terminál)
• ${\displaystyle A.a=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})}$, kde ${\displaystyle \{\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. 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 Why Attribute Grammars Matter 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ě.^[5] V příkladech používá Attribute Grammar System vytvořený na Univerzitě v Utrechtu.^[6] Článek na webu věnovanému jazyku Haskel^[7] popisuje atributové gramatiky ve vztahu k Haskellu a funkcionálnímu programování.

Odkazy

Poznámky

Reference

V tomto článku byl použit překlad textu z článku Attribute grammar na anglické Wikipedii.

Související články

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

Externí odkazy

• IRONS, Edgar T. Dostupné online. 
• KNUTH, Donald, 1968. Semantics of context-free languages. Mathematical Systems Theory. Roč. 2, čís. 2, s. 127–145. Dostupné online. DOI 10.1007/BF01692511. S2CID 5182310. 
• KNUTH, D. E., 1990. The genesis of attribute grammars [online]. 1990. S. 1–12. Dostupné online. DOI 10.1007/3-540-53101-7. 
• Why Attribute Grammars Matter. The Monad Reader. 2005-07-05, čís. 4. Dostupné online. 
• AttributeGrammarSystem [online]. [cit. 2021-07-30]. Dostupné v archivu pořízeném dne 2013-06-05. 
• Attribute grammar [online]. Dostupné online. 
• PAAKKI, Jukka. Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys. Roč. 27, čís. 2 (červen 1995), s. 196–255. Dostupné online.