Atributová gramatika: Porovnání verzí

Smazaný obsah Přidaný obsah
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.

 ExprExpr + Term
 ExprTerm
 TermTerm * Factor
 TermFactor
 Factor → "(" Expr ")"
 Factorinteger

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:

 Expr1Expr2 + Term [ Expr1.value = Expr2.value + Term.value ]
 ExprTerm [ Expr.value = Term.value ]
 Term1Term2 * Factor [ Term1.value = Term2.value * Factor.value ]
 TermFactor [ Term.value = Factor.value ]
 Factor → "(" Expr ")" [ Factor.value =  Expr.value ]
 Factorinteger [ 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