Re:My First Fifteen Compilers
by derefr on Friday July 12, 2019 @10:18AM
(#20420904)
Programming-language syntax specifically is pretty daunting to formalize. Programming languages (other than Lisp) have huge numbers of syntactic “features”! And they usually contain binary expressions with precedences, which—if your grammar notation doesn’t have a specific DSL for these—introduces the special hell of coercing a parser-generator into implementing precedence-climbing. This makes for hella opaque grammars that you really can’t understand until you’ve had to implement precedence-climbing yourself at least once.
PL grammars also tend to have a lot of degrees of freedom in the “production” side of them; because it’s basically up to you (as the author of the compiler) what the resulting AST output by the generated parser will “need” to look like, as you also control the next stage that consumes the AST, and there’s nothing forcing that API between the generated parser and your “code DOM builder” to take any particular shape. This is bad, for https://en.m.wikipedia.org/wiki/Analysis_paralysis reasons. Things are a lot easier when you lock down an AST “shape” (i.e. a known data structure) that your generated parser should aim to output. (Once you have this, you can write a conformance test suite as a set of {text input, data-structure output} pairs!)
So, my suggestion would be to 1. try writing a grammar for something simpler than a complete language syntax, 2. where it’s obvious what the resulting AST “should” look like.
Personally, I threw myself into the deep end, and my first experience with grammars was in writing a PR for a library that parsed just function-signatures of a particular language, previously with a hand-rolled parser. I wrote a grammar for a parser-generator to replace this hand-rolled parser. This was pretty good as an exercise, as I just had to match the output of the existing parser.
But even then, it was a bit of a struggle trying to understand what this thing was I was parsing at the same time that I was trying to write the grammar for it.
I’d instead suggest, a learning exercise, taking a text format you know well (for example, URLs, or email addresses) which is specified rigidly by an RFC (including a BNF grammar!) and attempting to recreate the BNF grammar (or an equivalent for your parser-generator of choice) by reading the RFC but avoiding the BNF part until you’re ready to “check your work.”
PL grammars also tend to have a lot of degrees of freedom in the “production” side of them; because it’s basically up to you (as the author of the compiler) what the resulting AST output by the generated parser will “need” to look like, as you also control the next stage that consumes the AST, and there’s nothing forcing that API between the generated parser and your “code DOM builder” to take any particular shape. This is bad, for https://en.m.wikipedia.org/wiki/Analysis_paralysis reasons. Things are a lot easier when you lock down an AST “shape” (i.e. a known data structure) that your generated parser should aim to output. (Once you have this, you can write a conformance test suite as a set of {text input, data-structure output} pairs!)
So, my suggestion would be to 1. try writing a grammar for something simpler than a complete language syntax, 2. where it’s obvious what the resulting AST “should” look like.
Personally, I threw myself into the deep end, and my first experience with grammars was in writing a PR for a library that parsed just function-signatures of a particular language, previously with a hand-rolled parser. I wrote a grammar for a parser-generator to replace this hand-rolled parser. This was pretty good as an exercise, as I just had to match the output of the existing parser.
But even then, it was a bit of a struggle trying to understand what this thing was I was parsing at the same time that I was trying to write the grammar for it.
I’d instead suggest, a learning exercise, taking a text format you know well (for example, URLs, or email addresses) which is specified rigidly by an RFC (including a BNF grammar!) and attempting to recreate the BNF grammar (or an equivalent for your parser-generator of choice) by reading the RFC but avoiding the BNF part until you’re ready to “check your work.”