正则表达式词法分析

为什么重复的字符串如 [wcw | w是a和b的字符串] 不能用正则表达式表示？给我详细的答案，因为我是词汇分析的新手。谢谢...正则表达式词法分析

2009-03-05 paragjain

记住，解析是我参加了研究生院（编译I）最难的课程之一的主要议题。已经有相当不错的答案，但您可能没有背景可以使用它。 – 2009-03-05 20:54:47

好吧，这并不容易。但有时候，至少它很有趣。尽管这里包括了优化以及超越解析的几种算法。任何想法如何使这个帖子更清楚的人没有太多的背景？ - 。 - – Joey 2009-03-05 21:43:10

正则表达式描述正规语言/语法。那些不能包含嵌套结构的语言可以用简单的有限状态机来描述。简化后，您可以看到，语言中的每个词都严格按照从左到右（或从右到左）的方向生长，其中重复结构必须明确定义并且是静态的。

这意味着，没有从先前的状态信息任何可以（在输入进一步几个字符）结转以后的状态。所以如果你有你的符号w你不能指定输入必须具有完全相同的字符串w后面的序列。同样，你不能保证每个开口paranthesis需要closin括号以及（所以正则表达式本身，甚至没有一个正规的语言，因此无法用正则表达式:-)描述）。

在我们有非常严格的一套regex操作符的工作理论计算机科学，基本上只包括序列，替代（|）和重复（*），其他的一切可以用这些操作进行说明。

然而，通常正则表达式引擎允许的某些子图案分组为随后可被引用的或以后提取匹配。一些引擎甚至允许在搜索表达式字符串本身中使用这样的反向引用，从而允许表达式不仅仅描述常规语言。如果我没有记错的话，这种反向引用的使用甚至可以产生没有上下文的语言。

其他指针：

This的StackOverflow问题
Wikipedia

来源

2009-03-05 20:18:05 Joey

它可以，你不能保证它的相同串的“一个” S和“b”是因为没有办法保留在遍历上半年获得的信息用于遍历第二个。在他们的原始形式

来源

2009-03-05 20:04:29 MarkusQ

正则表达式词法分析

回答

相关问题