5 ms·

The lex and yacc utilities are part of POSIX.2; is there any reason not to reach for them first? https://pubs.opengroup.org/onlinepubs/9699919799/utilities/lex

by chasil 2y ago

The lex and yacc utilities are part of POSIX.2; is there any reason not to reach for them first? https://pubs.opengroup.org/onlinepubs/9699919799/utilities/lex.html https://pubs.opengroup.org/onlinepubs/9699919799/utilities/l... https://pubs.opengroup.org/onlinepubs/9699919799/utilities/yacc.html https://pubs.opengroup.org/onlinepubs/9699919799/utilities/y... All the POSIX.2 standards for shell utilities can be found here: https://pubs.opengroup.org/onlinepubs/9699919799/utilities/ https://pubs.opengroup.org/onlinepubs/9699919799/utilities/ The original introduction to lex and yacc was in the book by Kernigan and Pike: https://scis.uohyd.ac.in/~apcs/itw/UNIXProgrammingEnvironment.pdf https://scis.uohyd.ac.in/~apcs/itw/UNIXProgrammingEnvironmen...

gavinhoward 2y ago
As the author of a POSIX standard utility, I would advise you to only reach for such utilities when portability is the most important thing. POSIX utilities are not great. Lex and Yacc included.
- chasil 2y ago
  Is your criticism of the relationship of the lexer and the parser, or something more fundamental? Is an LR parser expressed in BNF notation unsatisfactory? I say this only as it has been many years since I have written one, but I thought this OCaml presentation on a POSIX shell held the structure in high regard. https://archive.fosdem.org/2018/schedule/event/code_parsing_posix_s_hell/ https://archive.fosdem.org/2018/schedule/event/code_parsing_...
  - gavinhoward 2y ago
    The UX of the BNF notation. I am partial to hand-coded recursive descent purely because I struggled with Lex and Yacc too much when I tried.
    - chasil 2y ago
      I commiserate, it can be unforgiving, and the use of C is admittedly out of vogue.
      - gavinhoward 2y ago
        Oh, I love C. [1] But yes, unforgiving. And a lot of magic, with special variables, macros, and functions that you must know. And unclear scoping. [1]: https://gavinhoward.com/2023/02/why-i-use-c-when-i-believe-in-memory-safety/ https://gavinhoward.com/2023/02/why-i-use-c-when-i-believe-i...
        kelnos 2y ago
        OT, but: I remember reading that post of yours a year or so ago! It was so bizarre to me, but also really fun. I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it. (I am still less than thrilled that I have to rely on OpenSSL, regardless of the process improvements its developer team has made in more recent years.) I still (unfortunately, IMO) write a lot of C. Back in 2004 I thought it was great fun. But now that I've worked in safer, batteries-included languages, I find C to be a huge drag. I'm so much more productive in Rust or even Java. I could never ever ever ever approach the level of rigor you bring to your C code; I just don't find doing all that stuff to be fun or interesting... to the contrary, it feels like a huge drag: if I were "required" to do all that, I just wouldn't write any code at all in C in the first place, knowing that having to do all the testing and fuzzing and static analysis stuff would burn me out. Anyhow, I hope I don't sound like I'm being critical... quite the opposite. I just think we live in a magnificent world where people's brains can work so so so differently when it comes to the same topic.
        gavinhoward 2y ago
        No offense taken; I know my brain is different. :) > I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it. This is probably the most complimentary thing anyone has ever said to me. Thank you! I hope I can live up to that.
- nicoburns 2y ago
  Are POSIX utilities even portable? They tend to have poor windows support. And they also tend to target C, which has a high ceiling for portability, but also a high bar for making things portable (whereas more modern languages are often just portable by default). My take on POSIX utilities would be only to use them on Linux platforms where they effectively form a "native" part of the platform.
  - gavinhoward 2y ago
    I was mostly speaking about POSIX, since that was the focus of GGP. Yes, you should only use them on POSIX. My utility does build natively on Windows, though.
  - chasil 2y ago
    The NT kernel was created with a POSIX layer (along with os/2). https://en.m.wikipedia.org/wiki/Microsoft_POSIX_subsystem https://en.m.wikipedia.org/wiki/Microsoft_POSIX_subsystem Microsoft had previously been the largest AT&T UNIX licensee with Xenix sales on the TRS-80 model 2, so they were familiar with the need.
  - kelnos 2y ago
    > They tend to have poor windows support Does Windows claim POSIX compatibility these days? I didn't think so? I remember NT's old POSIX subsystem, but is that even a thing anymore? > My take on POSIX utilities would be only to use them on Linux platforms I mean, only use them on POSIX-compliant systems. Linux is just one of them. At the risk of sounding childishly derisive, when someone is talking about "portability", I think they're generally not bothering to include Windows in the mix, as Windows doesn't really share all that much of a common denominator with much else.
- rnart 2y ago
  I disagree here. The syntax can be infuriating at first, but once you understand it, Lex/Yacc are rock solid and speed up development significantly.
pdpi 2y ago
For a few reasons. One, because actually building the lexer and parser from scratch is a useful exercise in a learning context, which is what this is. Two, because the book wants to teach Pratt parsers, rather than LALR parsers. There’s a lot of literature out there on LALR parsers and generated parsers in general, but precious little on handrolled parsers. Covering material that hasn’t been covered to hell and back is a Good Thing. Three, because lex and yacc generate C, and the book has two implementations of the interpreter, in C and Java. You could’ve used ANTLR to generate both parsers, but lex/yacc would only cater to the C version And finally, because not everybody is on a POSIX system. Before WSL, using anything Unix-y on Windows was miserable. These days it’s mostly fine, but using WSL means you’re not actually building windows-native stuff anymore.
jahewson 2y ago
Parser generators create more problems than they solve.
runevault 2y ago
Does a single production compiler use lex and yacc to generate any part of their system, beyond maybe a first pass to test out syntax before it gets rewritten into a hand written parser/lexer? I'm not going to say none exist since I don't know literally every production compiler ever written, but I have never heard of one that used them for the final code.
- pansa2 2y ago
  I think Ruby does? IIRC its source code includes a 10,000+ line “parse.y” file which is converted to C code using Yacc.
  - runevault 2y ago
    Interesting, I'll have to look into this because I'd never heard that before and now I'm curious. A language with as much going on as Ruby was not one I would have picked as a candidate for yacc
  - runevault 2y ago
    Just went and looked in the github repo. 16,000+ line .y file. I can't imagine that is pleasant to maintain.
  - thomascountz 2y ago
    Excitingly, Ruby 3.3+ shipped with a new alternative parser called Prism[0]! See also: [1][2]. [0]: https://github.com/ruby/prism https://github.com/ruby/prism [1]: https://railsatscale.com/2023-06-12-rewriting-the-ruby-parser/ https://railsatscale.com/2023-06-12-rewriting-the-ruby-parse... [2]: https://railsatscale.com/2024-04-16-prism-in-2024/ https://railsatscale.com/2024-04-16-prism-in-2024/
- rnart 2y ago
  Yes, OCaml with its very complex syntax and hundreds of features uses the OCaml equivalents of Lex/Yacc. It is a myth that one cannot use Lex/Yacc in production.
- ufo 2y ago
1f60c 2y ago
Bob addresses this in the introduction^: > We will abstain from using [parser generators] here. I want to ensure there are no dark corners where magic and confusion can hide, so we’ll write everything by hand. As you’ll see, it’s not as bad as it sounds, and it means you really will understand each line of code and how both interpreters work. ^ https://craftinginterpreters.com/introduction.html#the-code https://craftinginterpreters.com/introduction.html#the-code
fmbb 2y ago
Is there any reason to reach for them first?
cdcarter 2y ago
The Unix Programming Environment tutorial for building hoc doesn’t even come close to what Nystrom gets into in Crafting Interpreters. Hoc is a very fun little language, but as Nystrom describes several times in the book…parsing just isn’t the interesting part of the game.

by chasil 2y ago

gavinhoward 2y ago

As the author of a POSIX standard utility, I would advise you to only reach for such utilities when portability is the most important thing. POSIX utilities are not great. Lex and Yacc included.

chasil 2y ago
Is your criticism of the relationship of the lexer and the parser, or something more fundamental? Is an LR parser expressed in BNF notation unsatisfactory? I say this only as it has been many years since I have written one, but I thought this OCaml presentation on a POSIX shell held the structure in high regard. https://archive.fosdem.org/2018/schedule/event/code_parsing_posix_s_hell/ https://archive.fosdem.org/2018/schedule/event/code_parsing_...
- gavinhoward 2y ago
  The UX of the BNF notation. I am partial to hand-coded recursive descent purely because I struggled with Lex and Yacc too much when I tried.
  - chasil 2y ago
    I commiserate, it can be unforgiving, and the use of C is admittedly out of vogue.
    - gavinhoward 2y ago
      Oh, I love C. [1] But yes, unforgiving. And a lot of magic, with special variables, macros, and functions that you must know. And unclear scoping. [1]: https://gavinhoward.com/2023/02/why-i-use-c-when-i-believe-in-memory-safety/ https://gavinhoward.com/2023/02/why-i-use-c-when-i-believe-i...
      - kelnos 2y ago
        OT, but: I remember reading that post of yours a year or so ago! It was so bizarre to me, but also really fun. I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it. (I am still less than thrilled that I have to rely on OpenSSL, regardless of the process improvements its developer team has made in more recent years.) I still (unfortunately, IMO) write a lot of C. Back in 2004 I thought it was great fun. But now that I've worked in safer, batteries-included languages, I find C to be a huge drag. I'm so much more productive in Rust or even Java. I could never ever ever ever approach the level of rigor you bring to your C code; I just don't find doing all that stuff to be fun or interesting... to the contrary, it feels like a huge drag: if I were "required" to do all that, I just wouldn't write any code at all in C in the first place, knowing that having to do all the testing and fuzzing and static analysis stuff would burn me out. Anyhow, I hope I don't sound like I'm being critical... quite the opposite. I just think we live in a magnificent world where people's brains can work so so so differently when it comes to the same topic.
        gavinhoward 2y ago
        No offense taken; I know my brain is different. :) > I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it. This is probably the most complimentary thing anyone has ever said to me. Thank you! I hope I can live up to that.
nicoburns 2y ago
Are POSIX utilities even portable? They tend to have poor windows support. And they also tend to target C, which has a high ceiling for portability, but also a high bar for making things portable (whereas more modern languages are often just portable by default). My take on POSIX utilities would be only to use them on Linux platforms where they effectively form a "native" part of the platform.
- gavinhoward 2y ago
  I was mostly speaking about POSIX, since that was the focus of GGP. Yes, you should only use them on POSIX. My utility does build natively on Windows, though.
- chasil 2y ago
  The NT kernel was created with a POSIX layer (along with os/2). https://en.m.wikipedia.org/wiki/Microsoft_POSIX_subsystem https://en.m.wikipedia.org/wiki/Microsoft_POSIX_subsystem Microsoft had previously been the largest AT&T UNIX licensee with Xenix sales on the TRS-80 model 2, so they were familiar with the need.
- kelnos 2y ago
  > They tend to have poor windows support Does Windows claim POSIX compatibility these days? I didn't think so? I remember NT's old POSIX subsystem, but is that even a thing anymore? > My take on POSIX utilities would be only to use them on Linux platforms I mean, only use them on POSIX-compliant systems. Linux is just one of them. At the risk of sounding childishly derisive, when someone is talking about "portability", I think they're generally not bothering to include Windows in the mix, as Windows doesn't really share all that much of a common denominator with much else.
rnart 2y ago
I disagree here. The syntax can be infuriating at first, but once you understand it, Lex/Yacc are rock solid and speed up development significantly.

pdpi 2y ago

For a few reasons. One, because actually building the lexer and parser from scratch is a useful exercise in a learning context, which is what this is. Two, because the book wants to teach Pratt parsers, rather than LALR parsers. There’s a lot of literature out there on LALR parsers and generated parsers in general, but precious little on handrolled parsers. Covering material that hasn’t been covered to hell and back is a Good Thing. Three, because lex and yacc generate C, and the book has two implementations of the interpreter, in C and Java. You could’ve used ANTLR to generate both parsers, but lex/yacc would only cater to the C version And finally, because not everybody is on a POSIX system. Before WSL, using anything Unix-y on Windows was miserable. These days it’s mostly fine, but using WSL means you’re not actually building windows-native stuff anymore.

jahewson 2y ago

Parser generators create more problems than they solve.

runevault 2y ago

Does a single production compiler use lex and yacc to generate any part of their system, beyond maybe a first pass to test out syntax before it gets rewritten into a hand written parser/lexer? I'm not going to say none exist since I don't know literally every production compiler ever written, but I have never heard of one that used them for the final code.

pansa2 2y ago
I think Ruby does? IIRC its source code includes a 10,000+ line “parse.y” file which is converted to C code using Yacc.
- runevault 2y ago
  Interesting, I'll have to look into this because I'd never heard that before and now I'm curious. A language with as much going on as Ruby was not one I would have picked as a candidate for yacc
- runevault 2y ago
  Just went and looked in the github repo. 16,000+ line .y file. I can't imagine that is pleasant to maintain.
- thomascountz 2y ago
  Excitingly, Ruby 3.3+ shipped with a new alternative parser called Prism[0]! See also: [1][2]. [0]: https://github.com/ruby/prism https://github.com/ruby/prism [1]: https://railsatscale.com/2023-06-12-rewriting-the-ruby-parser/ https://railsatscale.com/2023-06-12-rewriting-the-ruby-parse... [2]: https://railsatscale.com/2024-04-16-prism-in-2024/ https://railsatscale.com/2024-04-16-prism-in-2024/
rnart 2y ago
Yes, OCaml with its very complex syntax and hundreds of features uses the OCaml equivalents of Lex/Yacc. It is a myth that one cannot use Lex/Yacc in production.
ufo 2y ago

1f60c 2y ago

Bob addresses this in the introduction^: > We will abstain from using [parser generators] here. I want to ensure there are no dark corners where magic and confusion can hide, so we’ll write everything by hand. As you’ll see, it’s not as bad as it sounds, and it means you really will understand each line of code and how both interpreters work. ^ https://craftinginterpreters.com/introduction.html#the-code https://craftinginterpreters.com/introduction.html#the-code

fmbb 2y ago

Is there any reason to reach for them first?

cdcarter 2y ago

The Unix Programming Environment tutorial for building hoc doesn’t even come close to what Nystrom gets into in Crafting Interpreters. Hoc is a very fun little language, but as Nystrom describes several times in the book…parsing just isn’t the interesting part of the game.