Sat solver on top of regex matcher
yurichev.com
yurichev.com
You don't need backreferences for that:
'[^']*'|"[^"]*" /"([^"\\]|\\.)*"/
What you can't match without backreferences, however, is strings with customisable terminators, e.g. the behaviour in sed that whatever character you use after `s` is the regex terminator (it doesn't have to be `/`), or raw strings in C++.
> Won't work if you're already in a string
This doesn't make sense. How can you search for a string if you're already in a string? I can't think of a realistic situation where that would be useful or even really possible.
> or if there are escaped quotes in the string.
Solvable:
'(\'|\\|[^\'])*'|"(\"|\\|[^\"])*"
The regex in my previous comment already solves that. See: https://repl.it/repls/SolidCapitalProgram
query = "select * from table where name like \"%foo\""Although if you want to do it with pure regex, it can be done without backreferences too, although it would be exponentially large as you get more and more levels of nesting, whereas with backreferences I think it would only get quadratically large.
But more broadly, any situation where you search from a non-zero index has this problem.
I'm surprised your example works in Python. Is that a property of Python's parser, or all regex matchers?
Yeah, I agree. My point was that regex won't work, regardless of if you have backreferences or not. So backreferences won't help.
> But more broadly, any situation where you search from a non-zero index has this problem.
I'm not sure I understand that. A lot of regex libraries let you specify a start index. It won't take into account data from before the start index though (regex doesn't really do that, regardless of backreferences). If your regex library doesn't support passing in a start index, you can just take a substring starting at that index, then search the substring.
I don't think Python is really special. Python's findall() is just a convenience function that does a loop finding a match, then finding another match that starts after the first match, etc. Most languages provide a way to find the end point of the most recent match, and then you can just write the loop yourself to start the next search at that point.
"abc{ "def" }"
"a{ "b{ "c{ "d{ "e{ "f" }g" }h" }i" }j" }k"
→ "abcdefghijk"
my $count = 3;
"I went to $count place{ "s" if $count ≠ 1 } today"And that example reminds me that Bash can do something similar:
echo "$(echo "$(echo "$(echo "hi")")")"Basically you can use backreferences for that if you also allow the regex to be recursive.
my $regex = /
:ratchet
$<q> = (<["']>) # the beginning quote
{}:my $q = ~$<q>; # put it into a more normal lexical var
# capture between " and {
$<l> = ( [ <!before $q> <-[{}]> ]* )
[
[
:sigspace
｢{｣
<self=&?BLOCK>? # recurse
｢}｣
]
{$q = ~$<q>}
# capture between } and "
$<r> = ( [ <!before $q> <-[{}]> ]* )
]?
"$q" # match the end quote
# pass the combined string parts upwards
{ make ($<l> // '') ~ ($<self>.ast // '') ~ ($<r> // '') }
/;
｢'a{ "b{ "c{ "d{ 'e{ "f" }g' }h" }i" }j" }k'｣ ~~ /^ <r=$regex> $ { make $<r>.ast }/;
say $/.ast;
# abcdefghijk
`<foo=bar>` is a way to call `bar`, but also save it under the name of `foo`. `$<foo> = …` is a way to capture `…` and save it under the name of `foo`.
---
It is a lot nicer and modular when you use regexes as part of a grammar:
# use Grammar::Tracer;
grammar String::Grammar {
token TOP { <strings> }
rule strings {
# at least one string
# if there are more than one they are separated by ~
<string> + % ｢~｣
}
token string {
$<q> = <["']>
# set a dynamic variable to the quote character
{}:my $*quote = ~$<q>;
<string-part>*
"$<q>"
}
# multiple tokens that act like one
# which is nicer than using |
proto token string-part {*}
multi token string-part:<non> {
[ <-[{}]> <!after $*quote> ]+
}
multi token string-part:<block> {
<block>
}
rule block {
｢{｣ ~ ｢}｣ <strings>?
}
}
class String::Actions {
method TOP ($/) { make $<strings>.ast }
method strings ($/) { make [~] @<string>».ast }
method string ($/) { make [~] @<string-part>».ast }
method block ($/) { make $<strings>.ast }
method string-part:<non> ($/) { make ~$/ }
method string-part:<block> ($/) { make $<block>.ast }
}
say String::Grammar.parse(
｢"a{ "b{ "c{ "d{ "e{ "f" }g" ~ "zz" }h" }i" }j" }k"｣,
:actions( String::Actions ),
).ast;
# abcdefgzzhijk
Every instance of `<foo>` is basically a method call.
`make` is about generating an `.ast` to pass up and out of the parse. In this case the only thing the actions class does is return what would be the resulting string if it were compiled in Raku.
They are fairly powerful in terms of what they're capable of parsing however (not enough for an arbitrary html document, but enough to handle the hairier situations in this thread that people thought they couldn't), and that does mean that a regular expression generator can handle all of those situations as well and potentially be much more readable.
If I found myself writing code like this I'd still want to reach for a better parsing technology, but you can use other languages to add abstractions to regex. Here's a Python3.6+ example assuming any desired backslashes have already been applied:
'|'.join(rf'{a}[^{b}]*{b}' for a,b in pairs)The author is also incorrect in stating However the author incorrectly states that only 3SAT problems are solvable. Proof that 3SAT is NP-hard does not exclude broader SAT.
Every SAT problem can be converted into a 3-SAT problem so that's also not really an issue, they are both NPC
Jokes apart: I'd love for you to elaborate a bit more on this. I'm pretty sure I would benefit a lot from a more expanded, "dumber" explanation.
> I'd love for you to elaborate a bit more on this.
I'm not the original poster, but I'll have a go.
SAT is NP-Hard. In other words, any literally any NP problem can be efficiently[0] converted to SAT, and any solution can then be efficiently[0] converted back to a solution to the original.
Example: Think of the problem of factoring integers. Someone gives you an integer to factor, with a little work you can create a SAT instance, solve that, and then read off the factorisation of the original integer. SAT is, in some real sense, at least has hard as INT.
So there is a proof that SAT is at least as hard as every NP problem. That's what we call "NP-Hard".
Now someone has shown that they can solve SAT problems by using regex_backtrack. That means that every NP problem can be converted to SAT, then converted to regex+backtrack, solved, and the solution to the original read out from the result.
Thus regex+backtrack is at least as hard as every NP problem.
Now in the case of SAT, it itself is NP. So the combination of being NP and being NP-Hard is called "NP-Complete", or NPC. So SAT is an example of a problem that's NPC.
What has not been shown (I think) is that regex+backtrack is in NP. Showing that a solution to regex+backtrack implies a solution to SAT shows that regex+backtrack is NP-Hard.
If the linked article also shows that regex+backtrack is NP, then it is therefore NPC. But we can see that regex+backtrack is in NP, because verifying an alleged match is a polynomial time operation.
So regex-backtrack is NPC.
+--------------------+
| |
NP-Hard -> | |
| ,------------. |
\ / \ /
X NP-Complete X
/ \ / \
/ `------------' \
NP -> | |
| |
. +------------+ ,
\ | Polynomial | /
`--+------------+--'
> I read it the other way:
OK ...
> all CNF instances can be rewritten as regexp + backreferences,
By CNF you are referring to instances of the SAT problem. So yes, if you have an instance of the SAT problem, it can be re-written as an instance of regex+backtrack.
> meaning re + backreferences are at least as general that SAT,
Yes, the regex+backtrack problem is at least as hard as the SAT problem.
> ... not at most as.
Where did I say that? Here's a stripped-down summary of my comment:
* SAT is NP-Hard.
* Now someone has shown that they can solve SAT problems by using regex+backtrack. (That's the linked article)
* Thus regex+backtrack is at least as hard as every NP problem.
* SAT is NP, so it's NPC
* regex+backtrack can be seen to be in NP.
* So regex-backtrack is NPC.
So rewording that:
* The linked article shows regex+backtrack >= SAT.
* Independently we observe that checking an alleged regex+backtrack solution is a polynomial task, therefore regex+backtrack is in NP.
* SAT is in NPC, therefore regex+backtrack <= SAT (because regex+backtrack is in NP).
* Thus regex+backtrack = SAT (for some definition of "=")
So, I think you must have misread something ... I think everything I've written is correct as stands.
That's the point I missed at first. That's good news, because I was pretty sure perl regex were accidentally Turing complete, I don't know why.
This sort of thing can be really tough to follow because it's all deeply intertwungle. Glad I got it right.
Cheers!
Is there a general consensus to use "regular expression" to refer to the actual regular ones and "regex" to refer to the non-regular variants?
# math and/or computer science texts? It's the regular ones.
# pretty much elsewhere? It's the extended ones.
# threads about parsing HTML with regular expressions? People using both and insisting their version is the only correct one.
https://docs.raku.org/language/regexes (see the intro paragraph)
I don't think there's a difference, and if there is one, it's probably not relevant to programming. Whereas the one I'm highlighting is relevant to programming.
Personally I make the distinction, but I've noticed many many people do not, hence the question.
Timings for fred.cnf on my machine:
python: 0m53.744s
PHP (no PCRE JIT): (hits backtrack limit in 1m15.994s)
PHP (PCRE JIT): 0m20.109s
Still, yes, you can mess up your "add 1 to the input" program and make it run infinitely.
That being said, regexps were not initially meant to be "programming languages", so I'm not sure about the "feature, not bug" part. I'd rather have a notation that would let me solve, for instance, the "HTML tag matching" problem and would be guaranteed to always terminate, than one that also lets me implement Conway's game of life.
Took 9min and 10seconds on RPi 3 running Ubuntu 20.04. Consuming 100% CPU and 1% RAM (1024MB).