用PCRE正则expression式匹配正确的两个二进制数
(?<a>[01]+)\s*\+\s*(?<b>[01]+)\s*=\s*(?<c>[01]+) ，其中a + b == c （如二进制加法）必须保持？
这些应该匹配：
0 + 0 = 0 0 + 1 = 1 1 + 10 = 11 10 + 111 = 1001 001 + 010 = 0011 1111 + 1 = 10000 1111 + 10 = 10010
这些不应该匹配：
0 + 0 = 10 1 + 1 = 0 111 + 1 = 000 1 + 111 = 000 1010 + 110 = 1000 110 + 1010 = 1000
TL; DR ：是的，这确实是可能的（与Jx标志一起使用）：
(?(DEFINE) (?<add> \s*\+\s* ) (?<eq> \s*=\s* ) (?<carry> (?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) ) (?<digitadd> (?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) ) (?<recursedigit> (?&add) 0*+ (?:\d*(?:0|1(?<r1>)))? (?(ro)|(?=(?<cr>1)?))\k<r> (?&eq) \d*(?&digitadd)\k<f>\b | (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recursedigit) ) (?<checkdigit> (?:0|1(?<l1>)) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit) ) (?<carryoverflow> (?<x>\d+) 0 (?<y> \k<r> (?&eq) 0*\k<x>1 | 1(?&y)0 ) | (?<z> 1\k<r> (?&eq) 0*10 | 1(?&z)0 ) ) (?<recurseoverflow> (?&add) 0*+ (?(rlast) \k<r> (?&eq) 0*+(?(ro)(?:1(?=0))?|1)\k<f>\b | (?:(?<remaining>\d+)(?=0\d* (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) 0*\k<remaining>\k<f>\b | (?&carryoverflow)\k<f>\b)) | (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|(?=(?:\d\k<r>(?&eq)(?<rlast>))?)\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurseoverflow) ) (?<s> (| 0*? (?<arg>[01]+) (?&add) 0+ | 0+ (?&add) 0*? (?<arg>[01]+)) (?&eq) (*PRUNE) 0* \k<arg> | 0*+ (?=(?<iteratedigits> (?=(?&checkdigit))\d (?:\b|(?&iteratedigits)) )) (?=[01]+ (?&add) [01]+ (?&eq) [01]+ \b) (?<r>) (?<f>) (?&recurseoverflow) ) ) \b(?&s)\b
现场演示： https ： //regex101.com/r/yD1kL7/26
[ 更新 ：由于PCRE中的错误 ，该代码仅适用于所有PCRE JIT处于活动状态的情况; 感谢Qwerp-Derp的 注意 ; 没有JIT例如100 + 101 = 1001不匹配。]
这是一个相当怪异的正则expression式。 所以，让我们一步一步地了解发生了什么事情。
提示 ：为了便于记忆，并通过解释说明，让我解释一个或两个数字捕获组名称的名称（除了前两个都是标志 [见下文]）：
r => right; it contains the part of the right operand right to a given offset f => final; it contains the part of the final operand (the result) right to a given offset cl => carry left; the preceding digit of the left operand was 1 cr => carry right; the preceding digit of the right operand was 1 l1 => left (is) 1; the current digit of the left operand is 1 r1 => right (is) 1; the current digit of the right operand is 1 ro => right overflow; the right operand is shorter than the current offset rlast => right last; the right operand is at most as long as the current offset
对于更可读的+和=可能的前导和尾随空格，有两个捕获组(?<add> \s*\+\s*)和(?<eq> \s*=\s*) 。
我们正在执行一个加法。 因为这是正则expression式，我们需要一次validation每个数字。 所以，看看这个背后的math：
检查添加一个数字
current digit = left operand digit + right operand digit + carry of last addition
我们怎么知道进位？
我们可以简单地看一下最后一位数字：
carry = left operand digit == 1 && right operand digit == 1 || (left operand digit == 1 || right operand digit == 1) && result digit == 0
这个逻辑是由捕获组提供的，定义如下：
(?<carry> (?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) )
用cl表示最后一个左操作数的数字是否为1， cr是最后一个右操作数的数字是否为1; \d0是检查结果中的最后一位数字是否为0。
注意 ： (?(cl) ... | ...)是一个条件构造，用于检查捕获组是否已被定义。 由于捕获组被限制在每个recursion级别，所以这可以很容易地用作设置布尔标志的机制（可以在任何地方用(?<cl>)来设置），稍后可以对其进行有条件的处理。
那么实际添加是一个简单的：
is_one = ((left operand digit == 1) ^ (right operand digit == 1)) ^ carry
用digitadd捕获组表示（使用a ^ b == (a && !b) || (!a && b) ，使用l1表示左操作数的数字是否等于1， r1是否等于右数字：
(?<digitadd> (?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) )
在给定的偏移量处检查添加
现在，我们可以通过在该偏移量处调用(?&digitadd)来validation给定的cr ， cl ， l1和r1结果中的数字是否正确。
…在那个偏移处 这是下一个挑战，find抵消。
根本的问题是，给定三个string之间有一个已知的分隔符，如何从右边find正确的偏移量。
例如1***+****0***=****1*** （分隔符是+和=在这里， *表示任意数字）。
甚至更根本的是： 1***+****0***=1 。
这可以匹配：
(?<fundamentalrecursedigit> \+ \d*(?:1(?<r1>)|0)\k<r> = (?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) ) \b | (?=\d* + \d*(?<r>\d\k<r>) =) \d (?&fundamentalrecursedigit) ) (?<fundamentalcheckdigit> # Note: (?<r>) is necessary to initialize the capturing group to an empty string (?:1(?<l1>)|0) (?<r>) (?&fundamentalrecursedigit) )
（非常感谢nhahdth为他解决这个问题 – 在这里稍微修改，以适应这个例子）
首先我们在当前偏移处存储关于数字的信息（ (?:1(?<l1>)|0) – 设置标志 （即可以用(?(flag) ... | ...) ） l1当前数字是1。
然后，我们用(?=\d* + \d*(?<r>\d\k<r>) =) \d (?&fundamentalrecursedigit)recursion地在search的右操作数的右边build立string。它在recursion的每个级别上前进一位数字（在左边的操作数上）， 并且在右边的操作数的右边部分增加一位数字：（ (?<r> \d \k<r>)重新定义r捕获组并将另一个数字添加到已有的捕获（用\k<r>引用）。
因此，只要左边的操作数有数字，并且在每个recursion级别上只有一个数字被添加到r捕获组，那么这个循环就会recursion，这个捕获组将包含和左操作数上的数字一样多的字符。
现在，在recursion结束时（即到达分隔符+时），我们可以直接通过\d*(?:1(?<r1>)|0)\k<r>search的数字现在就是捕获组r匹配之前的数字。
现在还有条件设置的r1标志，我们可以进行到底，用简单的条件检查结果是否正确： (?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) 。
鉴于此，将此延伸至1***+****0***=****1*** ：
(?<fundamentalrecursedigit> \+ \d*(?:1(?<r1>)|0)\k<r> = \d*(?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) )\k<f> \b | (?=\d* + \d*(?<r>\d\k<r>) = \d*(?<f>\d\k<f>)\b) \d (?&fundamentalrecursedigit) ) (?<fundamentalcheckdigit> (?:1(?<l1>)|0) (?<r>) (?<f>) (?&fundamentalrecursedigit) )
通过使用完全相同的技巧，在f捕获组中也收集结果的正确部分，并且在该捕获组f匹配之前访问该偏移。
让我们添加对进位的支持，实际上只是在左和右操作数的当前位数之后通过(?=(?<cr/cl>1)?)设置下一个数字是否为1的cr和cl标志：
(?<carryrecursedigit> \+ \d* (?:1(?<r1>)|0) (?=(?<cr>1)?) \k<r> = \d* (?&digitadd) \k<f> \b | (?=\d* + \d*(?<r>\d\k<r>) = \d*(?<f>\d\k<f>)\b) \d (?&carryrecursedigit) ) (?<carrycheckdigit> (?:1(?<l1>)|0) (?=(?<cl>1)?) (?<r>) (?<f>) (?&carryrecursedigit) )
检查等长度的input
现在，我们可以在这里完成，如果我们要填补所有input足够的零：
\b (?=(?<iteratedigits> (?=(?&carrycheckdigit)) \d (?:\b|(?&iteratedigits)) )) [01]+ (?&add) [01]+ (?&eq) [01]+ \b
即recursion地为左操作数的每个数字断言可以执行加法，然后成功。
但显然，我们还没有完成。 关于什么：
- 左操作数比右边长？
- 右操作数比左边长？
- 左边的操作数和右边的操作数一样长或长，结果有最高有效位（即需要前导1）？
处理左边的操作数比右边的操作数长
这个很不重要，当我们完全抓住它的时候，就停止尝试向r捕获组添加数字，设置一个标志（这里： ro ）不考虑它适合携带，并且使一个数字前导r可选（由(?:\d* (?:1(?<r1>)|0))? ）：
(?<recursedigit> \+ (?:\d* (?:1(?<r1>)|0))? (?(ro)|(?=(?<cr>1)?)) \k<r> = \d* (?&digitadd) \k<f> \b | (?=\d* + (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) = \d*(?<f>\d\k<f>)\b) \d (?&recursedigit) ) (?<checkdigit> (?:1(?<l1>)|0) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit) )
这正在处理正确的操作数，就好像它是零填充的; 现在r1和cr从来就不会在那个点之后被设置。 这就是我们所需要的。
在这里可能很容易被弄糊涂，为什么我们可以在超过正确的操作员长度时立即设置ro标志，并立即忽略进位; 原因是checkdigit已经占用了当前位置的第一位，所以我们实际上已经超过了右操作数的末尾一位数。
右边的操作数恰好比左边的要长
这现在有点困难。 我们不能把它塞进recursedigit因为它只会像左操作数中的数字一样迭代。 因此，我们需要一个单独的匹配。
现在有几个案例需要考虑：
- 从左边操作数的最高有效位数开始增加一个进位
- 没有携带。
对于前一种情况，我们希望匹配10 + 110 = 1000 11 + 101 = 1000 ; 对于后一种情况，我们希望匹配1 + 10 = 11或1 + 1000 = 1001 。
为了简化我们的任务，现在我们将忽略前导零。 那么我们知道最重要的数字是1.现在没有进位，只有在以下情况下：
- 右操作数的当前偏移量（即左操作数的最高有效位数的偏移量）的数字为0
- 而且前面的偏移量没有进位，这意味着结果中当前的数字是1。
这转化成以下说法：
\d+(?=0)\k<r> (?&eq) \d*(?=1)\k<f>\b
在这种情况下，我们可以用(?<remaining>\d+)来捕获第一个\d+ ，并要求它位于\k<f> （结果当前偏移量右侧的部分）的前面：
(?<remaining>\d+)\k<r> (?&eq) \k<remaining>\k<f>\b
否则，如果有进位，我们需要增加右操作数的左边部分：
(?<carryoverflow> (?<x>\d+) 0 (?<y> \k<r> (?&eq) \k<x>1 | 1(?&y)0 ) | (?<z> 1\k<r> (?&eq) 10 | 1(?&z)0 ) )
并将其用作：
(?&carryoverflow)\k<f>\b
这个carryoverflow捕获组通过复制右操作数的左边部分，在那里find最后一个零，并且用零来replace那些比那个零不明显的一个零，并且用零来replace零。 如果该部分没有零点，那么这些零点就全部由一个零代替，并且加上一个前导点。
或者用较less的话来expression（n是任意的，以便它适合 ）：
(?<x>\d+) 0 1^n \k<r> (?&eq) \k<x> 1 0^n \k<f>\b | 1^n \k<r> (?&eq) 1 0^n \k<f>\b
所以，让我们运用我们通常的技巧来找出操作数右边的部分：
(?<recurselongleft> (?&add) (?:(?<remaining>\d+)(?=(?=0)\k<r> (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) \k<remaining>\k<f>\b | (?&carryoverflow)\k<f>\b) | (?=\d* (?&add) \d*(?<r>\d\k<r>) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurselongleft) )
请注意，我已经在第一个分支(?&eq) (*PRUNE)之后添加了一个(*PRUNE) ，以避免回溯到具有carryoverflow的第二个分支，以防碰巧没有进位并且结果不匹配。
注意 ：我们不会在这里对\k<f>部分进行任何检查，这是由上面的carrycheckdigit捕获组pipe理的。
领先的情况1
我们确定不希望1 + 1 = 0被匹配。 但是，如果我们单独去checkdigit 。 所以，在领导1是必要的情况下有不同的情况（如果前面的右操作数的情况还没有被覆盖的话）：
- 两个操作数（没有前导零）的长度是相等的（即它们都有一个最高有效位，加起来就剩下一个进位）
- 左边的操作数更长，并且有最高有效位数的进位，或者两个string都是一样长的。
前一种情况处理input如10 + 10 = 100 ，第二种情况处理110 + 10 = 1000以及1101 + 11 = 10100 ，最后一种处理111 + 10 = 1001 。
第一种情况可以通过设置一个标志ro来处理，左边的操作数是否比右边的长，然后在recursion结束时可以检查：
(?<recurseequallength> (?&add) \k<r> (?&eq) (?(ro)|1)\k<f>\b | (?=\d* (?&add) (?:\k<r>(?<ro>) | \d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurseequallength) )
第二种情况意味着我们只需要在ro情况下检查是否存在进位（即右操作数越短）。 通常可以检查进位（因为最重要的数字总是1，右边的操作数数字隐含0）然后用一个平凡的(?:1(?=0))?\k<f>\b是当前偏移量中的一个进位数，结果是0。
这很容易实现，因为checkdigit所有其他数字都将由checkdigit进行validation。 因此，我们可以在这里检查运载在这里。
因此，我们可以将此添加到recurseequallength交替的第一个分支：
(?<recurseoverflow> (?&add) (?(rlast) \k<r> (?&eq) (?(ro)(?:1(?=0))?|1)\k<f>\b | (?:(?<remaining>\d+)(?=0\d* (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) \k<remaining>\k<f>\b | (?&carryoverflow)\k<f>\b)) | (?=\d* (?&add) (?:\k<r>(?<ro>)|(?=(?:\d\k<r>(?&eq)(?<rlast>))?)\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurseoverflow) )
然后把所有的东西连接在一起：首先检查每个数字的checkdigit （与之前简单的填充零的情况相同），然后初始化recurseoverflow使用的不同的捕获组：
\b (?=(?<iteratedigits> (?=(?&checkdigit))\d (?:\b|(?&iteratedigits)) )) (?=[01]+ (?&add) [01]+ (?&eq) [01]+ \b) (?<r>) (?<f>) (?&recurseoverflow) \b
什么零呢？
0 + x = x和x + 0 = x仍未处理，将失败。
我们不是狡猾地去处理大的捕捉组，而是手动处理它们：
(0*? (?<arg>[01]+) (?&add) 0+ | 0+ (?&add) 0*? (?<arg>[01]+)) (?&eq) 0* \k<arg>
注意 ：当与主分支交替使用时，我们需要在(?&eq)之后放一个(*PRUNE) ，以避免当任何操作数为零且匹配失败时跳入该主分支。
现在，我们也总是假定input中没有前导零来简化expression式。 如果你看一下最初的正则expression式，你会发现许多出现0*和0*+ （占有欲避免回溯到和意外的事情发生），以便跳过前面的零，因为我们在某些地方假设最左边数字是1。
结论
就是这样。 我们实现了只匹配正确的二进制数字。
关于相对较新的J标志的小logging：它允许重新定义捕捉组。 为了将捕获组初始化为空值，这首先是重要的。 此外，它简化了一些条件（像addone ），因为我们只需要检查一个值而不是两个。 比较(?(a) ... | ...)与(?(?=(?(a)|(?(b)|(*F)))) ... | ...) 。 另外，不可能在(?(DEFINE) ...)构造内任意重新定义多重定义的捕获组。
最后说明：二进制加法不是乔姆斯基3型（即常规）语言。 这是一个PCRE特定的答案，使用PCRE的特定function。 [其他类似.NET的正则expression式也可以解决这个问题，但不是全部。]
如果有任何问题，请留下评论，然后我会在这个答案中澄清这一点。
