L-attributed grammar and bottom-up parsing

Question

I am trying to understand what is the relationship between L-attributed grammars and computing attributes during bottom-up parsing. Is it always possible to compute all attributes during syntax tree creation for every context-free grammar or just for some selected grammars like LR(k)? Let's assume that some transformations like adding new nonterminals and epsilon productions are allowed. I have been seeking some information about that but I cannot find.

Answer 1

If you can construct the parse tree bottom-up left-to-right, then you can compute L-attributes. That's a tautology because L-attributes are those attributes which you can compute bottom-up left-to-right. How you manage to do the parse is irrelevant.

Generalised LR parsing algorithms allow you to parse bottom-up left-to-right, with the proviso that there may be more than one possible parse available at a given moment. (In fact, if the grammar is not required to be unambiguous, more than one parse of the entire input could be possible.)

In practice, computing attributes for parse nodes before you know that they are part of the final parse can be extremely inefficient. Also in practice, one would insert here a warning about actions with side effects, but computing an attribute of a parse node is not a side-effect in itself, and if it has some other effect on the universe then we are no longer in the territory of the mathematical theory.

Furthermore, if the grammar is unambiguous, the number of possible parses could be exponential in the length of the input. Most generalised LR algorithms construct parse graphs rather than parse trees, which can be done using only polynomial space to represent the exponential number of possible trees. But that requires sharing nodes between different parses which might not be possible in the face of attribute computation, since the nodes to be shared might turn out to have different attributes.

Here, I think, it's worthwhile to revisit the question of side effects mentioned above, because it might not really be the case that computing the value of an attribute for a node is not a side effect. If you are building a persistent structure (a parse tree) which is observable during its construction, then assigning an attribute to a component of that structure is certainly a side effect. On the other hand, if the structure is not externally visible during its construction, then it doesn't matter when you assign attributes to components. In that case, it might be better to think of L-attributes as those attributes which can be computed in a single depth-first left-to-right traverse of the (fully constructed) parse tree.