调车场算法能解析POSIX正则表达式吗？

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

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

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

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

regexp.shar.Z

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

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

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

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

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

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

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

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

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

^[^az][asd-]

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