Combining Parsing and Evaluation for Attributed Grammars

Abstract

Attributed grammars, developed by Knuth, permit the formal specification of context-sensitive syntax and semantics within the framework of context-free grammars. This thesis explores techniques to combine parsing with attributed grammar evaluation. The methods of Lewis, Rosenkrantz, and Stearns for evaluating the attributes of symbols during a parse of a string are expanded to include both S- and L-attributed grammars as special cases. An extension that involves the temporary retention of subtrees and delays their evaluation during a parse allows evaluation of all non-circular attributed grammars with LR(k) context-free grammars. An attributed pushdown processor using left-corner parsing techniques is described to perform efficient translations specified by attributed grammars. It serves as a model for single-pass compilation that formalizes and generalizes the use of a semantic stack to encompass forward references. The applicability of the processor in a practical translator writing system is considered, and the salient table construction and run-time properties are established.