Syntax-Directed Translation, Parsing (2.3, 2.4)

So I skipped the section 2.3 exercises. They were asking for a bunch of translation schemes that were almost identical to the ones given in the chapter, which is boring. I was thinking about just writing code for them, but I figured I’d probably screw it up pretty badly so I just let it go.
2.3 was about syntax-directed translation. Basically the idea is that you can assign values to nodes of a parse tree and then use just that information, along with the position in the parse tree, to emit what you need. Pretty simple stuff to understand. It went into some detail about pre- and post-traversal execution and ways to do some translation without even constructing the tree explicitly. All neat stuff but not very interesting to explain minute details of on a blog.

2.4 is about parsing. It talks a little bit about the differences between top-down (start with the starting nonterminal and construct a parse tree) and bottom-up parsing (the opposite). There’s a bunch of detail about predictive parsers, which seems like a really powerful technique – if you design the grammar for your language appropriately, a predictive parser should be pretty easy to write. The idea is, you look at the next token, and given the context you’re currently in and the value of that token, you know what you’re parsing.
So if you have an if statement, it looks like (in many C-family languages):

if ( expression ) { statements }

And no other language construct starts with ‘if.’ So as soon as you see an ‘if,’ you know exactly what the next several syntax elements will be, and, further, you have a bunch of information about them – say there’s an expression that starts with foo and a statement that starts with foo – you can’t mix them up, because you know whether you’re parsing an expression or a statement next.

Anyway, then they went ahead and asked a question about a grammar that can’t be parsed predictively, which gave me some amount of trouble and delayed this post a lot. This section’s solutions were pure coding, so there’s nothing to write up here. Take a look on my github if you’re interested.
There’s currently no unit tests, because I am an undisciplined knave when I am working alone. Maybe I’ll add those before the next blog post. It’d be a good chance to finally spend some time with NUnit. So far, not having any luck getting it running, though.

This entry was posted in Dragon book. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s