Editing Attribute grammar

{{Short description|Type of formal grammar}}
An '''attribute grammar''' is a formal way to supplement a [[formal grammar]] with semantic information processing. Semantic information is stored in [[Attribute (computing)|attributes]] associated with [[terminal and nonterminal symbols]] of the grammar. The values of attributes are the result of attribute evaluation rules associated with productions of the grammar. Attributes allow the transfer of information from anywhere in the [[abstract syntax tree]] to anywhere else, in a controlled and formal way.{{Sfn|Knuth|1968|p=134}}

Each semantic function deals with attributes of symbols occurring only in one production rule: both semantic function parameters and its result are attributes of symbols from one particular rule. When a semantic function defines the value of an attribute of the symbol on the left hand side of the rule, the attribute is called ''synthesized''; otherwise it is called ''inherited''.{{Sfn|Knuth|1968|p=132}} Thus, synthesized attributes serve to pass semantic information up the parse tree, while inherited attributes allow values to be passed from the parent nodes down and across the syntax tree.

In simple applications, such as evaluation of arithmetic expressions, attribute grammar may be used to describe the entire task to be performed besides parsing in straightforward way; in complicated systems, for instance, when constructing a language translation tool, such as a compiler, it may be used to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax definition. It may be also used by [[parser]]s or [[compiler]]s to translate the syntax tree directly into code for some specific machine, or into some [[intermediate language]].

==History==
Attribute grammars were invented by [[Donald Knuth]] and [[Peter Wegner (computer scientist)|Peter Wegner]].<ref name="genesis">D. E. Knuth: [http://www.cs.miami.edu/home/odelia/teaching/csc419_spring17/syllabus/Knuth_AttributeHistory.pdf The genesis of attribute grammars]. ''Proceedings of the international conference on Attribute grammars and their applications'' (1990), LNCS, [https://doi.org/10.1007%2F3-540-53101-7 vol. 461], 1–12.</ref> While Donald Knuth is credited for the overall concept, Peter Wegner invented inherited attributes during a conversation with Knuth. Some embryonic ideas trace back<ref name="genesis"/> to the work of Edgar T. "Ned" Irons,<ref>{{Cite web|url=http://zzcad.com/ned.htm|title=Main}}</ref> the author of [[IMP (programming language)|IMP]].

==Example==
The following is a simple [[context-free grammar]] which can describe a language made up of multiplication and addition of integers.

  '''Expr''' &rarr; '''Expr''' + '''Term'''
  '''Expr''' &rarr; '''Term'''
  '''Term''' &rarr; '''Term''' * '''Factor'''
  '''Term''' &rarr; '''Factor'''
  '''Factor''' &rarr; "(" '''Expr''' ")"
  '''Factor''' &rarr; ''integer''

The following attribute grammar can be used to calculate the result of an expression written in the grammar. Note that this grammar only uses synthesized values, and is therefore an [[S-attributed grammar]].
  '''Expr<sub>1</sub>''' &rarr; '''Expr<sub>2</sub>''' + '''Term''' [ '''Expr<sub>1</sub>'''.value = '''Expr<sub>2</sub>'''.value + '''Term'''.value ]
  '''Expr''' &rarr; '''Term''' [ '''Expr'''.value = '''Term'''.value ]
  '''Term<sub>1</sub>''' &rarr; '''Term<sub>2</sub>''' * '''Factor''' [ '''Term<sub>1</sub>'''.value = '''Term<sub>2</sub>'''.value * '''Factor'''.value ]
  '''Term''' &rarr; '''Factor''' [ '''Term'''.value = '''Factor'''.value ]
  '''Factor''' &rarr; "(" '''Expr''' ")" [ '''Factor'''.value =  '''Expr'''.value ]
  '''Factor''' &rarr; ''integer'' [ '''Factor'''.value = strToInt(''integer''.str) ]

==Synthesized attributes==
A synthesized attribute is computed from the values of attributes of the children. Since the values of the children must be computed first, this is an example of bottom-up propagation.{{Sfn|Knuth|1968|p=130}} To formally define a synthesized attribute, let <math>G= \langle V_n,V_t,P,S \rangle</math> be a formal grammar, where

* <math>V_n</math> is the set of non terminal symbols
* <math>V_t</math> is the set of terminal symbols
* <math>P</math> is the set of [[Formal grammar#The syntax of grammars|productions]]
* <math>S</math> is the distinguished, or start, symbol

Then, given a string of nonterminal symbols <math>A</math> and an attribute name <math>a</math>, <math>A.a</math> is a synthesized attribute if all three of these conditions are met:

* <math>A \rightarrow \alpha \in P</math> (i.e. <math>A \rightarrow \alpha</math> is one of the rules in the grammar)
*<math>\alpha = \alpha_1 \ldots \alpha_n, \forall i, 1 \leq i \leq n: \alpha_i \in (V_n \cup V_t)</math> (i.e. every symbol in the body of the rule is either nonterminal or terminal)
*<math>A.a = f(\alpha_{j_1}.a_1, \ldots ,\alpha_{j_m}.a_m)</math>, where <math>\{\alpha_{j_1}, \ldots ,\alpha_{j_m}\} \subseteq \{\alpha_1, \ldots ,\alpha_n\}</math> (i.e. the value of the attribute is a function <math>f</math> applied to some values from the symbols in the body of the rule)

==Inherited attributes==
An ''inherited attribute'' at a node in parse tree is defined using the attribute values at the parent or siblings. Inherited attributes are convenient for expressing the dependence of a programming language construct on the context in which it appears. For example, we can use an inherited attribute to keep track of whether an identifier appears on the left or the right side of an assignment in order to decide whether the address or the value of the identifier is needed. In contrast to synthesized attributes, inherited attributes can take values from parent and/or siblings. As in the following production,

: S → ABC

where A can get values from S, B, and C. B can take values from S, A, and C. Likewise, C can take values from S, A, and B.

==Special types of attribute grammars==
* [[L-attributed grammar]]: ''inherited attributes'' can be evaluated in one left-to-right traversal of the abstract syntax tree
* [[LR-attributed grammar]]: an L-attributed grammar whose ''inherited attributes'' can also be evaluated in [[bottom-up parsing]].
* [[ECLR-attributed grammar]]: a subset of LR-attributed grammars where equivalence classes can be used to optimize the evaluation of inherited attributes.
* [[S-attributed grammar]]: a simple type of attribute grammar, using only ''synthesized attributes'', but no ''inherited attributes''

==See also==
* [[Affix grammar]]
* [[Van Wijngaarden grammar]]
* [[Syntax-directed translation]]

==References==
{{Reflist}}
* Original paper introducing attributed grammars: {{Cite journal
 | url = https://www.csee.umbc.edu/courses/331/fall16/01/resources/papers/Knuth67AG.pdf
 | title = Semantics of context-free languages
 | first = Donald E.
 | surname = Knuth
 | year = 1968
 | authorlink = Donald Knuth
 | volume = 2
 | number = 2
 | journal = Mathematical Systems Theory
 | pages = 127–145
 | doi = 10.1007/BF01692511
 | s2cid = 5182310
 | access-date = 2018-03-23
 | archive-date = 2020-05-19
 | archive-url = https://web.archive.org/web/20200519113619/https://www.csee.umbc.edu/courses/331/fall16/01/resources/papers/Knuth67AG.pdf
 | url-status = bot: unknown
 }},

==External links==
* [http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter Why Attribute Grammars Matter], The Monad Reader, Issue 4, July 5, 2005. (This article narrates on how the formalism of attribute grammars brings [[aspect-oriented programming]] to [[functional programming]] by helping writing [[catamorphism]]s [[compositionality|compositional]]ly. It refers to the [http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarSystem Utrecht University Attribute Grammar] {{Webarchive|url=https://web.archive.org/web/20130605181916/http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarSystem |date=2013-06-05 }} system (see also [https://www4.di.uminho.pt/~jas/Research/LRC/lrc.html Lrc: A Purely Functional, Higher-Order Attribute Grammar based System]) as the implementation used in the examples.)
* [https://wiki.haskell.org/Attribute_grammar Attribute grammar] in relation to [[Haskell (programming language)|Haskell]] and [[functional programming]].
* Jukka Paakki: [https://www.csee.umbc.edu/courses/graduate/631/Fall2002/p196-paakki.pdf Attribute grammar paradigms—a high-level methodology in language implementation]. ''ACM Computing Surveys'' '''27''':2 (June 1995), 196–255.
* Ox is an attribute grammar compiling system that augments [[Lex (software)|Lex]] and [[Yacc]] specifications with definitions of synthesized and inherited attributes written in a combination of Ox and [[C (programming language)|C]]/[[C++]] syntax. From these specifications, Ox generates ordinary Lex and Yacc specifications that build and decorate an attributed [[parse tree]]. Ox works with the Lex and Yacc versions distributed in the [[Unix]] and [[Oracle Solaris|Solaris]] operating systems, [[Flex (lexical analyser generator)|Flex]], RE/flex, [[GNU Bison|Bison]], [[Berkeley Yacc|BYacc]], [[Btyacc|BtYacc]] and [https://github.com/dino-lang/dino/tree/master/MSTA MSTA (in the DINO GitHub repository)]. (See the [https://sourceforge.net/projects/ox-attribute-grammar-compiler/ SourceForge repository].)
* [http://melt.cs.umn.edu/silver/ Silver] is an extensible attribute grammar specification language and system from University of Minnesota. (See also the [https://github.com/melt-umn/silver GitHub repository].)

{{Authority control}}

[[Category:Formal languages]]
[[Category:Compiler construction]]
[[Category:Parsing]]