c/c++语言开发共享调车场算法能解析POSIX正则表达式吗?

乍一看, 分流码算法似乎适用于POSIX正则表达式解析,但由于我在编写解析器方面没有太多经验(或理论背景),我想在跳入并写入内容之前先询问SO半途而废。

也许这个问题的一个更复杂的版本是:对于分流码算法可以应用的问题类别的正式陈述是什么?

澄清:这个问题是关于您是否可以使用分流算法的基本原理将POSIX语法解析为抽象语法树,而不是您是否可以使用正则表达式来实现分流算法。 对不起我说不清楚开头!

    我很确定它可以。 如果你看一下Henry Spencer的正则表达式包:

    regexp.shar.Z

    这是Perl正则表达式的基础,你会注意到他将程序描述为“铁路正常forms”。

    我会说你的问题的答案是“不,你不能使用正则表达式实现分流码算法。” 这与您无法使用正则表达式解析任意HTML的原因相同。 归结为此:

    正则表达式没有堆栈。 因为分流码算法依赖于堆栈(当你从中缀转换为RPN时推送和弹出操作数),然后正则表达式没有执行此任务的计算“能力”。

    这掩盖了许多细节,但“正则表达式”是定义常规语言的一种方式。 当您“使用”正则表达式时,您要求计算机说:“查看文本正文并告诉我这些字符串是否都是我的语言。我使用正则表达式定义的语言。” 我将指出这个最优秀的答案,你和每个读这篇文章的人都应该更多地使用常规语言。

    因此,现在您需要一些数学概念来增强“常规语言”,以便创建更强大的语言。 如果您将分流码算法描述为计算能力模型的实现,那么您可能会说该算法将被描述为无上下文语法 (嘿,您知道什么,该链接使用表达式解析树作为一个例子。)一个下推式自动机 。 有堆栈的东西。

    如果您对自动机理论和复杂性类不太熟悉,那么那些维基百科文章如果没有从头开始解释它们可能没那么有用。

    关键是,您可以使用正则表达式来帮助编写调车场。 但是正则表达式不是很擅长进行具有任意深度的操作,而这个问题就是这个问题。 因此,我不会花太多时间在这个问题的正则表达式大道上。

    我不明白为什么它不合适。 看一些旧的代码,我似乎对我的上一个regexp解析器使用了完全不同的解析策略,但是(本质上,从一开始就是一个漫游,随着时间的推移构建生成的自动机表示,一些前瞻和递归调用实现正则表达式的分组)。

    我认为你会遇到一些问题,因为不同的角色在不同的情境中有不同的含义,例如

    ^[^az][asd-] 

    ^有两个不同的含义, - 。 我想我会选择一个递归下降解析器。

    需要了解更多c/c++开发分享调车场算法能解析POSIX正则表达式吗?,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)

      以上就是c/c++开发分享调车场算法能解析POSIX正则表达式吗?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注(计算机技术网)。

      本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

      如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/978815.html

      (0)
      上一篇 2021年12月12日
      下一篇 2021年12月12日

      精彩推荐