分流码算法能解析POSIX正则表达式吗？

Question

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

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

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

Answer 1

我会说你的问题的答案是“不，你不能使用正则表达式来实现调车场算法”。这与您无法使用正则表达式解析任意 HTML 的原因相同。归结起来就是：

正则表达式没有堆栈。由于调车场算法依赖于堆栈（在从中缀转换为 RPN 时压入和弹出操作数），因此正则表达式不具备执行此任务的计算“能力”。

这掩盖了许多细节，但“正则表达式”是定义正则语言的一种方法。当您“使用”正则表达式时，您是在要求计算机说：“查看文本正文并告诉我这些字符串中的任何一个是否属于我的语言。我使用正则表达式定义的语言。” 我将指出这个最优秀的答案，您和阅读本文的每个人都应该为更多有关常规语言的内容点赞。

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

如果您不太熟悉自动机理论和复杂性类别，那么如果不从头开始解释这些维基百科文章可能没有多大帮助。

重点是，您也许可以使用正则表达式来帮助编写调车场。但正则表达式不太擅长执行任意深度的操作，而这个问题正是如此。所以我不会花太多时间去解决这个问题的正则表达式。