4 ms·

yacc is key

by nikkinana 5y ago

yacc is key

chrisseaton 5y ago
Never use Yacc. Just write your own parser.
- eatonphil 5y ago
  Adding on, the fraction of "real" language implementations using handwritten parsers vs. parser generators basically seems to be half and half. The Wikipedia list of Bison users even calls out that a number of them switched from Bison to handwritten parsers. https://en.wikipedia.org/wiki/GNU_Bison#Use https://en.wikipedia.org/wiki/GNU_Bison#Use
- p4bl0 5y ago
  Why would you say that? Yacc and other parser generators exist for a good reason: hand written parsers can be quite hairy to debug and extend, while parser generators offer a domain specific language to specify your grammar and can generate efficient parser code based on it. What are the arguments in favor of manually writing parsers?
  - codr7 5y ago
    What few seem to realize is that it's perfectly possible to abstract out some of the work and create an extensible foundation for manual parsers. Since it's all regular code, you can use the full power of the host language to deal with the problem. https://github.com/codr7/swifties/blob/main/Sources/Swifties/Parser.swift https://github.com/codr7/swifties/blob/main/Sources/Swifties...
    - p4bl0 5y ago
      I understand that, but I still find it easier to write/maintain/extend a grammar than a parser for that grammar.
      - brundolf 5y ago
        If you've got the right utility functions, a handwritten parser visually maps very directly to its grammar. It won't be as concise of course, but cognitively you can work with it almost as if it were just a grammar.
  - chrisseaton 5y ago
    Fundamentally I don't think parsing is a problem that's complex enough to warrant a custom tool and language. And even if it was Yacc is the wrong tool for the job in most cases. Since most languages are context-sensitive, you almost always have to bend Yacc, which is designed for context-free languages, out of shape to apply it. It's a hammer but we hardly have any nails, and the nails can just be pushed in by hand without a hammer, and they're the wrong type of nails anyway so that hammer isn't really compatible, and top of that it's a really expensive hammer.
    - rightbyte 5y ago
      Isn't the context sensitivity handled when you build an AST with the action statements in Yacc?
      - chrisseaton 5y ago
        Yes - so straight away you have to leave the DSL and bypass the formal mode of Yacc. At which point why bother with it? If the first thing you need to do with your tool is hack around it, maybe the tool isn’t so well-designed? And actions often do things like side-effect changes to the lexer state, so it gets worse from there.
- arcticbull 5y ago
  Lemon is an infinitely better parser generator than Yacc; it solves a lot of the issues that make Yacc terrible to work with: named non-terminals, non-terminal destructors, re-entrancy, etc. It's part of the SQLite codebase. Highly recommended. In many cases, though, I think parser combinators thread the needle elegantly - nom in Rust for instance. Or even just a hand-rolled LL(1).

yacc is key

chrisseaton 5y ago

Never use Yacc. Just write your own parser.

eatonphil 5y ago
Adding on, the fraction of "real" language implementations using handwritten parsers vs. parser generators basically seems to be half and half. The Wikipedia list of Bison users even calls out that a number of them switched from Bison to handwritten parsers. https://en.wikipedia.org/wiki/GNU_Bison#Use https://en.wikipedia.org/wiki/GNU_Bison#Use
p4bl0 5y ago
Why would you say that? Yacc and other parser generators exist for a good reason: hand written parsers can be quite hairy to debug and extend, while parser generators offer a domain specific language to specify your grammar and can generate efficient parser code based on it. What are the arguments in favor of manually writing parsers?
- codr7 5y ago
  What few seem to realize is that it's perfectly possible to abstract out some of the work and create an extensible foundation for manual parsers. Since it's all regular code, you can use the full power of the host language to deal with the problem. https://github.com/codr7/swifties/blob/main/Sources/Swifties/Parser.swift https://github.com/codr7/swifties/blob/main/Sources/Swifties...
  - p4bl0 5y ago
    I understand that, but I still find it easier to write/maintain/extend a grammar than a parser for that grammar.
    - brundolf 5y ago
      If you've got the right utility functions, a handwritten parser visually maps very directly to its grammar. It won't be as concise of course, but cognitively you can work with it almost as if it were just a grammar.
- chrisseaton 5y ago
  Fundamentally I don't think parsing is a problem that's complex enough to warrant a custom tool and language. And even if it was Yacc is the wrong tool for the job in most cases. Since most languages are context-sensitive, you almost always have to bend Yacc, which is designed for context-free languages, out of shape to apply it. It's a hammer but we hardly have any nails, and the nails can just be pushed in by hand without a hammer, and they're the wrong type of nails anyway so that hammer isn't really compatible, and top of that it's a really expensive hammer.
  - rightbyte 5y ago
    Isn't the context sensitivity handled when you build an AST with the action statements in Yacc?
    - chrisseaton 5y ago
      Yes - so straight away you have to leave the DSL and bypass the formal mode of Yacc. At which point why bother with it? If the first thing you need to do with your tool is hack around it, maybe the tool isn’t so well-designed? And actions often do things like side-effect changes to the lexer state, so it gets worse from there.
arcticbull 5y ago
Lemon is an infinitely better parser generator than Yacc; it solves a lot of the issues that make Yacc terrible to work with: named non-terminals, non-terminal destructors, re-entrancy, etc. It's part of the SQLite codebase. Highly recommended. In many cases, though, I think parser combinators thread the needle elegantly - nom in Rust for instance. Or even just a hand-rolled LL(1).