ECLR-attributed grammars: a practical class of LR-attributed grammars (Q1822525)

A class of attribute grammars called LR-attributed grammars (LR-AGs) has been proposed by Jones and Madsen as a (virtually) maximum class for which attributes can be evaluated in a single pass during LR parsing, without constructing a syntax tree. However, the original definition of LR-AGs has the problem that evaluation of attributes is inefficient in space and time because is was assumed that all inherited attributes related to an LR state are evaluated and stored separately. In this paper, we present a practical class of LR-AGs for which evaluation can be made efficiently. The idea is to partition the set of all inherited attributes into certain equivalence classes, and hence the resulting class is named equivalence class LR-attributed grammar (ECLR-AG). An equivalence class is basically a set of inherited attributes which have the same value for all LR states. Since all attributes belonging to an equivalence class have the same values at each state, their values can be obtained by a single evaluation and can be stored in a single location at each evaluation point which makes attribute evaluation efficient.