Attribute grammar Contents History Example Synthesized attributes Inherited attributes Special types of attribute grammars See also References External links Navigation menuThe genesis of attribute grammarsvol. 461Why Attribute Grammars MatterUtrecht University Attribute GrammarAttribute grammarSemantics of context-free languagesAttribute grammar paradigms—a high-level methodology in language implementation

Formal languagesCompiler constructionParsing


attributesformal grammarabstract syntax treeparsercompilerintermediate languageDonald KnuthPeter WegnerIMPcontext-free grammarS-attributed grammar




An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes with values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler.


The attributes are divided into two groups: synthesized attributes and inherited attributes. The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes.


In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down and across it. For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax definition.


Attribute grammars can also be used to translate the syntax tree directly into code for some specific machine, or into some intermediate language.


One strength of attribute grammars is that they can transport information from anywhere in the abstract syntax tree to anywhere else, in a controlled and formal way.[citation needed]




Contents





  • 1 History


  • 2 Example


  • 3 Synthesized attributes


  • 4 Inherited attributes


  • 5 Special types of attribute grammars


  • 6 See also


  • 7 References


  • 8 External links




History


Attribute grammars were invented by Donald Knuth and Peter Wegner.[1] While Donald Knuth is credited for the overall concept, Peter Wegner invented inherited attributes during a conversation with Knuth. Some embryonic ideas trace back[1] to the work of Edgar T. "Ned" Irons[2], the author of IMP.



Example


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


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

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.


 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) ]


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. To formally define a synthesized attribute, let G=⟨Vn,Vt,P,S⟩displaystyle G=langle V_n,V_t,P,Srangle be a formal grammar, where



  • Vndisplaystyle V_n is the set of non terminal symbols


  • Vtdisplaystyle V_t is the set of terminal symbols


  • Pdisplaystyle P is the set of productions


  • Sdisplaystyle S is the distinguished, or start, symbol

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



  • A→α∈Pdisplaystyle Arightarrow alpha in P (i.e. A→αdisplaystyle Arightarrow alpha is one of the rules in the grammar)


  • α=α1…αn,∀i,1≤i≤n:αi∈(Vn∪Vt)displaystyle alpha =alpha _1ldots alpha _n,forall i,1leq ileq n:alpha _iin (V_ncup V_t) (i.e. every symbol in the body of the rule is either nonterminal or terminal)


  • A.a=f(αj1.a1,…,αjm.am)displaystyle A.a=f(alpha _j_1.a_1,ldots ,alpha _j_m.a_m), where αj1,…,αjm⊆α1,…,αndisplaystyle alpha _j_1,ldots ,alpha _j_msubseteq alpha _1,ldots ,alpha _n (i.e. the value of the attribute is a function fdisplaystyle f 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




  1. ^ ab D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), LNCS, vol. 461, 1–12.


  2. ^ http://zzcad.com/ned.htm




External links



  • 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 catamorphisms compositionally. It refers to the Utrecht University Attribute Grammar system as the implementation used in the examples.)


  • Attribute grammar in relation to Haskell and functional programming.


  • Semantics of context-free languages, by Don Knuth, is the original paper introducing attributed grammars

  • Jukka Paakki: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196–255.


Compiler construction, Formal languages, ParsingUncategorized

Popular posts from this blog

Frič See also Navigation menuinternal link

Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox