blocks|key|1201182|text|因为正则表达式与自动机理论中的正则表达式不等价。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1201183|它们更像表亲，具有额外的功能，这使得它们更加复杂，有时(取决于正则表达式)不可能在长字符串上执行。|1201184|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Because regex are not equivalent to the Regular Expressions in Theory of Automata.

They are more like cousins with extra functionalities that make them more complex and sometimes (depending on the regex) impossible to execute on long strings.

blocks|key|2012101|text|(出于哪种必要性)它们被延长了吗？|type|blockquote|depth|inlineStyleRanges|entityRanges|data|2012102|Regexp实现是在缺乏regexp特性的系统中扩展的，这些系统需要困难的解决方法，例如用一种无表情的编程语言编写大量的代码。还有一个严重的风险，即代码可能被证明是正确的、可执行的，并且对假阳性匹配具有很强的鲁棒性。|unstyled|2012103|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|H|8|@]|9|@]|A|$]]|$1|E|3|-4|5|D|7|I|8|@]|9|@]|A|$]]]|F|$]]

<blockquote>
 (out of which necessity) were they extended?
</blockquote>

Regexp implementations were extended in systems in which the lack of a regexp feature requires difficult workarounds, such as writing a substantial amount of code in an inexpressive programming language. There is also the grave risk that the code might turn out to be correct, performant and robust against false positive matches.

blocks|key|2012115|text|一个很好的理由是灾难性回溯，它解释了为什么某些正则表达式的匹配不会在宇宙的热死亡之前返回。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2012116|entityMap|0|LINK|mutability|MUTABLE|url|https://regular-expressions.com/catastrophic.html?wlr=1|1|https://en.wikipedia.org/wiki/Heat_death_of_the_universe^0|8|5|0|Y|6|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

A good reason is <a href="https://regular-expressions.com/catastrophic.html?wlr=1" rel="nofollow noreferrer">catastrophic backtracking</a>, which explains why matching of some regexes will not return before the <a href="https://en.wikipedia.org/wiki/Heat_death_of_the_universe" rel="nofollow noreferrer">heat death of the universe</a>.

This is a theoretical Computer Science question (Computation Theory).

I know that RegExps can take a very long time to calculate. However, from Theory of Computation we know that matching with a Regular Expression can be done extremely fast in a few clock cycles.

If RegExps are equivalent to Finite Automata, why RegExps have (or require) a timeout method?
Using a DFA, the computation time for matching can be exteremely fast.

By RegExps I mean the Regular Expressions pattern matching classes in major languages; JavaScript, C#, etc.

Are common RegExps ("regex"s) not equivalent to the Regular Expressions in Theory of Automata (i.e. Regular Languages)?

For examples see: <a href="https://stackoverflow.com/questions/7616435/how-do-i-timeout-regex-operations-to-prevent-hanging-in-net-4-5">How do I timeout Regex operations to prevent hanging in .NET 4.5?</a> and <a href="https://stackoverflow.com/questions/29751230/regex-pattern-catastrophic-backtracking">Regex Pattern Catastrophic backtracking</a> .

If Regexp's matching require Backtracking, it means they are not equivalent to Regular Expressions.

If the languages captured by "Regexp"s are not Regular Languages, historically why (out of which necessity) were they extended?

If it that the resulting DFA will require a huge set of states?

Why does Regexp have a timeout method, while in theory they shouldn't?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

这是一个理论上的计算机科学问题(计算理论)。我知道RegExps需要很长的时间来计算。然而，从计算理论中我们知道，与正则表达式的匹配可以在几个时钟周期内快速完成。如果RegExps等价于有限自动机，为什么RegExps有(或需要)超时方法？使用DFA，匹配的计算时间可以非常快。RegExps指的是主要语言中的正则表达式...

问为什么Regexp有一个超时方法，而理论上它们不应该？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么Regexp有一个超时方法，而理论上它们不应该？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么Regexp有一个超时方法，而理论上它们不应该？
EN