草庐IT

c# - 扩展正则语言框架中正则语言的算法复杂度

coder 2024-03-18 原文

我有一定的形式语言背景，最近我发现 Java 和其他语言使用的是扩展正则语言。由于我的背景，当我为 Pattern 调用编译时，我总是假设使用 Java 这样的语言。它在后台生成了 DFA 或 Transducer。因此，我一直假设无论我的正则表达式多么丑陋，无论我的正则表达式、Pattern.matches 或类似方法在线性时间内运行多长时间。但这个假设似乎是 incorrect .

A post我读到似乎暗示某些 Regex 表达式确实在线性时间内运行，但我并不完全相信或信任一个人。

我最终会编写自己的 Java 正式正则表达式库(我发现的现有库只有 GNU GPL 许可证)，但与此同时我对 Java/C# 正则表达式的时间复杂度有一些疑问。想保证我读的内容elsewhere是正确的。

问题:

  1. 像\sRT\s. 这样的形式化语言，Java/C# 中正则表达式的匹配方法会解决线性或非线性时间的成员关系问题吗？
  2. 一般来说，我如何知道给定正则语言的表达式成员问题是否是正则表达式的线性时间？

我进行文本分析，发现 Java 正则表达式不是 DFA 真是令人沮丧。

最佳答案

Because of my background, I had always assumed in languages like Java when I call compile for Pattern it produced a DFA or Transducer in the background.

这种信念在学术界很普遍。实际上，正则表达式编译不会生成 DFA 然后执行它。我在这方面只有少量经验；我在 1990 年代曾短暂参与过 Microsoft JavaScript 实现中的正则表达式编译系统。我们选择将“正则”表达式编译成简单的特定领域字节码语言，然后为该语言构建解释器。

正如您所注意到的，这可能会导致重复回溯在输入长度上具有指数级的不良时间行为，但编译状态的构造在表达式的大小上基本上是线性的。

那么让我用另外两个问题来反驳你的问题——我注意到这些是真正的问题，而不是修辞。

1) 每个实际上 正则表达式都对应于一个具有 n 个状态的 NDFA。相应的 DFA 可能需要叠加多达 2n 个状态。那么，是什么阻止了构建 DFA 所花费的时间在病理情况下呈指数增长？运行时间在输入中可能是线性的，但如果运行时间在模式大小上呈指数增长，那么基本上您只是用一种非线性换取另一种非线性。

2) 现在所谓的“正则”表达式已经不是那种东西了；他们可以做括号匹配。它们对应于下推自动机，而不是非确定性有限自动机。是否存在为“正则”表达式构造相应下推自动机的线性算法？

关于c# - 扩展正则语言框架中正则语言的算法复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20528505/

c#正则语言sectionnoreferrer的javaregextime-complexity

有关c# - 扩展正则语言框架中正则语言的算法复杂度的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  2. ruby - 使用 C 扩展开发 ruby​​gem 时，如何使用 Rspec 在本地进行测试？ - 2

    我正在编写一个包含C扩展的gem。通常当我写一个gem时，我会遵循TDD的过程，我会写一个失败的规范，然后处理代码直到它通过，等等......在“ext/mygem/mygem.c”中我的C扩展和在gemspec的“扩展”中配置的有效extconf.rb，如何运行我的规范并仍然加载我的C扩展？当我更改C代码时，我需要采取哪些步骤来重新编译代码？这可能是个愚蠢的问题，但是从我的gem的开发源代码树中输入“bundleinstall”不会构建任何native扩展。当我手动运行rubyext/mygem/extconf.rb时，我确实得到了一个Makefile(在整个项目的根目录中)，然后当

  3. ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2

    在我的应用程序中，我需要能够找到所有数字子字符串，然后扫描每个子字符串，找到第一个匹配范围(例如5到15之间)的子字符串，并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串，例如，re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项，并且只替换第N个匹配项，我该怎么做？例如，如果我想替换第三个匹配项“10”(匹配项[2])，我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg

  4. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  5. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  6. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  7. c - mkmf 在编译 C 扩展时忽略子文件夹中的文件 - 2

    我想这样组织C源代码:+/||___+ext||||___+native_extension||||___+lib||||||___(Sourcefilesarekeptinhere-maycontainsub-folders)||||___native_extension.c||___native_extension.h||___extconf.rb||___+lib||||___(Rubysourcecode)||___Rakefile我无法使此设置与mkmf一起正常工作。native_extension/lib中的文件(包含在native_extension.c中)将被完全忽略。

  8. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  9. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  10. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

随机推荐