4 ms·

Is it nothing? I agree it's easy, but why do it if you don't need to. Besides it being "nothing" compared to all the rest of the code in the compiler it's also

by tinco 4y ago

Is it nothing? I agree it's easy, but why do it if you don't need to. Besides it being "nothing" compared to all the rest of the code in the compiler it's also the least interesting part of it, unless you're trying to aim for some real fancy programmer comfort features like Rust and newer versions of GCC are. You can sketch your grammer out in EBNF, and just throw that into a parser generator and bam you're ready to spit out some byte code. And just absolutely talking, 10-20k lines of code is never nothing. That's months if not years of coding, that has to maintained and expanded upon as your project grows.

foldr 4y ago
You can't generally just throw EBNF grammars into a parser generator and get good results. For example, YACC will only accept LALR(n) grammars, not any grammar that can be expressed in EBNF. Some newer parser generators are more flexible, but you'll still have to do some wrangling. Once you get used to writing recursive descent parsers you can bash them out quite quickly. You can write a mostly-working parser for a programming language in a few days. 10-20k lines of code might sound like quite a lot, but it's mostly repetitive code that's easy to get right and easy to write tests for. Recursive descent parsers can often be easier to maintain than parser generator based parsers because you don't have to keep hacking around the limitations of the generator. For example, C and C++ don't permit any kind of clean separation between lexing, parsing and symbol resolution. Even gcc's C parser and lexer combined are only about 30,000 LOC, depending on which files you count besides the main parser module: https://github.com/gcc-mirror/gcc/blob/master/gcc/c/c-parser.cc https://github.com/gcc-mirror/gcc/blob/master/gcc/c/c-parser... And this is code written in Cish C++. In a higher-level language it could be significantly more concise.
- srcreigh 4y ago
  Hey foldr, re higher level language parser, I’d just like to say at uwaterloo it was common to use racket to write the compiler for the above^5 mentioned class (you could use racket or C). Is this what you had in mind? Which language is best in your opinion for a parser?
  - foldr 4y ago
    If you're writing a traditional recursive descent parser, it doesn't make much difference (IMHO). Any vaguely modern programming language will work fine. If you want to use parser combinators, then something with basic support for functional programming (particularly closures and and a lightweight lambda syntax).

by tinco 4y ago

foldr 4y ago

You can't generally just throw EBNF grammars into a parser generator and get good results. For example, YACC will only accept LALR(n) grammars, not any grammar that can be expressed in EBNF. Some newer parser generators are more flexible, but you'll still have to do some wrangling. Once you get used to writing recursive descent parsers you can bash them out quite quickly. You can write a mostly-working parser for a programming language in a few days. 10-20k lines of code might sound like quite a lot, but it's mostly repetitive code that's easy to get right and easy to write tests for. Recursive descent parsers can often be easier to maintain than parser generator based parsers because you don't have to keep hacking around the limitations of the generator. For example, C and C++ don't permit any kind of clean separation between lexing, parsing and symbol resolution. Even gcc's C parser and lexer combined are only about 30,000 LOC, depending on which files you count besides the main parser module: https://github.com/gcc-mirror/gcc/blob/master/gcc/c/c-parser.cc https://github.com/gcc-mirror/gcc/blob/master/gcc/c/c-parser... And this is code written in Cish C++. In a higher-level language it could be significantly more concise.

srcreigh 4y ago
Hey foldr, re higher level language parser, I’d just like to say at uwaterloo it was common to use racket to write the compiler for the above^5 mentioned class (you could use racket or C). Is this what you had in mind? Which language is best in your opinion for a parser?
- foldr 4y ago
  If you're writing a traditional recursive descent parser, it doesn't make much difference (IMHO). Any vaguely modern programming language will work fine. If you want to use parser combinators, then something with basic support for functional programming (particularly closures and and a lightweight lambda syntax).