L-attributed grammar

L-attributed grammars are a special type of <a href="/facts/Attribute_grammar/N4yuxaoR">attribute grammars</a>. They allow the attributes to be evaluated in one depth-first left-to-right traversal of the <a href="/facts/Abstract_syntax_tree/73AUK1jI">abstract syntax tree</a>. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in <a href="/facts/Top-down_parsing/VVqphs5y">top-down parsing</a>. 
A syntax-directed definition is L-attributed if each inherited attribute of 
 
 
 
 
 X
 
 j
 
 
 
 
 {\displaystyle X_{j}}
 
 on the right side of 
 
 
 
 A
 →
 
 X
 
 1
 
 
 ,
 
 X
 
 2
 
 
 ,
 …
 ,
 
 X
 
 n
 
 
 
 
 {\displaystyle A\rightarrow X_{1},X_{2},\dots ,X_{n}}
 
 depends only on 

<ol><li>the attributes of the symbols 
 
 
 
 
 X
 
 1
 
 
 ,
 
 X
 
 2
 
 
 ,
 …
 ,
 
 X
 
 j
 −
 1
 
 
 
 
 {\displaystyle X_{1},X_{2},\dots ,X_{j-1}}
 
</li>
<li>the inherited attributes of 
 
 
 
 A
 
 
 {\displaystyle A}
 
 (but not its synthesized attributes)</li></ol>
Every S-attributed syntax-directed definition is also L-attributed.
Implementing L-attributed definitions in Bottom-Up parsers requires rewriting L-attributed definitions into translation schemes.
Many programming languages are L-attributed. Special types of <a href="/facts/Compiler/WNfCDFJe">compilers</a>, the narrow compilers, are based on some form of L-attributed grammar. These are a strict superset of <a href="/facts/S-attributed_grammar/9HUfcgDW">S-attributed grammars</a>. Used for code synthesis.
Either "inherited attributes" or "synthesized attributes" associated with the occurrence of symbol 
 
 
 
 
 X
 
 1
 
 
 ,
 
 X
 
 2
 
 
 ,
 …
 ,
 
 X
 
 n
 
 
 
 
 {\displaystyle X_{1},X_{2},\dots ,X_{n}}
 
.

L-attributed grammar open-in-new

L-attributed grammar