This makes the book sound very well structured! I also found Ghuloum's paper inspirational.
Working through 'Writing A C Compiler'
21–30 of 44 posts
Re: Working through 'Writing A C Compiler'
#22Earlier quoted context omitted.
What? The visitor pattern is a technique for dynamic dispatch on two values (typically one represents 'which variant of data are we working with' and the other 'which operation are we performing'). You would not generally use that in recursive descent parsing, because when parsing you don't have an AST yet, so 'which variant of data' doesn't make sense, you are just consuming tokens from a stream.
> you are just consuming tokens from a stream. My guy... Do you think that parsers just like... concat tokens into tuples or something....??? Do you not understand that after lexing you have tokens (which are a "type") and AST node construction (an "operation") and that the grammar of a language is naturally a graph .... Like where else would you get the "recursion" from.... If that doesn't make sense I invite you to…
I see that you've found an example of how recursive descent parsing actually can be implemented with the visitor pattern, which I've never come across before, and I didn't read it carefully enough to understand the motivation - but that doesn't mean they are the same thing - the recursive descent parsers I've seen before just inspect which tokens are seen and directly construct AST nodes
as an adendum, the reason I don't understand the motivation is that the visitor pattern in the way I described it is useful when you have many different operations to perform on your AST. If you have only one operation on tokens - parsing into an AST - I'm not sure why you need dynamic dispatch on a second thing, the first thing being the token type. Maybe the construction is that different operations correspond to different 'grammar rules'?
Re: Working through 'Writing A C Compiler'
#23Earlier quoted context omitted.
> you are just consuming tokens from a stream. My guy... Do you think that parsers just like... concat tokens into tuples or something....??? Do you not understand that after lexing you have tokens (which are a "type") and AST node construction (an "operation") and that the grammar of a language is naturally a graph .... Like where else would you get the "recursion" from.... If that doesn't make sense I invite you to…
I see that you've found an example of how recursive descent parsing actually can be implemented with the visitor pattern, which I've never come across before, and I didn't read it carefully enough to understand the motivation - but that doesn't mean they are the same thing - the recursive descent parsers I've seen before just inspect which tokens are seen and directly construct AST nodes as an adendum, the reason I d…
> just inspect which tokens are seen and directly construct AST nodes
I'll repeat myself: this is not possible because you need to recursively construct the nodes (how else would you get a tree...).
Re: Working through 'Writing A C Compiler'
#24Earlier quoted context omitted.
I see that you've found an example of how recursive descent parsing actually can be implemented with the visitor pattern, which I've never come across before, and I didn't read it carefully enough to understand the motivation - but that doesn't mean they are the same thing - the recursive descent parsers I've seen before just inspect which tokens are seen and directly construct AST nodes as an adendum, the reason I d…
> just inspect which tokens are seen and directly construct AST nodes I'll repeat myself: this is not possible because you need to recursively construct the nodes (how else would you get a tree...).
I think I'm missing something here. if you have a grammar rule R with children A and B, and a function in your recursive descent parser that corresponds to R, why can R not call the parser functions for A and B, which return AST nodes themselves, and then construct another AST node using the result of those? Where was the visitor pattern required here?
Re: Working through 'Writing A C Compiler'
#25Earlier quoted context omitted.
> you are just consuming tokens from a stream. My guy... Do you think that parsers just like... concat tokens into tuples or something....??? Do you not understand that after lexing you have tokens (which are a "type") and AST node construction (an "operation") and that the grammar of a language is naturally a graph .... Like where else would you get the "recursion" from.... If that doesn't make sense I invite you to…
I see that you've found an example of how recursive descent parsing actually can be implemented with the visitor pattern, which I've never come across before, and I didn't read it carefully enough to understand the motivation - but that doesn't mean they are the same thing - the recursive descent parsers I've seen before just inspect which tokens are seen and directly construct AST nodes as an adendum, the reason I d…
> why you need dynamic dispatch on a second thing
You're overindexing on maximally generic visitor pattern. If you have one type of visitor but nonetheless dispatch based on type that's still visitor pattern.
EDIT: to be honest who even cares. My initial point was why in the hell would you stop reading a book because a particular "pattern" offends you. And I'll reassert it here: who cares whether a recursive descent parser fits the exact definition of visitor pattern or not - you have members of a class that do stuff (construct AST nodes) and possibly track other data and then call other members. I usually call that a visitor class even if it's the only one that ever exists
Re: Working through 'Writing A C Compiler'
#26Earlier quoted context omitted.
I see that you've found an example of how recursive descent parsing actually can be implemented with the visitor pattern, which I've never come across before, and I didn't read it carefully enough to understand the motivation - but that doesn't mean they are the same thing - the recursive descent parsers I've seen before just inspect which tokens are seen and directly construct AST nodes as an adendum, the reason I d…
> why you need dynamic dispatch on a second thing You're overindexing on maximally generic visitor pattern. If you have one type of visitor but nonetheless dispatch based on type that's still visitor pattern. EDIT: to be honest who even cares. My initial point was why in the hell would you stop reading a book because a particular "pattern" offends you. And I'll reassert it here: who cares whether a recursive descent…
Ok, that's true, but my claim is that recursive descent parsing does not have to use the visitor pattern and indeed using recursive descent parsing is not the same as using the visitor pattern (you can do the former without the latter and I claim that you usually do)
Re: Working through 'Writing A C Compiler'
#27[deleted]
Re: Working through 'Writing A C Compiler'
#28Earlier quoted context omitted.
What? The visitor pattern is a technique for dynamic dispatch on two values (typically one represents 'which variant of data are we working with' and the other 'which operation are we performing'). You would not generally use that in recursive descent parsing, because when parsing you don't have an AST yet, so 'which variant of data' doesn't make sense, you are just consuming tokens from a stream.
> you are just consuming tokens from a stream. My guy... Do you think that parsers just like... concat tokens into tuples or something....??? Do you not understand that after lexing you have tokens (which are a "type") and AST node construction (an "operation") and that the grammar of a language is naturally a graph .... Like where else would you get the "recursion" from.... If that doesn't make sense I invite you to…
OK I might be wrong about the visitor pattern, but what I really did not like is to use the accept() and visitBlah() way to execute AST nodes: https://craftinginterpreters.com/representing-code.html#the-...
I did continue reading the book (not the original author of that reply) but I do think it is distracting for newbies. I had to come back to this page over and over again to recollect memory about the pattern, because I usually read it one chapter or a few sections every week, so every time I had to remind myself how this visitBlah() and accept() pair works. I really think a big switch() (or anything that works but is simpler) would be a lot easier to understand.
The other reason I dislike this kind of stuffs is that I have someone in the team who really likes to use patterns for every piece of code. It's kinda difficult to tell whether it is over-engineering or not, but my principle is that intuition always beats less lines of code (or DRY), unless it is absurdly more lines of code or repetition. And to test that principle you just grab a newbie and see which one makes more sense to him.
Re: Working through 'Writing A C Compiler'
#29The crafting interpreting asks the reader to use the visitor pattern, and this was quite a turn off for me, I stopped there.
> The crafting interpreting asks the reader to use the visitor pattern... ...or just a big old, plain jane switch statement. In my current project I modified my ASDL generator to output a C instead of C++ AST and the visitor pattern carried over until realizing a switch statement is just as good (or better) in C so I ripped out that part of the template file. The choice was to write a dispatch function which called t…
I think I did something similar for an emulator. Instead of using a big switch I simply used a big array of function pointers. So if it is a BLAH opcode, the execution code simply call fp_list[BLAH](op). But I guess it is a bit too much for CPUs that have tons of operations.
Re: Working through 'Writing A C Compiler'
#30Earlier quoted context omitted.
> you are just consuming tokens from a stream. My guy... Do you think that parsers just like... concat tokens into tuples or something....??? Do you not understand that after lexing you have tokens (which are a "type") and AST node construction (an "operation") and that the grammar of a language is naturally a graph .... Like where else would you get the "recursion" from.... If that doesn't make sense I invite you to…
OK I might be wrong about the visitor pattern, but what I really did not like is to use the accept() and visitBlah() way to execute AST nodes: https://craftinginterpreters.com/representing-code.html#the-... I did continue reading the book (not the original author of that reply) but I do think it is distracting for newbies. I had to come back to this page over and over again to recollect memory about the pattern, beca…
> I really think a big switch() (or anything that works but is simpler) would be a lot easier to understand.
It's much easier conceptually to implement this using recursion instead of a while loop and a token stack (it's basically DFS). So I disagree with you there.
> The other reason I dislike this kind of stuffs is that I have someone in the team who really likes to use patterns for every piece of code. It's kinda difficult to tell whether it is over-engineering or not, but my principle is that intuition always beats less lines of code (or DRY), unless it is absurdly more lines of code or repetition. And to test that principle you just grab a newbie and see which one makes more sense to him
I'm with you - I really don't give a shit about patterns (which was my whole original point - who cares). But that last part I don't agree with - systems code (like a parser) doesn't need to be legible to a noob. Of course we're talking about a textbook so your probably right but like I said most production parsers and AST traversals are written exactly this same way. So anyone learning this stuff hoping to get a job doing it should just get used to it.