正則表達式詞法分析

爲什麼重複的字符串如 [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

正則表達式詞法分析

回答

相關問題