Parsing – Choosing a Parser for a Code Beautifier

code formattinglexerparsing

I'm in the planning stage of making a code beautifier (similar to AStyle or Uncrustify) – originally I was going to just contribute to one of those projects,
but reviewing their source led me to the conclusion that I have different design goals and that their source is written in a way that makes it difficult for an outsider to easily contribute. AStyle, for example, instead of building some sort of AST, uses over 100 state variables such as isInComment, foundClassHeader, isLineReady, etc.

I'm deciding between using scanner and parser generators (such as flex and bison) and writing my own parsing system. Which would be a better approach? I've been through a compilers class in university, so I do have some experience with scanning and parsing theory. Below are the advantages I've thought of for each:

Generators

  • Arguably simpler/faster to develop
  • Possibly more optimized than my initial stab at a custom parser, though a custom one might leave more room for improvement

Custom parser

  • Arguably easier to debug
  • Programmers seems to prefer custom lexers and parsers in past questions – "Anyone who wants a decent lexer doesn't use Lex"
  • Fewer dependencies
  • Could possibly allow for "fuzzier" parsing – since I'm just developing a beautifier, the parser wouldn't need to be nearly as strict or detailed as one for a compiler
  • Parallelization – flex and bison (or what I've seen of them) use global state. If I want to parse multiple files at once (in separate threads), a custom solution would be simpler to compartmentalize

Best Answer

It's not a choice between flex/bison or nothing. There are several options out there. I used antlr for a recent project and found it very nice to work with. Some things you might not have considered:

  • Lexers aren't that difficult, but parsers have a considerable number of gotchas you won't even realize until they hit you. Widely used tools have already solved a bunch of problems you don't even know exist yet.
  • Your parser will still need to be just as strict as a compiler. The difference will be you can use a simpler grammar in some places, but that will probably be offset by needing to use more complex grammar in other places. For example, code beautifiers often want to preserve an intentional newline that a regular compiler just lumps into "whitespace." If your language has a preprocessor, a beautifier will have to incorporate that into the grammar, whereas a compiler's parser won't.
  • Grammars are extremely difficult to debug. Tools like antlr have devoted considerable effort to producing useful error messages. Even if you do go with a custom parser, you may still find it useful to use an existing parser generator to debug your grammar.
Related Topic