返回主题:正则引擎与回溯性能

知识卡片

普通读书笔记卡 · 1912.a.1

回溯保存选择

理解等级:未标注

回溯式引擎在分支或可选重复处保留未走的选择。备用状态包含模式中的继续位置、文本中的位置,以及需要恢复的捕获等状态;局部失败时,优先回到最近保留的选择,即后进先出。当前起点所有路均失败后,普通搜索才可能换到下一个起点,后者与表达式内部回溯是两层动作。成功的局部匹配不保证全式成功,捕获也不能保留已经被放弃路径上的旧结果。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      备用状态 Saved States 用NFA正则表达式的术语来说,那些面包屑相当于“备用状态(saved state)”。它们用来标记:在需要的时候,匹配可以从这里重新开始尝试。它们保存了两个位置:正则表达式中的位置,和未尝试的分支在字符串中的位置。因为它是NFA匹配的

    参考来源

    - 位置:《精通正则表达式(第3版)》回溯(spine 29;来源项目book-sources,`extracted/精通正则表达式(第3版)/_epub-src/text/part0009_split_004.html`;来源键`s029-ch04-003`)。 - 结论依据:本节原文、执行位置图与测验答案均实际读取;按本书回溯式引擎模型解释,不补造实测结果。 - 原始内容:备用状态 Saved States 用NFA正则表达式的术语来说,那些面包屑相当于“备用状态(saved state)”。它们用来标记:在需要的时候,匹配可以从这里重新开始尝试。它们保存了两个位置:正则表达式中的位置,和未尝试的分支在字符串中的位置。因为它是NFA匹配的