41–48 of 48 posts
Sorry, title took me down a nostalgic trip.
What is a good book just for recursive descend parsing? I dabbed into some compiler books but found BNF difficult. Just some clarification, it is not difficult to understand but difficult to build from scratch. I'm thinking maybe a book that asks me to build up BNF expressions for a series of grammars of gradually increasing complexity would be nice.
This [1] is a great tutorial to start with. Personally, I followed up with a standards compliant JSON parser of my own, in Python [2], and later ported it into a larger golang codebase. Practically building up multiple JSON parsers taught me to build my own DSL, using recursive descent parsing. My path admittedly is quite non-standard and idiosyncratic, but was way more fun than going through a textbook :)
[1]: https://www.booleanworld.com/building-recursive-descent-pars...
Earlier quoted context omitted.
3AC/TAC is something fundamentally different than SSA. Sure, both somehow superficially constrain how you write variable assignment statements - if your intermediate representation contains such things and is a list of instructions. 3AC means that your "instructions" have In fact SSA makes no constraints on the number of operands in an instruction/operation what so ever.
Three address code: ``` p = a + b q = p-c p = q * d ``` Ssa: ``` p1 = a+ b q1= p1 - c p2 = q1 * d ``` Given the above examples how is it not straightforward to use ssa instead of three address code using what the dragon book teaches? What is wrong with the above examples? In fact section 6.2.4 in the dragon book it says: “Two distinctive aspects distinguish SSA from three-address code. The first is that all assignmen…
On the other hand, if you write your analyses and transformations with SSA form as a precondition, you can reduce complexity because SSA form is referentially transparent, giving you a lot of things like use-def chains, dead code analysis, etc for more or less free.
This is what people mean when they say that SSA is essential for modern compiler construction. That quote from the book is reductionist to the maximum possible extent and put's it in the direct comparison with 3AC, to which it only has the relation that both are transformations of IR instructions the result of both have nothing in common.
The example is misleading because it displays the SSA IR also in 3AC - which is unnecessary - and it completely omits PHIs without which SSA properties simply do not hold and for which no 3AC correlation exists at all - they are not representable. In fact, control flow can easily be built such that a PHI has any amount of operands - e.g. a switch which might need significant additional code transformation to be representable as 3AC.
Earlier quoted context omitted.
Three address code: ``` p = a + b q = p-c p = q * d ``` Ssa: ``` p1 = a+ b q1= p1 - c p2 = q1 * d ``` Given the above examples how is it not straightforward to use ssa instead of three address code using what the dragon book teaches? What is wrong with the above examples? In fact section 6.2.4 in the dragon book it says: “Two distinctive aspects distinguish SSA from three-address code. The first is that all assignmen…
That's exactly what I mean with superficially similar. Sure, you can transform a non-3AC SSA IR into three address code or transform a 3AC IR into SSA form - as you have done in your example. However, you will need an SSA transformation/construction algorithm to do the latter, which is not that simple or straightforward, especially if you want to be somewhat optimal with placing the PHIs. You can also try to apply yo…
Perhaps you work on llvm or something professionally?
But yeah if you can please provide support for your view. Thanks
Besides devoting too many pages to parsing, I think compiler practitioners have low opinion of the book because it isn't useful for them. For example, the second edition claims to be updated to modern optimization techniques, and in a sense that's true, but it is useless because the book isn't using SSA. For practitioners, SSA is not optional these days, and everything about optimization in the book needs to be updat…
I make a living as a high-performance JIT compiler writer, and the dragon book is a waste of time in my opinion. There are much better books out there. If you are a beginner, start by learning Recursive Descend parsing. And then learn LLVM.
List please?
Earlier quoted context omitted.
That's exactly what I mean with superficially similar. Sure, you can transform a non-3AC SSA IR into three address code or transform a 3AC IR into SSA form - as you have done in your example. However, you will need an SSA transformation/construction algorithm to do the latter, which is not that simple or straightforward, especially if you want to be somewhat optimal with placing the PHIs. You can also try to apply yo…
My apologies for saying the following but can you share some books or papers that support your view? The example that I provided was from the dragon book. CMU uses that same example for one of its ssa slides for an compiler optimization course. This makes me think that I can I indeed lower an ast to ssa that looks like the example I gave and still exploit the ssa for optimization. By the way the examples I provided a…
You should probably start on the Wikipedia page for SSA, which - since the dragon book doesn't teach what SSA actually is, is a reasonable starting point https://en.m.wikipedia.org/wiki/Static_single-assignment_for... Note that even though it provides many examples and other comparisons it not once mentions 3AC (and vice versa actually). Under Benefits you can find links to various optimizations some of whose pages reference what SSA helps with. None of them have much if anything to do with 3AC.
That the CMU simply copies an example straight from the book and provides no further explanation and maybe even doesn't mention PHIs (?) doesn't speak for that course at all. Especially if you take a look at the list of compilers that do use SSA on Wikipedia and note that pretty much all major programming language implementations use SSA.
Of course you can lower an AST to SSA that looks like the example (except the example is so rudimentary it's still missing the very necessary PHI functions) and you can even make it have 3AC form and still exploit the SSA properties in optimizations. It's just that the properties and the SSA form still have no real relation except that both modify your list of instructions and claiming that there's one that's somehow meaningful or that 3AC gives you anything that SSA does is at best grossly misleading by a textbook.