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

我相当肯定它能。如果你看看Henry Spencer的正则表达式包:

regexp.shar.Z

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

我想你会遇到一些问题,因为不同的角色在不同的语境中有不同的含义。

^[^a-z][asd-]

这个 ^ 有两种不同的含义,这个词也有两种不同的含义 - .我想我应该选择递归下降解析器。

我不明白为什么不合适。但是,看看一些旧代码,似乎我在上一个regexp解析器中使用了完全不同的解析策略(本质上,从一开始就进行了一次演练,边走边构建生成的自动机表示,通过一些前瞻和递归调用来实现正则表达式的分组)。

我会说,你的问题的答案是“不,你不能用正则表达式实现调车场算法。”这与不能使用正则表达式解析任意HTML的原因相同。这可以归结为:

正则表达式没有堆栈。因为调车场算法依赖于堆栈(在从中缀转换为RPN时推送和弹出操作数),所以正则表达式没有执行此任务的计算“能力”。

这掩盖了许多细节,但“正则表达式”是定义正则语言的一种方法。当你“使用”正则表达式时,你要求计算机说:“看一段文本,告诉我这些字符串中是否有我的语言。我用正则表达式定义的语言。”我要指出 this most excellent answer which you and everyone reading this should upvote 有关常规语言的详细信息。

所以现在你需要一些数学概念来扩充“常规语言”,以创建更强大的语言。如果你将调车场算法描述为计算能力模型的实现,那么你可能会说该算法将被描述为 context-free grammar (嘿,你知道什么,这个链接使用表达式解析树作为例子。)A. push-down automata .有叠的东西。

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

重点是,您可以使用正则表达式来帮助编写调车场。但是regex不太擅长做任意深度的操作,这就是问题所在。所以我不会为了这个问题花太多时间在regex大道上。