9 ms·

I don't understand why so many people glorify hand-written parsers. Maybe because they never used good parser generators (not unlike type systems and Java) ? P

• dukoid 10y ago
  Because the problem is not parsing alone, but doing type checks / ambiguity resolution during parsing and linking up the parse tree with type information etc. See http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... Also, you people may just want to learn how to build a parser. Shameless plug if you need a small but flexible expression parser for java: https://github.com/stefanhaustein/expressionparser https://github.com/stefanhaustein/expressionparser
  • Drup 10y ago
    My point is precisely that, if you are creating your language from scratch, you shouldn't have to do that. Those are mistake needed because the C grammar is full of cruft (and the C++ one is even worse). It's much better, for a new language, to separate type checking from parsing completely, and to avoid any ambiguity.
    • deleted 10y ago
      [deleted]
    • PaulHoule 10y ago
      In theory yes, in practice, if you want to make a serious improvement in the ergonomics of programming languages for "ordinary" folks, you have to face up to the fact that natural languages don't make an artificial distinction between different aspects of language.
  • Ericson2314 10y ago
    > Because the problem is not parsing alone, but doing type checks / ambiguity resolution during parsing and linking up the parse tree with type information etc. Holy shit, people think that's a good idea? Pipelines please!
    • munificent 10y ago
      It's often faster to do as much as you can in a single pass, and language front ends are one of those areas where squeezing every last drop of performance out still really matters.
      • Drup 10y ago
        It's actually faster to separate things, because you will be able to implement them cleanly. Having a good pipeline such as "text -> AST -> typed AST -> IR -> .... -> ASM/VM code" is very valuable. The costy parts are the middle layer optimization anyway. Typechecking time, for a well written type checker, is not that big.
      • Ericson2314 10y ago
        I think incremental compilation is a far more elegant and efficient way to shorten debug cycles. Also makes IDE stuff easier too.
  • deleted 10y ago
    [deleted]
• UK-AL 10y ago
  There's a reason nearly every actually used programming language parser is hand rolled. It's easier for adding errors messages, debugging and diagnostics tools. I know modern parser generators can do this as well. It's just easier in a recursive descent parser. Learning to use parser generator is a learning experience in itself. Most can be pretty complicated to use, once you get past the basics. Yet nearly every programmer can understand a recursive descent parser. You can debug them using standard breakpoints for example. Yet parser generators can output quite difficult error messages, unless you have had a parser education. In practical implementations, recursive descent can be optimised to be really fast, and to use a low amount of memory.
  • wruza 10y ago
    >I know modern parser generators can do this as well Can you please list them here? These without build/runtime dependencies on java and other non-default platforms. That alone would make the whole thread.
    • paulddraper 10y ago
      ANTLR has hooks you can use to help the error message. Though it uses Java. What is a "default platform"?
  • userbinator 10y ago
    Yet nearly every programmer can understand a recursive descent parser. ...and I also hypothesise that nearly every programmer will come up with some form of recursive descent parser if asked to parse a recursive language --- without ever having heard of the term "recursive descent" nor parser generators. It's the intuitive, "natural" solution to the problem.
• masklinn 10y ago
  > Maybe because they never used good parser generators (not unlike type systems and Java) ? Is there such a thing as a "good parser generator" where "good" includes "generates at least decent error messages"? > Personal opinion: writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans. Hardly. Humans have way less trouble with ambiguity than computers do, as demonstrated by, well, the entire history of programming languages. If syntactic simplicity and regularity were what humans seeked, the primary languages in use would be Lisps, Forths and Smalltalks, not C derivatives.
  • marcosdumay 10y ago
    What are those "good error messages" in the parsing stage you keep talking about? I don't remember I've ever used a language that reported anything different from "syntax error at line X" at this stage.
    • megous 10y ago
      You can get a parser generator to automagically list you expected (non-)terminals at this point. It may not be helpful though, depending on the location of the error. But it is something at least.
    • btilly 10y ago
      As a random example from Perl, Unmatched ( in regex... is the error when you open a capturing group in a regex and fail to close it. In a recursive descent parser, this type of error is very easy to generate because working top down you know what you are in the middle of trying to do when you hit the error. But a bottom up parser lacks that context - it just knows where it was when it got stuck.
• tyoverby 10y ago
  Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so: * Incremental re-parsing. If a user in the IDE changes the document, we need to reparse the file, but we want to do this while using as little memory as possible. To this end, we re-use AST nodes from previous parses. * Better error reporting. Parser generators are known for producing terrible errors. While you can hack around this, by using recursive-descent, you can get information from further "up" the tree to make your more relevant to the context in which the error occurred. * Resilient parsing. This is the big one! If you give our parser a string that is illegal according to the grammar, our parser will still give you a syntax tree! (We'll also spit errors out). But getting a syntax tree regardless of the actual validity of the program being passed in means that the IDE can give autocomplete and report type-checking error messages. As an example, the code "var x = velocity." is invalid C#. However, in order to give autocomplete on "velocity", that code needs to be parsed into an AST, and then typechecked, and then we can extract the members on the type in order to provide a good user experience. My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P
  • bbcbasic 10y ago
    Thanks it's great to hear from someone that makes the tools I use everyday. > My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P C# 8 maybe?
    • marxidad 10y ago
      Untyped S-Expressions would be taking a step back from a C# perspective.
      • e12e 10y ago
        I don't see how s-expressions are inheritently less "typed" than utf-8 text? Have a compiler target dialect that expects "(int 5)" and "(int x)" have a type-inference step that target such "typed" s-expressions?
    • 10y ago
• zzzcpan 10y ago
  I don't understand your complaint, it's faster and easier to implement a recursive descend parser, than to use a yacc-like parser generator. It's not much of a choice, isn't it?
  • btilly 10y ago
    If you know the toolchains, that is backwards. It is faster and easier to use a parser generator, and easier to figure out what it is doing when you read one. Plus it performs better. But recursive descent gives you more flexibility and better error messages.
• stcredzero 10y ago
  writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans. In my (admittedly limited) experience, most grammars for programming languages that are supposed to be easy on humans end up being harder to parse. (See below) One notable exception is, of course, Smalltalk. One criticism I have of this article, is that it is written in a way that obscures the fact a top-down parser is an LL(k) parser. I'd posit that sticking to an LL(1) grammar is a great way to wind up with a simpler syntax that lacks sticky syntactic sugar that will be hard to optimize and build software tool for later on. (AT least for your personal learning hobby project. But in that case, at least use a separate Lexer!) You can't introduce bullshit ambiguous extensions to your grammar Ruby: http://po-ru.com/diary/ruby-parsing-ambiguities/ http://po-ru.com/diary/ruby-parsing-ambiguities/
  • munificent 10y ago
    > One criticism I have of this article, is that it is written in a way that obscures the fact a top-down parser is an LL(k) parser. Yes, I worry a lot that I conveniently designed Lox to be LL(1) which is why the parsing is so straightforward, but I don't spend a lot of time telling the reader about that fact. At the very end, there's an aside that hints at that, but that's about it. Unfortunately, the chapter is quite long already, and it's hard to even start talking about what makes one syntax easier to parse than another without having to go pretty deep into lookahead, LL(k), left-factoring, etc. So, for better or worse, I chose to leave it out. I look at this book as a guided tour of the language space. The reader may not know that they are being carefully herded away from the sketchy parts of town and not realize that things may appear cleaner and safer than they actually are when you start exploring on your own. At the same time, it does ensure that their first experience in the area is a happy, positive one. My hope is that that will give them enough momentum to explore more, run into some of those nasty spots, and still have the fortitude to overcome them.
• zeptomu 10y ago
  > I don't understand why so many people glorify hand-written parsers. [...] I would say because they make the easy things easier, but the hard things harder. If one tries to do something more elaborated, like getting a data structure for the AST (most tutorials just build simple "accepters" which I find unacceptable) and passing it to different functions - which is a standard procedure in an interpreter or compiler - things are not so trivial anymore and you need to know your generator really well and hope that your use case is supported. Another approach are parser generators like you find in functional languages, and I really like them, as you do not have to learn an additional language and they compose incredible well. They can blow-up your memory requirements but this is another story.
• specialist 10y ago
  To better understand how generated parsers work. ANTLR LL(k) thru LL(*) is largely a black box for me. I can't say writing my own helped my ANTLR skills. But hopefully I'm doing less trial and error now.
• camus2 10y ago
  > I don't understand why so many people glorify hand-written parsers. it is a learning exercise. Once you have written one, you can choose to go for yacc and co, or stick with hand written ones.
• marssaxman 10y ago
  I've never used a parser generator that was worth the extra time and hassle incurred by adding code generation and another implementation language into the project. Parsing just isn't that hard, and having your parsing code written in the same language as the rest of your compiler pays off over the long run.