5 ms·

Irregular Expressions

73 points by signa11 4y ago

andrewfromx 4y ago
GPT has completely changed my use and feeling about regex. I used to hate them, would rather write the logic myself in a language I understand. But now I just ask GPT for the regex I need and voila!
- tomashubelbauer 4y ago
  That's interesting. I personally like regexes very much but I'm slow to create them so I figured I'd ask ChatGPT a few times and just double check its work and it got them all wrong.
  - sroussey 4y ago
    Got them wrong for me as well. :/ I could point out the flaw and it would fix it, but introduce another. However, I got enough out of it to rewrite it myself.
  - leobg 4y ago
    I recently asked it to produce a regex for me, and it responded that as a large language model, it wasn’t allowed to produce hate speech… Not making this up.
- zabzonk 4y ago
  and next you will be asking gpt "how do i do multiplication"?
  - MathMonkeyMan 4y ago
    There will be no need to ask.
  - pests 4y ago
    Didn't people say this about calculators too probably?
    - zabzonk 4y ago
      they did, and they were right
- 8uhaal 4y ago
  Writing regexes is one of the most fun things that sometimes pop up at work. A little puzzle. Well-defined, clear that there must be a solution, somewhat easily checkable .. the easiest kind of task. I enjoy this just as much as some people enjoy crosswords or sudoku. Nobody would ask chatgpt to solve a sudoku for them (It would get them all wrong anyway.) No way I'm gonna let GPT take this away from me.
  - andrewfromx 4y ago
    "No way I'm gonna let GPT take this away from me" surely you can see a photoshop expert from years ago saying this about pixel blurring?
    - meindnoch 4y ago
      What is "pixel blurring"?
- chrismorgan 4y ago
  Every regular expression I’ve seen produced by a large language model has either being broken, or done an unacceptably bad job due to being the wrong tool for the job (e.g. validating an email address with a fairly short regular expression, which I’ve seen people share the answers of at least three times).
- Turing_Machine 4y ago
  The regex GPT gave me the other day was pure shite. However, that was only a small part of the job, so GPT was still a big win overall.
chubot 4y ago
The animated diagrams are cool! Does anyone know how they're made?
- leetrout 4y ago
  Glad you said this because they do not work in mobile safari. All I saw was empty ovals
  - KerrAvon 4y ago
    Also broken in Desktop Safari.
- tavianator 4y ago
  I wrote the SVGs by hand
  - tester457 4y ago
    They're beautifully animated. How did you know that your article was posted? Do you have a program to alert you of mentions?
    - tavianator 4y ago
      Nope, a friend of mine messaged me that I was on the front page of HN! I'm busy with family for Easter so I can't reply to everything I want to, but I'll come back later
martyalain 4y ago
Cool. Could your irregular expressions take something interesting from the Johnathan's snippet recalled in this wiki page http://lambdaway.free.fr/lambdawalks/?view=levithan http://lambdaway.free.fr/lambdawalks/?view=levithan ?
metadat 4y ago
Great writeup, clear and easy to follow. For readers unfamiliar with nom, it would be even more helpful if the author included reference links, because I was immediately confused about the sudden appearance of the "alt(..)" function scene, seemingly materialized out of thin air (presumably imports omitted for brevity). https://docs.rs/nom/latest/nom/branch/fn.alt.html https://docs.rs/nom/latest/nom/branch/fn.alt.html
- jmholla 4y ago
  What's with the 21 parsers limit?
  - School-Cotton 4y ago
    It's currently not possible to write a Rust function that's generic over a tuple with arbitrarily many entries, so they had to implement a trait by hand for tuple sizes up to 21 (presumably that limit was chosen arbitrarily).
    - metadat 4y ago
      Does Rust have a template or macro system that would facilitate generating up to e.g. 221 instead? If I'm understanding correctly, some Regex features may require implementing more than 21 rules for a thorough and complete implementation.
      - jcparkyn 4y ago
        The workaround is just to nest multiple `alt`s inside each other.
      - iudqnolq 4y ago
        Yes, rust declarative macros shine at exactly this kind of problem. And nom does use this to generate the implementation. But for some reason it's customary in rust to stick to a lower number of autogenerated implementations. My first guess would be it might be a compile time issue? https://docs.rs/nom/latest/src/nom/branch/mod.rs.html#245 https://docs.rs/nom/latest/src/nom/branch/mod.rs.html#245
zokier 4y ago
There is also unrelated Scheme(/Racket) library called IrRegular Expressions/irregex: https://synthcode.com/scheme/irregex https://synthcode.com/scheme/irregex It is notable for supporting lispy "SRE" syntax in addition to traditional PCRE syntax, standardized as SRFI 115: https://srfi.schemers.org/srfi-115/srfi-115.html https://srfi.schemers.org/srfi-115/srfi-115.html
8uhaal 4y ago
Anybody knows what the problem with negation is? Can't you just swap accepting with non-accepting states? The result should accept exactly the complement, no? Since we're not talking about Büchi automata here.
- deleted 4y ago
  [deleted]
- mcyc 4y ago
  It's because this produces NFAs not DFAs (due to the epsilon arcs), and so negation can't be done by just flipping the final states. Take, for example, the regex "a|(aa)+" (the set of even length strings of "a"'s or just one "a"). If you use the construction from the article, you get an NFA with basically two arms: one that recognizes "a" and one that recognizes "(aa)+". The initial state contains an epsilon arc to the start state of each of these arms. If you just flip the final/non-final states in each arm, the resulting language contains "a", since we are no longer accepting each even length "a" string, but now each odd length "a" string, of which "a" is a member. Thus the new language is not the proper complement of "a|(aa)+", which would not contain "a".
  - zeroimpl 4y ago
    That example doesn’t really fit since one easily could compute the negation of “a|(aa)+” in linear time by simply returning the opposite of the top-level node in the tree. Perhaps something like “X|!Y” or similar might be impossible?
    - mcyc 4y ago
      The parent comment asked specifically about negating the finality of each state, which I addressed. As for how to actually implement complement in a regex engine, there are certainly some strategies like the one you mentioned that could be used (but the point of my comment was that just swapping final/non-final states is not a valid one).
      - 4y ago
ridiculous_fish 4y ago
Often you want to capture something, not just check if a match exists. But the theory of capture groups in DFAs is relatively obscure - for example tagged DFAs in the Laurikari paper, which is a difficult read. Does anyone know of an accessible writeup of these techniques? Interestingly neither re2 nor Rust regex perform capturing in DFAs. Rather, a DFA is used to locate the end of a match, the DFA is used again to determine the beginning of the match, and then an NDFA is used to match a third time, to extract the capture groups.
- burntsushi 4y ago
  The "Papers" section on re2c's web site continues Laurikari's work: http://re2c.org/ http://re2c.org/ ... but I haven't found them particularly accessible. And it's not clear it's a viable strategy in a general purpose regex engine. Namely, I'm not sure how much bigger it makes the DFA. Also, AFAIK, these aren't DFAs. They are different theoretical structures with explicitly more power. > and then an NDFA is used to match a third time, to extract the capture groups. That's the PikeVM. It's an NFA simulation. Although it uses additional storage and is otherwise more computationally powerful than just a plain NFA.
  - ridiculous_fish 4y ago
    Thanks! I hadn't encountered that top paper "A closer look at TDFA." That paper claims to be "the first practical submatch extraction and parsing algorithm based on DFA" and it came out only last year! It shows how new this theory is.
- yarg 4y ago
  I don't know about sound theory, but pulling something out of bullshit: Firstly, the nice part about DFAs is that they're really simple to implement - in terms of capture groups bare in mind that the generation mechanism means that the nodes are probably super-positions, and the extracts across aspects of your language can intersect if you're not careful. You can get into messy places really quickly - so I'd suggest not fucking with the machine directly. However, there's one thing that you can do without compromising machine generation: add a processing mode that returns the trace of machine states for the matching string. And then process that state trace. Now bare in mind that some of the states that you went through might have been super-positions, so you don't quite know what they are. But (now that you have a match) you can run the reverse of the match through the reverse of the network and intersect the reverse of its trace. (I haven't actually done that, but it will clean up some trace ambiguity - where earlier branches were only later found not to have been taken.)

73 points by signa11 4y ago

GPT has completely changed my use and feeling about regex. I used to hate them, would rather write the logic myself in a language I understand. But now I just ask GPT for the regex I need and voila!

tomashubelbauer 4y ago
That's interesting. I personally like regexes very much but I'm slow to create them so I figured I'd ask ChatGPT a few times and just double check its work and it got them all wrong.
- sroussey 4y ago
  Got them wrong for me as well. :/ I could point out the flaw and it would fix it, but introduce another. However, I got enough out of it to rewrite it myself.
- leobg 4y ago
  I recently asked it to produce a regex for me, and it responded that as a large language model, it wasn’t allowed to produce hate speech… Not making this up.
zabzonk 4y ago
and next you will be asking gpt "how do i do multiplication"?
- MathMonkeyMan 4y ago
  There will be no need to ask.
- pests 4y ago
  Didn't people say this about calculators too probably?
  - zabzonk 4y ago
    they did, and they were right
8uhaal 4y ago
Writing regexes is one of the most fun things that sometimes pop up at work. A little puzzle. Well-defined, clear that there must be a solution, somewhat easily checkable .. the easiest kind of task. I enjoy this just as much as some people enjoy crosswords or sudoku. Nobody would ask chatgpt to solve a sudoku for them (It would get them all wrong anyway.) No way I'm gonna let GPT take this away from me.
- andrewfromx 4y ago
  "No way I'm gonna let GPT take this away from me" surely you can see a photoshop expert from years ago saying this about pixel blurring?
  - meindnoch 4y ago
    What is "pixel blurring"?
chrismorgan 4y ago
Every regular expression I’ve seen produced by a large language model has either being broken, or done an unacceptably bad job due to being the wrong tool for the job (e.g. validating an email address with a fairly short regular expression, which I’ve seen people share the answers of at least three times).
Turing_Machine 4y ago
The regex GPT gave me the other day was pure shite. However, that was only a small part of the job, so GPT was still a big win overall.

chubot 4y ago

The animated diagrams are cool! Does anyone know how they're made?

leetrout 4y ago
Glad you said this because they do not work in mobile safari. All I saw was empty ovals
- KerrAvon 4y ago
  Also broken in Desktop Safari.
tavianator 4y ago
I wrote the SVGs by hand
- tester457 4y ago
  They're beautifully animated. How did you know that your article was posted? Do you have a program to alert you of mentions?
  - tavianator 4y ago
    Nope, a friend of mine messaged me that I was on the front page of HN! I'm busy with family for Easter so I can't reply to everything I want to, but I'll come back later

martyalain 4y ago

Cool. Could your irregular expressions take something interesting from the Johnathan's snippet recalled in this wiki page http://lambdaway.free.fr/lambdawalks/?view=levithan http://lambdaway.free.fr/lambdawalks/?view=levithan ?

metadat 4y ago

Great writeup, clear and easy to follow. For readers unfamiliar with nom, it would be even more helpful if the author included reference links, because I was immediately confused about the sudden appearance of the "alt(..)" function scene, seemingly materialized out of thin air (presumably imports omitted for brevity). https://docs.rs/nom/latest/nom/branch/fn.alt.html https://docs.rs/nom/latest/nom/branch/fn.alt.html

jmholla 4y ago
What's with the 21 parsers limit?
- School-Cotton 4y ago
  It's currently not possible to write a Rust function that's generic over a tuple with arbitrarily many entries, so they had to implement a trait by hand for tuple sizes up to 21 (presumably that limit was chosen arbitrarily).
  - metadat 4y ago
    Does Rust have a template or macro system that would facilitate generating up to e.g. 221 instead? If I'm understanding correctly, some Regex features may require implementing more than 21 rules for a thorough and complete implementation.
    - jcparkyn 4y ago
      The workaround is just to nest multiple `alt`s inside each other.
    - iudqnolq 4y ago
      Yes, rust declarative macros shine at exactly this kind of problem. And nom does use this to generate the implementation. But for some reason it's customary in rust to stick to a lower number of autogenerated implementations. My first guess would be it might be a compile time issue? https://docs.rs/nom/latest/src/nom/branch/mod.rs.html#245 https://docs.rs/nom/latest/src/nom/branch/mod.rs.html#245

zokier 4y ago

There is also unrelated Scheme(/Racket) library called IrRegular Expressions/irregex: https://synthcode.com/scheme/irregex https://synthcode.com/scheme/irregex It is notable for supporting lispy "SRE" syntax in addition to traditional PCRE syntax, standardized as SRFI 115: https://srfi.schemers.org/srfi-115/srfi-115.html https://srfi.schemers.org/srfi-115/srfi-115.html

8uhaal 4y ago

Anybody knows what the problem with negation is? Can't you just swap accepting with non-accepting states? The result should accept exactly the complement, no? Since we're not talking about Büchi automata here.

deleted 4y ago
[deleted]
mcyc 4y ago
It's because this produces NFAs not DFAs (due to the epsilon arcs), and so negation can't be done by just flipping the final states. Take, for example, the regex "a|(aa)+" (the set of even length strings of "a"'s or just one "a"). If you use the construction from the article, you get an NFA with basically two arms: one that recognizes "a" and one that recognizes "(aa)+". The initial state contains an epsilon arc to the start state of each of these arms. If you just flip the final/non-final states in each arm, the resulting language contains "a", since we are no longer accepting each even length "a" string, but now each odd length "a" string, of which "a" is a member. Thus the new language is not the proper complement of "a|(aa)+", which would not contain "a".
- zeroimpl 4y ago
  That example doesn’t really fit since one easily could compute the negation of “a|(aa)+” in linear time by simply returning the opposite of the top-level node in the tree. Perhaps something like “X|!Y” or similar might be impossible?
  - mcyc 4y ago
    The parent comment asked specifically about negating the finality of each state, which I addressed. As for how to actually implement complement in a regex engine, there are certainly some strategies like the one you mentioned that could be used (but the point of my comment was that just swapping final/non-final states is not a valid one).
    - 4y ago

ridiculous_fish 4y ago

Often you want to capture something, not just check if a match exists. But the theory of capture groups in DFAs is relatively obscure - for example tagged DFAs in the Laurikari paper, which is a difficult read. Does anyone know of an accessible writeup of these techniques? Interestingly neither re2 nor Rust regex perform capturing in DFAs. Rather, a DFA is used to locate the end of a match, the DFA is used again to determine the beginning of the match, and then an NDFA is used to match a third time, to extract the capture groups.

burntsushi 4y ago
The "Papers" section on re2c's web site continues Laurikari's work: http://re2c.org/ http://re2c.org/ ... but I haven't found them particularly accessible. And it's not clear it's a viable strategy in a general purpose regex engine. Namely, I'm not sure how much bigger it makes the DFA. Also, AFAIK, these aren't DFAs. They are different theoretical structures with explicitly more power. > and then an NDFA is used to match a third time, to extract the capture groups. That's the PikeVM. It's an NFA simulation. Although it uses additional storage and is otherwise more computationally powerful than just a plain NFA.
- ridiculous_fish 4y ago
  Thanks! I hadn't encountered that top paper "A closer look at TDFA." That paper claims to be "the first practical submatch extraction and parsing algorithm based on DFA" and it came out only last year! It shows how new this theory is.
yarg 4y ago
I don't know about sound theory, but pulling something out of bullshit: Firstly, the nice part about DFAs is that they're really simple to implement - in terms of capture groups bare in mind that the generation mechanism means that the nodes are probably super-positions, and the extracts across aspects of your language can intersect if you're not careful. You can get into messy places really quickly - so I'd suggest not fucking with the machine directly. However, there's one thing that you can do without compromising machine generation: add a processing mode that returns the trace of machine states for the matching string. And then process that state trace. Now bare in mind that some of the states that you went through might have been super-positions, so you don't quite know what they are. But (now that you have a match) you can run the reverse of the match through the reverse of the network and intersect the reverse of its trace. (I haven't actually done that, but it will clean up some trace ambiguity - where earlier branches were only later found not to have been taken.)