用Pike VM实现正则表达式分组捕获时为啥只需要保留一条thread
刚刚在stackoverflow上描述问题时，写着写着突然想通了，于是便来回答自己的提问：正则表达式中没有用到backreference，即submatching对后面的状态不影响，自动机的所有状态是固定的，既然不同的thread能同时运行至相同状态，即所有这些thread往后同时经历的状态都是相同的，假如当中有一条失配则全部失配，若有一条匹配则全部匹配，且匹配结果完全相同，不同thread之间只有submatching不同，相当于(ab)b与(a)(bb)的区别，而我们只需要得到一种submatching，所以只保留一条thread
■网友
VM 匹配其实本质上和 NFA 模拟是相同的，再深入一点，其实二者都是宽度优先的图遍历算法，其中用 state 的 listid/pc 是否等于当前的那个 listid/pc 来作为普通宽度优先搜索中的 color/is_visited 判断(这里不需要区分黑白灰三种情况，只有黑白两种)。
推荐阅读
- 北京22家市属医院均开展安检基本实现重点区域安检措施全覆盖
- 长江流域渔民退捕“上岸”实现扩产新致富
- 实现“甜蜜计划”，这对中哈跨国夫妻好甜
- 北京地铁11号线西段三座车站提前实现主体结构封顶
- 特斯拉|特斯拉将全面发布全自动驾驶软件最新版，曾承诺年底实现完全无人干预
- |徐州建有农家书屋2205家，实现数字书屋全覆盖
- 阿里云|【GET2020】阿里云解航：在线教育帮助线下教育一起实现教育公平和个性化
- 我有几个app点子，拉出来比较容易实现的一个和大家探讨，只差程序员（替你们说了）请问这个点子咋样
- 一个利用量子纠缠实现超光速通讯的构想，可行吗
- 请问计算器求积分，求导，求极限怎样实现