blocks|key|1864249|text|我很肯定它可以。如果您查看Henry的正则表达式包：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1864250|regexp.shar.Z|offset|length|1864251|这是Perl正则表达式的基础，您会注意到，他将该程序描述为“铁路正常形式”。|1864252|entityMap|0|LINK|mutability|MUTABLE|url|ftp://ftp.cs.toronto.edu/pub/regexp.shar.Z^0|0|0|D|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

I'm fairly sure it can. If you look at Henry Spencer's regular expression package:

<a href="ftp://ftp.cs.toronto.edu/pub/regexp.shar.Z" rel="nofollow">regexp.shar.Z</a>

which was the basis for Perl's regular expressions, you will notice that he describes the program as being in "railroad normal form".

blocks|key|666001|text|我想你会有一些问题，因为不同的字符在不同的上下文中有不同的含义。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|666002|%5E[%5Ea-z][asd-]|code-block|syntax|javascript|666003|%5E有两个不同的含义，-也是如此。我想我会选择一个递归下降解析器。|offset|length|style|CODE|666004|entityMap^0|0|0|0|1|A|1|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]|$I|T|J|U|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|N|$]]

I reckon you'd have some problems because different characters have different meanings in different contexts e.g.

<pre><code>^[^a-z][asd-]
</code></pre>

The <code>^</code> has two different meanings and so does the <code>-</code>. I think I'd choose a recursive descent parser.

blocks|key|2219765|text|我不明白为什么不合适。但是，看看一些旧代码，似乎我对上一个regexp解析器使用了完全不同的解析策略(从本质上讲，从一开始就走了一步，一边构建生成的自动机表示，一边使用一些前瞻性调用和递归调用来实现正则表达式分组)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2219766|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I don't see why it wouldn't be suitable. Looking at some old code, it does seem I used a completely different parsing strategy for my last regexp parser, however (essentially, a walk-through from the start, building the resulting automaton representation as you go, with some look-ahead and recursive calls to implement grouping of regular expressions).

blocks|key|2219737|text|我会说，你的问题的答案是“不，你不能用正则表达式实现分流码算法。”这与不能使用正则表达式解析任意HTML的原因相同。可以归结为：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2219738|正则表达式没有堆栈。因为分流码算法依赖于堆栈(在从infix转换到RPN时推和弹出操作数)，所以正则表达式没有执行此任务的计算“能力”。|2219739|这掩盖了许多细节，但“正则表达式”是定义规则语言的一种方法。当你“使用”一个正则表达式时，你要求计算机说：“看看一堆文本，告诉我这些字符串中是否有我的语言。我用正则表达式定义的语言。”有关常规语言的更多信息，我将指向这是你和每一个读到这篇文章的人都应该投赞成票的最好答案。。|offset|length|2219740|因此，现在您需要一些数学概念来增强“常规语言”，以创建更强大的语言。如果您要将分流码算法描述为计算能力模型的实现，那么您可能会说该算法将被描述为一个上下文无关语法+(您知道什么，该链接使用表达式解析树作为示例)。一个下推自动机。一堆东西。|2219741|如果你对自动机理论和复杂性类不太熟悉，那么这些维基百科的文章如果不从根本上解释它们，可能就没有多大帮助。|2219742|关键是，你可以使用regex来帮助编写调车场。但是regex并不擅长执行任意深度的操作，这个问题就是如此。因此，我不会花太多时间在regex大道上处理这个问题。|2219743|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/1085404/what-is-regular-expression/1085469#1085469|1|http://en.wikipedia.org/wiki/Context_free_grammar|2|http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton^0|0|0|30|S|0|0|22|7|1|30|5|2|0|0|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|10|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|11|8|@]|9|@$F|12|G|13|1|14]]|A|$]]|$1|H|3|I|5|6|7|15|8|@]|9|@$F|16|G|17|1|18]|$F|19|G|1A|1|1B]]|A|$]]|$1|J|3|K|5|6|7|1C|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1D|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|1E|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|U]]|V|$5|Q|R|S|A|$T|W]]|X|$5|Q|R|S|A|$T|Y]]]]

I will say that the answer to your question is "no, you cannot implement the shunting yard algorithm using a regular expression." This is for the same reason you cannot parse arbitrary HTML using regular expressions. Which boils down to this:

Regular expressions do not have a stack. Because the shunting yard algorithm relies on a stack (to push and pop operands as you convert from infix to RPN), then regular expressions do not have the computational "power" to perform this task.

This glosses over many details, but a "regular expression" is one way to define a regular language. When you "use" a regular expression, you are asking the computer to say: "Look at a body of text and tell me whether or not any of those strings are in my language. The language that I defined using a regular expression." I'll point to <a href="https://stackoverflow.com/questions/1085404/what-is-regular-expression/1085469#1085469">this most excellent answer which you and everyone reading this should upvote</a> for more on regular languages.

So now you need some mathematical concept to augment "regular languages" in order to create more powerful languages. If you were to characterize the shunting yard algorithm as an realization of a model of computational power, then you might say that the algorithm would be described as a <a href="http://en.wikipedia.org/wiki/Context_free_grammar" rel="nofollow noreferrer">context-free grammar</a> (hey what do you know, that link uses an expression parse tree as an example.) A <a href="http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton" rel="nofollow noreferrer">push-down automata</a>. Something with a stack.

If you are less-than-familiar with automata theory and complexity classes, then those wikipedia articles are probably not that helpful without explaining them from the ground up.

The point being, you may be able to use regex to help writing shunting yard. But regex are not very good at doing operations that have an arbitrary depth, which this problem has. So I would not spend too much time going down the regex avenue for this problem.

At first glance, the <a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="noreferrer">shunting yard algorithm</a> seems applicable to POSIX regular expression parsing, but since I don't have much experience (or theoretical background) in writing parsers, I'd like to ask SO before jumping in and writing something only to get stuck halfway.

Perhaps a more sophisticated version of the question is: What is a good formal statement of the class of problems the shunting yard algorithm can be applied to?

Clarification: This question is about whether you can parse POSIX re syntax into an abstract syntax tree using the basic principles of the shunting algorithm, not whether you can use regular expressions to implement the shunting algorithm. Sorry I wasn't clear enough stating that to begin with!

Can the shunting yard algorithm parse POSIX regular expressions?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

乍一看，似乎适用于POSIX正则表达式解析，但由于我在编写解析器方面没有多少经验(或理论背景)，所以我想在跳进去写东西之前问一问。也许这个问题的一个更复杂的版本是:对调车场算法可以应用的问题类别的一个好的正式陈述是什么？Clarification:这个问题是关于是否可以使用分流算法的基本原理将POSIX语法解析为抽象语法树，而不是是否可以使用正则表达式来实现分流算法。对不起，我一开始说的还不够清楚

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

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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