Parsing Awk Is Tricky • Hacker News Board

Re: Parsing Awk Is Tricky

#41

Post by HelloNurse » Mon, Sep 02, 2024, 1:14 PM UTC

jasone wrote: post #3

RodgerTheGreat wrote: post #2

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.

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.

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.

Re: Parsing Awk Is Tricky

#42

Post by chrsig » Mon, Sep 02, 2024, 1:21 PM UTC

rlonstein wrote: post #40

Chris2048 wrote: post #35

Earlier quoted context omitted.

> every programmer and especially every sysadmin should learn There are lots of things "every 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?

- Awk is defined in POSIX - Awk is on more systems than Perl - Awk has more implementations than Perl

awk is also a much smaller language than perl, so it's generally less effort to teach, learn, and read.

Re: Parsing Awk Is Tricky

#43

Post by masfuerte » Mon, Sep 02, 2024, 1:31 PM UTC

thomasmg wrote: post #10

jasone wrote: post #3

Earlier quoted context omitted.

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.

> 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, an…

If you start with an unambiguous grammar then you aren't going to introduce ambiguities by implementing it with a recursive descent parser.

If you are developing a new grammar it is quite easy to accidentally create ambiguities and a recursive descent parser won't highlight them. This becomes painful when you try to evolve the grammar.

Re: Parsing Awk Is Tricky

#44

Post by Snoddas » Mon, Sep 02, 2024, 1:36 PM UTC

Chris2048 wrote: post #35

mmsc wrote: post #32

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/ I'll have to add those:)

> every programmer and especially every sysadmin should learn There are lots of things "every 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?

Both will get you where you want to go, but I don't think the usecase for perl and awk are the same.

I reach for awk when my bash-scripts get a bit messy, perl is/was for when I want to build a small application (or nowdays python).

But both perl and python require cpan/pip to get the most out of and with awk, I just nead awk.

Re: Parsing Awk Is Tricky

#45

Post by jangliss » Mon, Sep 02, 2024, 1:53 PM UTC

Surely it is AWKward?

Re: Parsing Awk Is Tricky

#46

Post by scbrg » Mon, Sep 02, 2024, 2:05 PM UTC

forinti wrote: post #31

dotancohen wrote: post #21

Earlier quoted context omitted.

Perl, then?

As a dare from a friend I compared my Perl solution to an AWK solution: $time perl -MData::Dumper -ne '$n{length($_)}++; END {print Dumper(%n)}' bigfile.txt $VAR1 = '1088'; $VAR2 = 349647; real 0m1.326s user 0m0.814s sys 0m0.371s $time awk 'length($0) > max { max=length($0) } END { print max }' bigfile.txt 1087 real 0m21.400s user 0m18.596s sys 0m0.455s I prefer Perl, but I have no issue with AWK and I actually use i…

Well. I don't know. Those two programs don't really do the same thing. There's an awful lot of comparisons in the second one. After making the awk program more similar to the Perl program, and using mawk instead of gawk (which is quite a bit slower) the numbers look a bit different:

  $ seq 100000000 > /tmp/numbers 
  $ time perl -MData::Dumper -ne '$n{length($_)}++; END {print Dumper(%n)}'  /tmp/numbers 
  $VAR1 = '7';
  $VAR2 = 900000;
  $VAR3 = '8';
  $VAR4 = 9000000;
  $VAR5 = '5';
  $VAR6 = 9000;
  $VAR7 = '4';
  $VAR8 = 900;
  $VAR9 = '6';
  $VAR10 = 90000;
  $VAR11 = '10';
  $VAR12 = 1;
  $VAR13 = '2';
  $VAR14 = 9;
  $VAR15 = '3';
  $VAR16 = 90;
  $VAR17 = '9';
  $VAR18 = 90000000;
  
  real 0m16.483s
  user 0m16.071s
  sys 0m0.352s
  $ time mawk '{ lengths[length($0)]++ } END { max = 0; for(l in lengths) if (int(l) > max) max = int(l); print max; }' /tmp/numbers 
  9

  real 0m5.980s
  user 0m5.493s
  sys 0m0.457s

[edit]: Actually had a bug in the initial implementation. Of course.

Re: Parsing Awk Is Tricky

#47

Post by forinti » Mon, Sep 02, 2024, 2:13 PM UTC

scbrg wrote: post #46

forinti wrote: post #31

Earlier quoted context omitted.

As a dare from a friend I compared my Perl solution to an AWK solution: $time perl -MData::Dumper -ne '$n{length($_)}++; END {print Dumper(%n)}' bigfile.txt $VAR1 = '1088'; $VAR2 = 349647; real 0m1.326s user 0m0.814s sys 0m0.371s $time awk 'length($0) > max { max=length($0) } END { print max }' bigfile.txt 1087 real 0m21.400s user 0m18.596s sys 0m0.455s I prefer Perl, but I have no issue with AWK and I actually use i…

Well. I don't know. Those two programs don't really do the same thing. There's an awful lot of comparisons in the second one. After making the awk program more similar to the Perl program, and using mawk instead of gawk (which is quite a bit slower) the numbers look a bit different: $ seq 100000000 > /tmp/numbers $ time perl -MData::Dumper -ne '$n{length($_)}++; END {print Dumper(%n)}' /tmp/numbers $VAR1 = '7'; $VAR2…

I used them both to find the longest line in a file. The Perl option just spits out the number of times each line length occurs. It will get messy if you have many different line lengths (which was not my case).

You also have to take into account that awk does not count the line terminator.

Let's try the opposite: make the Perl script more like the AWK one.

  $ time perl -ne 'if(length($_)>$n) {$n=length($_)}; END {print $n}'  rockyou.txt 
  286

  real 0m2,569s
  user 0m2,506s
  sys 0m0,056s

  $ time awk 'length($0) > max { max=length($0) } END { print max }' rockyou.txt 
  285

  real 0m3,768s
  user 0m3,714s
  sys 0m0,048s

Re: Parsing Awk Is Tricky

#48

Post by orwin » Mon, Sep 02, 2024, 2:40 PM UTC

kragen wrote: post #38

orwin wrote: post #37

Earlier quoted context omitted.

> of course you can make compiling c++ arbitrarily slow with templates This might be my problem :/ (template are the closest to metaprogramming I can find outside of Lisps) Tbf I was mostly comparing my experience with Rust, SBCL and C++, to me it was a given that C was an order of magnitude faster (3 order of magnitude seems a bit much). I found opt-level=1 quite early and managed to feel way better about rust and l…

yeah! you can get an enormous amount of metaprogramming mileage out of c++ templates. i think the pattern-matching paradigm embodied by sfinae is maybe a better fit for, effectively, user-defined language extensions, than the more straightforward imperative approach lisp uses by default. but c++ templates are unnecessarily hard to debug i think, for reasons that aren't inherent to the pattern-matching paradigm i didn…

Honestly, it was a school project, i had time and my final internship was month away, so i took the time to do it. Barely finished in time and it was quite lousy, but i was proud of it. It was my peak "Dunning-Kruger", because i was probably the most mathematically-inclined of all my classmates, and thought i was really clever.

Funny stuff, during my final internship i made a heavy use of scikit-image, learned about openBlas and unterstood how much better low-level libraries were for matrix computation, and how far away my own library was. And at my next job i was setting up our PaaS VMs with a lot of stuff, including TitanX with Cuda and pytorch, informed myself on the tools i was installing (i did set up tutorials in notebooks for an easy launch), and then understood i was years behind and way less informed than i thought i was. I think i learned about HN around that time.

Re: Parsing Awk Is Tricky

#49

Post by fnord77 » Mon, Sep 02, 2024, 3:10 PM UTC

moomin wrote: post #18

teleforce wrote: post #16

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…

Pretty sure Rust's compile times are a function of the complex type system and generic instantiation. Everything's a trade-off.

IIRC, rust's long compile times are because it is basically doing static analysis, looking for potential errors

Re: Parsing Awk Is Tricky

#50

Post by pornel » Mon, Sep 02, 2024, 3:31 PM UTC

moomin wrote: post #18

teleforce wrote: post #16

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…

Pretty sure Rust's compile times are a function of the complex type system and generic instantiation. Everything's a trade-off.

`cargo check` that does all the parsing, type system checks, and lifetime analysis is pretty fast compared to builds.

Rust compilation time spends most time in LLVM, due to verbosity of the IR it outputs, and during linking, due to absurd amount of debug info and objects to link.

When cargo check isn't fast, it's usually due to build scripts and procedural macros, which are slow due to being compiled binaries, so LLVM, linking, and running of an unoptimized ton of code blocks type checking.