Attribute Grammar §

Formal definition §

Context Free Grammar: §

Formal definition §

• V: vocabulary:
  • N: set of non-terminal symbols
  • T: set of terminal symbols
• P: set of grammar production rules
  • $p\in P:X_0\to X_1...$
• S: the starting symbol

Link to original

Extended by: §

• $A$: set of attributes
  • $INH$: set of inherited attributes
    • $IN{H}_X$: set of inherited attributes for $X\in V$
  • $SYN$: set of synthesized attributes
    • $SY{N}_X$: set of synthesized attributes for $X\in V$
• $f$: semantic rules bound to $a\in A$ and $p\in P$
  • has to be defined $\forall a_i\in IN{H}_{x1}(1\le i\le np)$
    • → for every inherited attribute
  • and $\forall a_0\in SY{N}_{x0}$
    • → for every synthesized attribute
  • parameters: $f(p,i,a)$
    • $f$ evaluates the attribute $a$ of the production rule $p$ at the position $i$

Norms §

• normal form: an attribute only appears on one side
• well-formed: an attribute grammar AG contains no cycle for every possible derivation tree

Example definition §

1. Nonterminals & Terminals
   • $V=(S\cup N\cup T)$
2. Attributes
   • $A$
3. Rules
   • $P$, $f$

Example min amount of f §

• 2p: A → XA
• AG G:
  • $IN{H}_A$ = {i1}
  • $IN{H}_X$ = {i2}
  • $SY{N}_A$ = {s1}
  • $SY{N}_X$ = {s2}
• $f(2p,0,s1)$

LL-attributed grammar §

• S-attributed grammar = L attributed grammar with only synthesized attributes