6 ms·

What I don't get is that the example given: hello\\s+w.+d$ Is 100% perl compatible, seems more like "subset" than "incompatible". I've seen comments that

by rnovak 11y ago

What I don't get is that the example given: hello\\s+w.+d$ Is 100% perl compatible, seems more like "subset" than "incompatible". I've seen comments that say it's a "joke". Can any confirm that the title was indeed a joke? Edit: I know both what a DFA/NFA are, and how they relate to formal language theory and regular languages, the question still stands how a subset can be called "incompatible"

brudgers 11y ago
Perl's regex engine is uses a non-deterministic finite automata [NFA]. Because the Readme indicates each character is only examined once and that PIRE lacks backtracking, look ahead and capture groups, it's engine is almost certainly DFA [deterministic finite automata] based. Thus among the syntax it is likely to choke on or ignore are anything involving curly braces {}. Keep in mind that "regular expressions" can denote a notation for describing finite automata and that this is subtly different from the programming language implementation of regex engines in languages like Perl.
- js2 11y ago
  See https://swtch.com/%7Ersc/regexp/regexp1.html https://swtch.com/%7Ersc/regexp/regexp1.html for a fine explanation of DFA vs NFA.
- rnovak 11y ago
  Again, that's leaves it as a subset of Perls regular-expressions, not a disjoint/distinct set, which is what incompatibility would imply.
  - brudgers 11y ago
    Since regular expressions evaluate to values [that's what makes them expressions], type theory is perhaps a better abstraction than set theory. In particular, since regular expressions accept an input and produce an output, it May be particularly useful to think of them as function types. If PIRE is an ancestor type of Perl regular expressions, then it's less specific input language can be fed into a Perl engine and Perl's more specific input language cannot be fed into it. Compatibility/incompatibility labels depend on which side of covariance/contravariance [1] the person doing the labeling stands. The authors of the library got their labelbaby label maker out first. If they were wrong, file an issue on their Github repository. [1]: https://en.m.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) https://en.m.wikipedia.org/wiki/Covariance_and_contravarianc...
    - rnovak 11y ago
      Well, since you want to get pedantic, fine.... Regular Expressions define/describe a language. They do not, can not, evaluate to a value, and it wouldn't even make sense if they did. Regular Expressions also don't by themselves accept input. A RE library/software accepts input (which is always a finite string, an expression (also a finite string), and always returns one of two values: The input string is a member of that language, or the input string is not a member of that language. The result is binary, and it isn't returned from the regular expression. Saying that you can't feed PCRE expressions into PIRE is completely false, since my original comment and the example in the linked github is literally a valid PCRE. That's like saying ASM.js isn't compatible with JavaScript, which is obvious nonsense, because it's by definition a strict subset of javascript. The set of all regular expressions that will test valid in this library is strictly a subset of those which are valid in PCRE. Type theory has nothing to do with anything here, and even if it did, PCRE and PIRE have identical functional types. They both accept string expressions (language descriptions), finite string input, and they both return boolean values (wether the input string is a member of that language). And enough with the snark already. You aren't the only one on the planet who knows what a DFA/NFA is, and your statements make it seem debatable that you understand them. But again, my first question was: "is this name really a joke?", which could have been answered by a single damned comment saying "yes".
      - brudgers 11y ago
        When we get to the end of a string, the automata is either in an accepting state or not. If that ain't a boolean, it'll do till one comes along...at least for me as I have a hard time imagining uses for regular expressions that aren't implemented so as to return values. Then again I'm not that bright and tend to mumble along writing down my thoughts. Which is why I'm writing about types...it seems to unroll the at hand possible "compatible/incompatible" conundrum of the name...or at least when after writing about it and heaedd to bed, I realized a simpler illustration was possible using Sets...and isn't that just the way of the maths, one description is isomorphic with another that makes explanation easier? Alas, I despaired of sharing it, but then this very morning I found a place for it. Anyway, if one tests for compatibility [whatever that may be] between a set S and a superset SS as suggested above, the results of the test depend on both the test chosen and the ordering of the arguments. This is to say: For each m in S, m is member of SS -> true For each mm in SS, mms is member if S -> false But choosing a different test S is subset of SS -> true SS is subset of S -> false Of course whether we map true to compatibility [whatever that is] or incompatibility is entirely dependent in our arbitrary choice of whether our test is deemed to be for compatibility or incompatibility. I wish I had an easy answer, but it's turtles, even by any other sweet smelling name, all the way down I'm afraid.
- userbinator 11y ago
  https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html and the articles it links to are a good detailed explanation of the advantages of the DFA approach.
  - loup-vaillant 11y ago
    To sum it up: The NFA and the DFA have exactly the same Big O complexity. The NFA is just slower by some factor. So that's not much of a difference. The real difference is between dynamic programming and backtracking. When you implement an NFA with dynamic programming, you're still O(N) with respect to the input no matter what. But when you use backtracking, as Perl does, you're prone to combinatorial explosions in some cases. Also keep in mind that PCRE are not regular expressions. They're more expressive than that, and can express more than just regular grammars. That's possible because when you start with backtracking, it is relatively easy to add other niceties on top of pure regular expressions.
    - brudgers 11y ago
      Though there is an equivalent DFA for every NFA, the DFA can have an exponentially larger number of states than the NFA, though my understanding is that's not usually the case in practice. In any event the processing time of an NFA implementation can reflect this explosion since the actual implementation algorithm of a finite state machine on ordinary hardware has to be deterministic.
      - loup-vaillant 11y ago
        > the DFA can have an exponentially larger number of states than the NFA Yep. Which is why some implementation fall back to NFA when the number of state of the DFA reaches some predefined threshold. > In any event the processing time of an NFA implementation* can reflect this explosion* Well, not necessarily. Trial and error (backtracking) is not the only way to simulate an NFA. A more reliable way to do it is to execute the multiple choices in parallel. This nullifies the combinatorial explosion because the different threads share a great deal of information. A thread of execution in a finite automaton has exactly 2 pieces of information: the current position in the character stream, and the current state. In the case of a DFA, you stick to a single thread of execution, and if you fail, there's nothing to backtrack to anyway. In the case of an NFA, you can maintain a set of current states. And that set will never be bigger than the number of states in your NFA. The algorithm looks like this: Set = [Start_state] Until input is empty: Read the next character New_set = [] // empty set For each state in your old set: Add all the possible next states to New_set Set = New_set If New_set is empty You failed to recognised the input You successfully recognised the input
- more_original 11y ago
  Perl's regex engine must use something stronger than plain NFAs. The expressive power of NFAs and DFAs is exactly the same. They both recognize the regular languages, which is less than what can be expressed with Perl "regular expressions".
  - brudgers 11y ago
    I'm using Friedl's classification scheme for regex engines from Mastering Regular Expressions. I don't know of a more standard survey regarding regex's as implemented in various programming languages. Anyway, from a practical standpoint an NFA has to be implemented as a push down automata in the Von Neumann machines we currently have to allow backtracking to simulate simultaneous exploration of the arbitrary number of DFA states that a single NFA state may represent. That doesn't make Friedl's classification useless.
rnovak 11y ago
Edit: I can't edit my post, but how about instead of down-voting, you answer my question? I don't get how my question isn't genuine.
- desdiv 11y ago
  It's a pun on Perl Compatible Regular Expressions. You're being downvoted for bikeshedding over a name.
deleted 11y ago
[deleted]
jlarocco 11y ago
I think it's called "incompatible" because it looks at it from the other direction, so to speak. There are valid Perl regular expressions, i.e. those using backtracking, that are incompatible with this regex engine.
- rnovak 11y ago
  Thank you, that's 100% the type of answer I was hoping for
loup-vaillant 11y ago
I don't know PCRE nor PIRE. Still… …I bet you can find some input that would work differently on PIRE and PCRE. Just use an escape sequence that PCRE recognise, and PIRE interprets as ordinary characters. Failing that, we may be able to find some input that is accepted by PCRE and rejected by PIRE; then some input that is accepted by PIRE and rejected by PCRE. If any of those two hypothesis turn out to be true, then PIRE is neither forward nor backward compatible with PCRE. So it would truly be incompatible. I expect the provided example works on both simply because most simple inputs would work on both. Showing incompatibilities was probably not the goal of this example.

by rnovak 11y ago

brudgers 11y ago

Perl's regex engine is uses a non-deterministic finite automata [NFA]. Because the Readme indicates each character is only examined once and that PIRE lacks backtracking, look ahead and capture groups, it's engine is almost certainly DFA [deterministic finite automata] based. Thus among the syntax it is likely to choke on or ignore are anything involving curly braces {}. Keep in mind that "regular expressions" can denote a notation for describing finite automata and that this is subtly different from the programming language implementation of regex engines in languages like Perl.

js2 11y ago
See https://swtch.com/%7Ersc/regexp/regexp1.html https://swtch.com/%7Ersc/regexp/regexp1.html for a fine explanation of DFA vs NFA.
rnovak 11y ago
Again, that's leaves it as a subset of Perls regular-expressions, not a disjoint/distinct set, which is what incompatibility would imply.
- brudgers 11y ago
  Since regular expressions evaluate to values [that's what makes them expressions], type theory is perhaps a better abstraction than set theory. In particular, since regular expressions accept an input and produce an output, it May be particularly useful to think of them as function types. If PIRE is an ancestor type of Perl regular expressions, then it's less specific input language can be fed into a Perl engine and Perl's more specific input language cannot be fed into it. Compatibility/incompatibility labels depend on which side of covariance/contravariance [1] the person doing the labeling stands. The authors of the library got their labelbaby label maker out first. If they were wrong, file an issue on their Github repository. [1]: https://en.m.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) https://en.m.wikipedia.org/wiki/Covariance_and_contravarianc...
  - rnovak 11y ago
    Well, since you want to get pedantic, fine.... Regular Expressions define/describe a language. They do not, can not, evaluate to a value, and it wouldn't even make sense if they did. Regular Expressions also don't by themselves accept input. A RE library/software accepts input (which is always a finite string, an expression (also a finite string), and always returns one of two values: The input string is a member of that language, or the input string is not a member of that language. The result is binary, and it isn't returned from the regular expression. Saying that you can't feed PCRE expressions into PIRE is completely false, since my original comment and the example in the linked github is literally a valid PCRE. That's like saying ASM.js isn't compatible with JavaScript, which is obvious nonsense, because it's by definition a strict subset of javascript. The set of all regular expressions that will test valid in this library is strictly a subset of those which are valid in PCRE. Type theory has nothing to do with anything here, and even if it did, PCRE and PIRE have identical functional types. They both accept string expressions (language descriptions), finite string input, and they both return boolean values (wether the input string is a member of that language). And enough with the snark already. You aren't the only one on the planet who knows what a DFA/NFA is, and your statements make it seem debatable that you understand them. But again, my first question was: "is this name really a joke?", which could have been answered by a single damned comment saying "yes".
    - brudgers 11y ago
      When we get to the end of a string, the automata is either in an accepting state or not. If that ain't a boolean, it'll do till one comes along...at least for me as I have a hard time imagining uses for regular expressions that aren't implemented so as to return values. Then again I'm not that bright and tend to mumble along writing down my thoughts. Which is why I'm writing about types...it seems to unroll the at hand possible "compatible/incompatible" conundrum of the name...or at least when after writing about it and heaedd to bed, I realized a simpler illustration was possible using Sets...and isn't that just the way of the maths, one description is isomorphic with another that makes explanation easier? Alas, I despaired of sharing it, but then this very morning I found a place for it. Anyway, if one tests for compatibility [whatever that may be] between a set S and a superset SS as suggested above, the results of the test depend on both the test chosen and the ordering of the arguments. This is to say: For each m in S, m is member of SS -> true For each mm in SS, mms is member if S -> false But choosing a different test S is subset of SS -> true SS is subset of S -> false Of course whether we map true to compatibility [whatever that is] or incompatibility is entirely dependent in our arbitrary choice of whether our test is deemed to be for compatibility or incompatibility. I wish I had an easy answer, but it's turtles, even by any other sweet smelling name, all the way down I'm afraid.
userbinator 11y ago
https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html and the articles it links to are a good detailed explanation of the advantages of the DFA approach.
- loup-vaillant 11y ago
  To sum it up: The NFA and the DFA have exactly the same Big O complexity. The NFA is just slower by some factor. So that's not much of a difference. The real difference is between dynamic programming and backtracking. When you implement an NFA with dynamic programming, you're still O(N) with respect to the input no matter what. But when you use backtracking, as Perl does, you're prone to combinatorial explosions in some cases. Also keep in mind that PCRE are not regular expressions. They're more expressive than that, and can express more than just regular grammars. That's possible because when you start with backtracking, it is relatively easy to add other niceties on top of pure regular expressions.
  - brudgers 11y ago
    Though there is an equivalent DFA for every NFA, the DFA can have an exponentially larger number of states than the NFA, though my understanding is that's not usually the case in practice. In any event the processing time of an NFA implementation can reflect this explosion since the actual implementation algorithm of a finite state machine on ordinary hardware has to be deterministic.
    - loup-vaillant 11y ago
      > the DFA can have an exponentially larger number of states than the NFA Yep. Which is why some implementation fall back to NFA when the number of state of the DFA reaches some predefined threshold. > In any event the processing time of an NFA implementation* can reflect this explosion* Well, not necessarily. Trial and error (backtracking) is not the only way to simulate an NFA. A more reliable way to do it is to execute the multiple choices in parallel. This nullifies the combinatorial explosion because the different threads share a great deal of information. A thread of execution in a finite automaton has exactly 2 pieces of information: the current position in the character stream, and the current state. In the case of a DFA, you stick to a single thread of execution, and if you fail, there's nothing to backtrack to anyway. In the case of an NFA, you can maintain a set of current states. And that set will never be bigger than the number of states in your NFA. The algorithm looks like this: Set = [Start_state] Until input is empty: Read the next character New_set = [] // empty set For each state in your old set: Add all the possible next states to New_set Set = New_set If New_set is empty You failed to recognised the input You successfully recognised the input
more_original 11y ago
Perl's regex engine must use something stronger than plain NFAs. The expressive power of NFAs and DFAs is exactly the same. They both recognize the regular languages, which is less than what can be expressed with Perl "regular expressions".
- brudgers 11y ago
  I'm using Friedl's classification scheme for regex engines from Mastering Regular Expressions. I don't know of a more standard survey regarding regex's as implemented in various programming languages. Anyway, from a practical standpoint an NFA has to be implemented as a push down automata in the Von Neumann machines we currently have to allow backtracking to simulate simultaneous exploration of the arbitrary number of DFA states that a single NFA state may represent. That doesn't make Friedl's classification useless.

rnovak 11y ago

Edit: I can't edit my post, but how about instead of down-voting, you answer my question? I don't get how my question isn't genuine.

desdiv 11y ago
It's a pun on Perl Compatible Regular Expressions. You're being downvoted for bikeshedding over a name.

deleted 11y ago

[deleted]

jlarocco 11y ago

I think it's called "incompatible" because it looks at it from the other direction, so to speak. There are valid Perl regular expressions, i.e. those using backtracking, that are incompatible with this regex engine.

rnovak 11y ago
Thank you, that's 100% the type of answer I was hoping for

loup-vaillant 11y ago

I don't know PCRE nor PIRE. Still… …I bet you can find some input that would work differently on PIRE and PCRE. Just use an escape sequence that PCRE recognise, and PIRE interprets as ordinary characters. Failing that, we may be able to find some input that is accepted by PCRE and rejected by PIRE; then some input that is accepted by PIRE and rejected by PCRE. If any of those two hypothesis turn out to be true, then PIRE is neither forward nor backward compatible with PCRE. So it would truly be incompatible. I expect the provided example works on both simply because most simple inputs would work on both. Showing incompatibilities was probably not the goal of this example.