Jump to content

L-attributed grammar

From Wikipedia, the free encyclopedia

L-attributed grammars are a special type of attribute grammars.[1] They allow the attributes to be evaluated in one depth-first left-to-right traversal of the abstract syntax tree. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in top-down parsing.

A syntax-directed definition is L-attributed if each inherited attribute of on the right side of depends only on

  1. the attributes of the symbols
  2. the inherited attributes of (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 compilers, the narrow compilers, are based on some form of L-attributed grammar. These are a strict superset of S-attributed grammars. Used for code synthesis.

Either "inherited attributes" or "synthesized attributes" associated with the occurrence of symbol .

References

[edit]
  1. ^ Knuth, Donald E. (June 1968). "Semantics of context-free languages". Mathematical Systems Theory. 2 (2): 127–145. CiteSeerX 10.1.1.455.1434. doi:10.1007/BF01692511. ISSN 0025-5661. S2CID 5182310. QID 56672530.