# How to handle L-attributed SDDs with LR parsers

I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points:

1. How to handle L-attributed SDDs in an LR grammar when using a tool such as Bison? I believe, the book says that inherited attributes could be used with an LR parser (via Marker symbols?) provided the grammar is LL, or is (partly?) transformed into LL. Is this true? What if the grammar is LR and/or converting it to LL is not easy -- how do you then use inherited attributes?

2. If LR grammars are a proper superset of LL grammars and therefore more powerful, then how come LR grammars/parsers won't out-of-the-box allow L-attributed SDDs which, being a superset of S-attributed SDDs, are more powerful?

3. Avoiding the SDD style - Parsing style mismatch: Is it true that no matter the grammar (LL, LR, ...) or the parsing tool (Antlr, bison, yacc...), I can always first build the AST and then traverse it post-/pre-order any number of times to get whatever SDTs I want? (Ignore the time inefficiency here.)

Is there a text or online resource that covers topics 1 and 2 better or in more detail?

Let's start with #3: Can you always walk the AST in any way you like after it is built? Yes, you can, and the Dragon book has an extensive discussion about how to do that for a given set of attributes; in particular, how to avoid (or detect) infinite regression.

Moreover, there is really no inefficiency in doing it this way. Or, to put it another way, trying to compute attributes on the fly during the parse does not speed things up much if at all, and can even slow things down. Even if it were slightly inefficient, it generally makes the parser much more complicated than it should be, partly because of the artificial hoops which need to be jumped through to perform the analysis online, and partly because it tends to interlace code which doesn't need to be codependent. Separation of concerns is almost always a good programming model.

With that out of the way, and briefly:

1. What the Dragon book says (iirc, because I still don't have either of my copies at my fingertips) is that adding markers can destroy the LR property of a grammar. This doesn't happen if the grammar happens to be LL. It's not actually necessary for the whole grammar to be LL, but it's a bit tricky to provide a formal description of what it means for a part of a grammar to be LL, although it's possible. Before LALR parser generators were available, there was quite a lot of research into left corner parsing (LCP), which you could look at if you're interested in the concepts. (I don't have references handy but the phrase should still be usable as a search term.)

If you want to introduce a marker into an LR grammar, you need to ensure that the reduction action for that marker does not conflict with any shift action. For that to be the case, each itemset which contains an item whose • is just before the marker must be free of items which would allow a shift of a symbol which could follow the marker. This is very similar to the LL(1) criterion, because it is effectively saying that the parser needs to be able to predict a single unique production at that point in the parse, something which is not normally required in an LR parser. (Strictly speaking, the parser only needs to be able to predict a single unique production for some lookahead symbols -- as I said, those which might follow the marker -- but that fact doesn't usually help much.)

A common way of creating this sort of conflict is when you have two similar productions with different markers before the same symbol. See the bison manual for some specific examples. (Bison automatically inserts markers for you when you put an action in the middle of the rule, which is why that section is called what it is called.)

2. LR grammars can recognise a strictly larger set of languages than LL grammars. But here, we're not talking about just recognising whether a sentence is in a language or not. The goal of parsing (outside of some formal language theory discussions) is almost always to recursively break the input into parts (which is the root of the verb "to parse") and understand the relationships between those parts.

All the same, LR parsers are, by and large, more capable at parsing as well. For example, the common language of arithmetic expressions can easily be recognised by an LL parser, and most textbooks insist that students work through the chore of destroying refactoring a simple operator grammar in order to make it possible to parse with a top-down parser. But the resulting LL grammar does not produce the same AST; it has completely lost any information about operator associativity. In order to use the parse, it is necessary to rewrite the AST to recover that information. The fact that an LL grammar cannot produce a parse tree for left-associative operators seems to me like it should count as a weakness.

In any event, if there is an LL grammar which correctly parses a language then you can indeed insert whatever attributes you like wherever you want to insert them. But that grammar will also be an LR grammar, and you will be able to insert markers freely into that grammar without losing the LR property. Unfortunately, it is possible that adding markers to the $$LL(1)$$ grammar will produce a grammar which is not $$LALR(1)$$ (since not all $$LR(1)$$ grammars are $$LALR(1)$$). But as far as I know this doesn't show up often in practical grammars.

If you want an academic reference, you can look at Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars", Journal of the ACM, 29 (4 (Oct)): 1007–1022. (doi:10.1145/322344.322350. I got that from a reference in the Wikipedia entry on LL grammars; the reference link is not pay-walled, at least as of today.)

• +1, first off. I'm studying the Dragon book and will also be parallelly learning Antlr4 (ALL(*)), Bison (G/LR), and maybe even Yacc (LALR). I love the elegance of left-recursive expression-SDTs and also the ability to build Concrete Syntax Trees (CSTs, not ASTs!) with an LR parser using postfix SDTs (ie, when actions are all at the very end of their rules). However, even when trying to build an AST using Bison, what if I need inherited attributes from unprocessed rules 'up above' in the tree? It seems, I can only build a CST first, and then create the needed AST from this CST. Am I right? – Harry Feb 19 at 6:05
• I'll be trying to absorb your response fully over the next few days/weeks, so apologies if the clarification I just now sought is already implied in your detailed response. I'll check out LCP much later... only once I get a good grip on the Parsing and SDT chapters of the Dragon Book and also get a good hands-on on Antlr4 and Bison. Thanks, for the LCP pointer. – Harry Feb 19 at 6:10
• @Harry: I guess it depends on what you mean by "construct an AST". Generally speaking, the AST is built during the parse, but most of the attributes are not yet filled in. As you say, you can use the full syntax tree, but honestly for me there's not much point unless you're building a pretty-printer or colorizer. For most parsing purposes, you can dispense with unit productions and syntactic noise without losing any functionality, and the resulting AST is a somewhat easier to analyse... – rici Feb 19 at 6:35
• Once the parse is finished, you can start walking the tree to fill in the attributes. That doesn't usually change the shape of the tree, although at a certain point you will want to start rearranging things, in order to implement constant folding, common subexpression elimination, etc., etc. Whether that's done by mutating the AST or by building new datastructures is another design decision. You'll also want to build control flow graphs, which are not really ASTs at all, and at some point you'll start to emit actual compiled code, which is yet another data structure... – rici Feb 19 at 6:38
• Anyway, hope you have fun with the project. – rici Feb 19 at 6:38