Simon's blog

Working from home

Seriously, I got a lot of good work done today; I fleshed out the outline of my new book a little more, and I finished off some more work on Shishi. I spent the morning working out how to remove recursion from Shishi - then it dawned on me that since Shishi's a recursive descent parser (essentially) that removing the recursion may turn out to be difficult. This has various knock-on effects for the Perl 6 regex engine - people have to be very careful not to blow the C stack if they implement the regexes naively. I'm currently looking up clever ways to turn the depth-first search into an iterative algorithm. (Yes, I know I have to maintain a stack of child nodes, but that's as far as I've got.)


One of the things that makes it really difficult to create shishi parsers at the moment is the fact that you create a node which has to jump to the next node in the chain. For instance, given ab, you could write a node which matches a which then goes on to the node which matches b. Unfortunately, when you create the a node, you haven't created the b node yet. So you end up with a dangling pointer and have to backpatch and it's ugly as all hell.