4 ms·

Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.

by pkoird 3y ago

shagie 3y ago
Correct. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole. Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending_finite_automata_to_efficiently_match_Perl-compatible_regular_expressions https://www.researchgate.net/publication/221325349_Extending... > Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata. > In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for back-tracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system. ---- The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG (you can write CFGs that can't be matched by a PCRE - ([{}]) matching, a^nb^n and so on). So the question that gets interesting is "can every PCRE be matched by a CFG?" Is it a fork? or is it a non-integer language? https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy > Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy; these would be properly between Type-0 and Type-1. So there's a language between the Turing machine and the linear bounded Turing machine that matches a context sensitive language. Is the PCRE something between Type-2 and Type-3? or is it a Type-3+I? https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_generative_grammars https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_... > Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. ...
- davidgay 3y ago
  > The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG Hmm, there's a reduction of 3-cnf-sat to perl regexps, making them NP-complete. As CFGs are in NP... https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html
  - shagie 3y ago
    Reading up on the current spec, apparently a PCRE can do recursive calls. https://www.pcre.org/original/doc/html/pcrepattern.html#SEC23 https://www.pcre.org/original/doc/html/pcrepattern.html#SEC2... \( ( [^()]++ | (?R) )* \) https://regex101.com/r/eBtSTM/1 https://regex101.com/r/eBtSTM/1 for a slightly different formulation of that regex.
eru 3y ago
If you want something with an actual regular expression, have a look at https://codegolf.stackexchange.com/questions/3503/hard-code-golf-regex-for-divisibility-by-7 https://codegolf.stackexchange.com/questions/3503/hard-code-... which is a code golf for regular expressions to test divisibility by 7.

Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.

by pkoird 3y ago

Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.

shagie 3y ago

Correct. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole. Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending_finite_automata_to_efficiently_match_Perl-compatible_regular_expressions https://www.researchgate.net/publication/221325349_Extending... > Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata. > In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for back-tracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system. ---- The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG (you can write CFGs that can't be matched by a PCRE - ([{}]) matching, a^nb^n and so on). So the question that gets interesting is "can every PCRE be matched by a CFG?" Is it a fork? or is it a non-integer language? https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy > Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy; these would be properly between Type-0 and Type-1. So there's a language between the Turing machine and the linear bounded Turing machine that matches a context sensitive language. Is the PCRE something between Type-2 and Type-3? or is it a Type-3+I? https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_generative_grammars https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_... > Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. ...

davidgay 3y ago
> The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG Hmm, there's a reduction of 3-cnf-sat to perl regexps, making them NP-complete. As CFGs are in NP... https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html
- shagie 3y ago
  Reading up on the current spec, apparently a PCRE can do recursive calls. https://www.pcre.org/original/doc/html/pcrepattern.html#SEC23 https://www.pcre.org/original/doc/html/pcrepattern.html#SEC2... \( ( [^()]++ | (?R) )* \) https://regex101.com/r/eBtSTM/1 https://regex101.com/r/eBtSTM/1 for a slightly different formulation of that regex.

eru 3y ago

If you want something with an actual regular expression, have a look at https://codegolf.stackexchange.com/questions/3503/hard-code-golf-regex-for-divisibility-by-7 https://codegolf.stackexchange.com/questions/3503/hard-code-... which is a code golf for regular expressions to test divisibility by 7.