10 ms·

Parsing Awk Is Tricky

• RodgerTheGreat 2y ago
  I think this is a good illustration of why parser-generator middleware like yacc is fundamentally misguided; they create totally unnecessary gaps between design intent and the action of the parser. In a hand-rolled recursive descent parser, or even a set of PEG productions, ambiguities and complex lookahead or backtracking leap out at the programmer immediately.
  • jasone 2y ago
    Hard disagree. Yacc has unnecessary footguns, in particular the fallout from using LALR(1), but more modern parser generators like bison provide LR(1) and IELR(1). Hand-rolled recursive descent parsers as well as parser combinators can easily obscure implicit resolution of grammar ambiguities. A good LR(1) parser generator enables a level of grammar consistency that is very difficult to achieve otherwise.
    • tgv 2y ago
      Same. LR(k) and LL(k) are readable and completely unambiguous, in contrast to PEG, where ambiguity is resolved ad hoc: PEG doesn't have a single definition, so implementations may differ, and the original PEG uses the order of the rules and backtracking to resolve ambiguity, which may lead to different resolutions in different contexts. Ambiguity does not leap out to the programmer. OTOH, an LL(1) grammar can be used to generate a top-down/recursive descent parser, and will always be correct.
    • thomasmg 2y ago
      > Hand-rolled recursive descent parsers as well as parser combinators can easily obscure implicit resolution of grammar ambiguities. Could you give a concrete, real-life example of this? I have written many recursive-descent parsers and never ran into this problem (Apache Jackrabbit Oak SQL and XPath parser, H2 database engine, PointBase Micro database engine, HypersonicSQL, NewSQL, Regex parsers, GraphQL parsers, and currently the Bau programming language). I have often heard that Bison / Yacc / ANTLR etc are "superior", but mostly from people that didn't actually have to write and maintain production-quality parsers. I do have experience with the above parser generators, eg. for university projects, and Apache Jackrabbit (2.x). I remember that in each case, the parser generators had some "limitations" that caused problems down the line. Then I had to spend more time trying to work around the parser generator limitations than actually doing productive work. This may sound harsh, but well that's my experience... I would love to hear from people that had a different experience for non-trivial projects...
      • tgv 2y ago
        The original comment says that using yacc/bison is "fundamentally misguided." But parser generators make it easy to add a correct parser to your project. It's obviously not the only way. Hand-rolling has a bunch of pitfalls, and easily leads to apparently correct behavior that does weird things on untested input. Your comment then is a bit like: I've never had memory corruption in C, so Rust/Java/etc. is for toy projects only.
        • thomasmg 2y ago
          > Hand-rolling has a bunch of pitfalls I'm arguing that this is not the case in reality, and asked for concrete examples... So again I ask for a concrete example... For memory corruption, there are plenty of examples. For parsing, I know one example that lead to problems. Interestingly, it was about using a state machine that was then modified (manually) and the result was broken. Here I argue that using a handwritten parser, instead of a state machine that is then manually modified, would not have resulted in this problem. Also, there was no randomized testing / fuzz testing, which is also a problem. This issue is still open: https://issues.apache.org/jira/browse/OAK-5367 https://issues.apache.org/jira/browse/OAK-5367
          • tgv 2y ago
            There's no reason for concrete examples, because the point was about the fundamental misguidedness of parser generators, not about problems with individual parser generators or the nice things you can do in a hand-rolled one, but to accommodate you, ANTLR gives one on its home page: "... At Twitter, we use it exclusively for query parsing in Twitter search... Samuel Luckenbill, Senior Manager of Search Infrastructure, Twitter, inc." Also, regexps are used very often in production, and that's definitely a parser-generator of sorts. The memory corruption example was an analog, but to spell it out: it's easier and faster to write a correct parser using flex/bison than by hand, especially for more complex languages. Parser-generators have their use, and are not fundamentally misguided. That you might want to write your own parser in some cases does not diminish that (nor vice versa).
      • masfuerte 2y ago
    • HelloNurse 2y ago
      A large portion of this consistency is not making executive decisions about parsing ambiguities. The difference between "the language is implicitly defined by what the parser does" and "the grammar for the language has been refined one failed test at a time" is large and practically important.
  • Levitating 2y ago
    And GNU is notorious for their use of yacc. Even gnulib functions like parse_datetime (primarily used to power the date command) rely on a yacc generated parser.
    • bonzini 2y ago
      That's mostly for historical reasons. Nobody felt the need to switch and do all the work needed to avoid breaking edge cases. GCC used to have Bison grammars but it switched to recursive descent about 20 years ago. The C++ grammar was especially horrible.
  • tannhaeuser 2y ago
    I think it would be interesting and adequate to hear about and link to the reflections of the original awk authors (Aho, Kernighan, Weinberg et al) considering they were also experts for yacc and other compiler-compiler tools from the 1977–1985 era and authors of the dragon book. After all, awk syntax was the starting point for JavaScript including warts such as regexp literals, optional semicolons, for (e in a), delete a[e], introducing the function keyword to a C-like language, etc. I recall at least Kernighan talked about optional semicolons as something he‘d reconsider given the chance.
• v3ss0n 2y ago
  Reading awk as a human is hard too. And performance of awk is crap. A lot slower than most interpreter language out there. I had replaced all the awk scripts in python and everything is a lot faster.
  • oguz-ismail 2y ago
    skill issue
    • creesch 2y ago
      Sure. I do not live in the terminal. But, I work with Linux enough to comfortably navigate around, read various shell scripts with relative ease. With the exception of awk. Which to me signals that, at least in my case, awk has a higher barrier for entry compared to most other things in the same environment. So with alternatives around I can more easily parse myself, I happily concede that I have a skill issue with awk.
    • watt 2y ago
      once there are more productive alternatives that require less specialized "skill", your condescending "skill issue" becomes a devex issue, and basically a productivity gap which will doom your language or tool.
    • DonHopkins 2y ago
      You just need to have the skill to overcome whatever non-technical, legacy, lack of education, or poor judgement issues that are steamrolling you into choosing to use awk instead of a sane rational decent modern efficient maintainable language.
      • dotancohen 2y ago
        Perl, then?
        • mst 2y ago
          The rule of thumb back at Netcraft was to prototype in awk/sed for brevity/expressiveness and then port to perl for production use for performance reasons. Been a couple decades since I was wrangling the survey systems there though, no idea what it looks like now.
• deleted 2y ago
  [deleted]
• teleforce 2y ago
  If you think AWK is hard to parse then try C++. The latter is so hard to parse thus very slow compile time that most probably inspired a funny programmer skit like this, one of the most popular XKCDs of all time [1]. Then come along fast compilation modern languages like Go and D. The latter is such a fresh air is that even though it's a complex language like C++ and Rust but it managed to compile very fast. Heck it even has RDMD facility that can perform compiled REPL as you interacting with the prompt similar to interpreted programming languages like Python and Matlab. According to its author, the main reason D has very fast compile time (as long as you avoid the CTFE) is because of the language design decisions avoid the notorious symbols that can complicated symbol table just like happened in C++ and the popular << and >> overloading for I/O and shifting. But the fact that Rust come much later than C++ and D but still slow to compile is bewildering to say the least. [1] Compiling: https://xkcd.com/303/ https://xkcd.com/303/
  • moomin 2y ago
    Pretty sure Rust's compile times are a function of the complex type system and generic instantiation. Everything's a trade-off.
    • dotancohen 2y ago
      Which are damn more important (to me) than is the compile time metric.
    • masklinn 2y ago
      Except in some rare edge cases, it’s mostly the latter, indirectly: in the average crate the vast majority of the time is spent in LLVM optimization passes and linking. Sometimes IR generation gets a pretty high score, but that’s somewhat inconsistent.
    • deleted 2y ago
      [deleted]
    • fnord77 2y ago
      IIRC, rust's long compile times are because it is basically doing static analysis, looking for potential errors
• ufo 2y ago
  Another tricky bit is deciding whether "/" is the division operator or the start of a regular expression. IIRC, awk does this in a context sensitive manner, by looking at the previous token.
• librasteve 2y ago
  just use raku
• mmsc 2y ago
  Awk is something that I think every programmer and especially every sysadmin should learn. 8 like the comparison at the end and have never heard of nnawk or bbawk before. I recently made a dashboard to compare four versions of awk output together, since not all awk scripts I'll run the same on each version: https://megamansec.github.io/awk-compare/ https://megamansec.github.io/awk-compare/ I'll have to add those:)
  • Chris2048 2y ago
    > every programmer and especially every sysadmin should learn There are lots of things "every <tech position> should learn", usually by people who already did so. I still have a bunch of AI/ML items on that list too. What's the advantage of learning AWK over Perl?
    • rlonstein 2y ago
      - Awk is defined in POSIX - Awk is on more systems than Perl - Awk has more implementations than Perl
      • chrsig 2y ago
        awk is also a much smaller language than perl, so it's generally less effort to teach, learn, and read.
        • Chris2048 2y ago
          Is it not possible to learn a subset of perl?
          • chrsig 2y ago
            Learning any language more or less starts with learning a subset of it. Asking a new hire to "learn awk" vs "learn perl" have two very different time investments attached to them. Tasking someone with "learning a subset of perl" begets the question "what subset?", and a very exhausting conversation with someone(s) routinely asking "so?" follows. After spending a large amount of time re-litigating which subsets of perl features we want that awk already supplies.
• jangliss 2y ago
  Surely it is AWKward?
• kazinator 2y ago
  If you are parsing awk, you must treat any ream of whitespace that contains a newline as a visible token, which you have to reference in various places in the grammar. Your implementation will likely benefit from a switch, in the lexical analyzer, which sometimes turns off the visible newline.
• benhoyt 2y ago
  Brian Kernighan sent Gawk maintainer Arnold Robbins an email linking to this blog post with the comment "Hindsight has a lot of benefits, it would appear." Peter Weinberger (quoted with permission) responded: > That's interesting, Here's some thoughts/recollections. (remember that human memory is fallible.) > 1. Using whitespace for string concatenation, in retrospect, was probably not the ideal choice (but '+' would not have worked). > 2. Syntax choices were in part driven by the desire for our local C programmers to find it familiar. > 3. As creatures of a specific time and place awk shared with C the (then endearing, now irritating) property of being underspecified. > I think that collectively we understood YACC reasonably well. We tortured the grammar until the parser came close to doing what we wanted, and then we stopped. The tools then were more primitive, but they did fit in 64K of memory. Al Aho also replied (quoted with permission): > Peter's observation about torturing the grammar is apt! As awk grew in its early years, the grammar evolved with it and I remember agonizing to make changes to the grammar to keep it under control (understanding and minimizing the number of yacc-generated parsing-action conflicts) as awk evolved. I found yacc's ability to point out parsing-action conflicts very helpful during awk's development. Good grammar design was very much an art in those days (maybe even today). It's fun to hear the perspectives of the original AWK creators. I've had some correspondence with Kernighan and Weinberger before, but I think that's the first time I've been on an email thread with all three of A, W, and K.
  • Affric 2y ago
    Thanks for posting this. I think it casts a pretty harsh light on criticisms of awk. Ultimately awk is one of the all time great languages. Small. Good at what it does. There’s something satisfying about using it which languages like Python just don’t give you. It’s a little bit of Unix wizardry.
  • 1vuio0pswjnm7 2y ago
    "The tools were more primitive, but they did fit in 64k of memory." I will take "primitive" over present-day bloat and complexity every time, quirks and all. That programs fitting in 64K of memory have remained in continuous use and the subject of imitation for so long must be a point of pride for the authors. From what I have seen, contemporary software authors are unlikely to ever achieve such longevity.
• mby 2y ago
  [flagged]