L-attributed Grammar
   HOME

TheInfoList



Click Here for Items Related To - L-attributed Grammar
OR:
L-attributed Grammar on:   [Wikipedia]   [Google]   [Amazon]

L-attributed grammars are a special type of
attribute grammar An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are resu ...
s. They allow the attributes to be evaluated in one depth-first left-to-right traversal of the
abstract syntax tree In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring ...
. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in
top-down parsing Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-d ...
. A syntax-directed definition is L-attributed if each ''inherited'' attribute of X_j on the right side of A \rightarrow X_1, X_2, \dots, X_n depends only on # the attributes of the symbols X_1, X_2, \dots, X_ # the inherited attributes of A (but not its synthesized attributes) 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
compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
s, the narrow compilers, are based on some form of L-attributed grammar. These are a strict superset of
S-attributed grammar S-attributed grammars are a class of attribute grammars characterized by having no inherited attributes, but only synthesized attributes. Inherited attributes, which must be passed down from parent nodes to children nodes of the abstract syntax ...
s. Used for code synthesis. Either "inherited attributes" or "synthesized attributes" associated with the occurrence of symbol X_1,X_2, \dots, X_n.


References

{{DEFAULTSORT:L-Attributed Grammar Formal languages Compiler construction