Pete's Log: black magic: recursive-descent
Entry #831, (Coding, Hacking, & CS stuff)(posted when I was 22 years old.)
So I'm teaching class tomorrow for compilers since Dr Freeh is out of town. This should prove to be an interesting adventure. The fun thing is actually reading the chapter in the book on top down parsing, I never read it when I actually took the class. Top down parsing is one of those things that just clicked for me, it immediately made intuitive sense, so I just wrote my parser for 443 last year without ever bothering to read the chapter. But I figure if I'm gonna lecture on the subject I should have a better clue as to the official lingo of the business 'n such.
As part of the preparation, I've written a few recursive-descent parsers for a simple expression grammar. recursive descent rocks. It's such an amazing bit of black magic. It's extraordinarily simple, yet so powerful. Granted, you can do more with bottom up parsers, but they lack the simplicity. Rarely are bottom up parsers written by hand, they're mostly generated by tools like yacc. So three versions of the same parser: one that just verifies that the input is valid. A second that will compute the value of the input expression, and a third that will create a simplistic syntax tree of the input. syntax tree. woo.
but thinking about parsers and syntax trees and grammars, I'm almost kinda tempted to go back to the parser I wrote for my OS shell project and rewrite it as a recursive descent parser, possibly adding lex for tokenizing. The parser I wrote for that is a bastardization ... but it works...
the whole field of compilers is cool. I really dig this stuff. I really wish there was an advanced compilers course that covered all the cool optimization techniques out there. but compilers is definitely an excellent course, just because it pulls together so much of the stuff learned in previous courses. data structures, automata, os, and so on... so here's hoping I don't screw up tomorrows lecture too bad...