Misplaced Pages

L-attributed grammar

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "L-attributed grammar" – news · newspapers · books · scholar · JSTOR (July 2020) (Learn how and when to remove this message)

L-attributed grammars are a special type of attribute grammars. 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 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

  1. the attributes of the symbols X 1 , X 2 , … , X j − 1 {\displaystyle X_{1},X_{2},\dots ,X_{j-1}}
  2. the inherited attributes of A {\displaystyle 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 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 X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} .

References

  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.
Categories: