LR-attributed grammar
Encyclopedia
LR-attributed grammars are a special type of attribute grammar
s. They allow the attributes to be evaluated on LR parsing
. As a result, attribute evaluation in LR-attributed grammars can be incorporated conveniently in bottom-up parsing. zyacc is based on LR-attributed grammars. They are a subset of the L-attributed grammar
s, where the attributes can be evaluated in one left-to-right traversal of the abstract syntax tree. They are a superset of the S-attributed grammar
s, which allow only synthesized attributes. In yacc, a common hack is to use global variables to simulate some kind of inherited attributes and thus LR-attribution.
Attribute grammar
An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler....
s. They allow the attributes to be evaluated on LR parsing
LR parser
In computer science, an LR parser is a parser that reads input from Left to right and produces a Rightmost derivation. The term LR parser is also used; where the k refers to the number of unconsumed "look ahead" input symbols that are used in making parsing decisions...
. As a result, attribute evaluation in LR-attributed grammars can be incorporated conveniently in bottom-up parsing. zyacc is based on LR-attributed grammars. They are a subset of the L-attributed grammar
L-attributed grammar
L-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated in one 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.Many programming...
s, where the attributes can be evaluated in one left-to-right traversal of the abstract syntax tree. They are a superset of the S-attributed grammar
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 tree during the semantic analysis of the parsing...
s, which allow only synthesized attributes. In yacc, a common hack is to use global variables to simulate some kind of inherited attributes and thus LR-attribution.
External links
- http://www.cs.binghamton.edu/~zdu/zyacc/doc/zyacc_4.html
- Reinhard WilhelmReinhard Wilhelm- Life and work :Wilhelm was born in Deutmecke, Westphalia. He studied math, physics and mathematical logic at University of Münster and computer science at Technical University Munich and Stanford University. He finished his PhD at TU Munich in 1977...
: LL- and LR-Attributed Grammars. Programmiersprachen und Programmentwicklung, 7. Fachtagung, veranstaltet vom Fachausschuß 2 der GI (1982), 151–164, Informatik-Fachberichte volume 53. - J. van Katwijk: A preprocessor for YACC or A poor man's approach to parsing attributed grammars. Sigplan Notices 18:10 (1983), 12–15.