6

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
Improve this question
3
  • If you want to beautify C or C++, take the creative use of macros than some code base have into account (see QT for instance). Then a code beautifier needs to be able to recreate the input exactly; IMHO that should even be the baseline above which you add transformations.
    – AProgrammer
    May 21, 2013 at 15:43
  • Certainly - I plan to design the beautifier so that it doesn't modify things it doesn't understand. Better safe than sorry.
    – Matt Kline
    May 21, 2013 at 16:00
  • 1
    Someone who doesn't recognize the value of an AST over stateful-control-flow-insanity probably needs a beautifier just to make their code resemble something readable. Irony.
    – Jimmy Hoffa
    May 21, 2013 at 16:29

1 Answer 1

Reset to default
4

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.
Improve this answer
4
  • 3
    "Widely used tools have already solved a bunch of problems you don't even know exist yet." I 100% agree.
    – Mike
    May 21, 2013 at 16:36
  • I apologize if these responses are naive, but, 1. I didn't plan on building whitespace into the grammar, but by storing the row an column of each token I scan, which I could use later when I do formatting. 2. Why would I have to incorporate preprocessing into the grammar?
    – Matt Kline
    May 21, 2013 at 17:13
  • @slavik, storing row and column accomplishes the same thing, but may or may not be more difficult to use. It's hard to know without trying it. You need to account for preprocessing one way or another, because it will be present in your input and output, and presumably will have its own formatting rules.
    – Karl Bielefeldt
    May 21, 2013 at 17:25
  • Thank you very much for the insight! I may try my hand at my own parser for educational purposes (since this is a hobby project), but I'll certainly keep in mind the points you've made.
    – Matt Kline
    May 23, 2013 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.