Atributová gramatika: Porovnání verzí
Vytvoření článku překladem zoufalého článku na anglické Wikipedii značka: možný podpis v článku |
(Žádný rozdíl)
|
Verze z 30. 7. 2021, 11:57
Atributová gramatika je v matematické informatice při konstrukci překladačů formální způsob, jak doplnit syntaktický analyzátor o možnost přenášet dodatečné informace při analýze vstupního řetězce. K symbolům formální gramatiky popisující analyzovaný jazyk jsou doplněny atributy s hodnotami. Atributy se vyhodnocují v uzlech syntaktického stromu při zpracování vstupní věty syntaktickým analyzátorem nebo překladačem.
Atributy se dělí na dvě skupiny: syntetizované a zděděné (nebo dědičné). Zděděné atributy se předávají z rodičovských uzlů dolů. Hodnoty syntetizovaných atributů jsou výsledkem aplikace pravidel pro vyhodnocování atributů, která mohou využívat i hodnoty zděděných atributů.
V některých přístupech se syntetizované atributy používají pro přenos sémantické informace derivačním stromem vzhůru, zatímco zděděné atributy pro přenos informací ostatními směry. Při konstrukci překladače mohou být použity pro přiřazení sémantických hodnot syntaktickým konstrukcím. 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.
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.
Hlavní význam atributových gramatik tkví v tom, že mohou přenášet informace z libovolného místa v abstraktním syntaktickém stromě kamkoli jinam, řízeným a formálním způsobem.[zdroj?]
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 1967.[1] Knuth zmiňuje, že zárodky konceptu atributových gramatik lze dohledat již u Edgare T. „Neda“ Ironse,[2] autora programovacího jazyka IMP, a uvádí, že koncept zděděných atributů navrhl během konverzace s Knuthem Peter Wegner.[3]
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ť je formální gramatika, kde
- je množina neterminálních symbolů
- je množina terminálních symbolů
- je množina přepisovacích pravidel
- je počáteční symbol
Je-li dán řetězec neterminálních symbolů pak jeho atribut , je syntetizovaným atributem, pokud jsou splněny následující tři podmínky:
- (tj. je jedním z pravidel v gramatice)
- (tj. každý symbol v těleso/tělo pravidla je buď neterminál anebo terminál)
- , kde (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áší Aspektově orientované programování do funkcionálního programování tím, že pomáhá programovat katamorfismy kompozicionálně.[4] V příkladech používá Attribute Grammar System vytvořený na Univerzitě v Utrechtu.[5] Článek na webu věnovanému jazyku Haskel[6] 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
Externí odkazy
- KNUTH, Donald, 1967. Semantics of context-free languages [online]. 1967. Dostupné online.
- KNUTH, D. E. The genesis of attribute grammars [online]. 1990. S. 1–12. Dostupné online. DOI https://doi.org/10.1007%2F3-540-53101-7.
- Why Attribute Grammars Matter. The Monad Reader. 2005-07-05, čís. 4. Dostupné online.
- AttributeGrammarSystem [online]. Dostupné online.
- 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.