回溯

1、NFA引擎最重要的性质是:遇到两个匹配成功的情况,选择其中的一个,同时记住另一个,作为备选状态。

2、需要做出选择的情况有:量词和多选结构。量词是匹配优先的,而多选结构往往是按顺序选择的。

3、选择一条支路,全局匹配成功,匹配结束。如果失败,后退一步,选择另一条支路,后退只是后退一步,符合后进先出。如果全局匹配成功,return 成功。如果尝试了所有的路径,还不成功,return 匹配失败。

原文地址:https://www.cnblogs.com/nzbbody/p/4419784.html