2015-03-19 112 views
0

我正在編寫一個編譯器。我剛開始,所以我正在創建掃描儀(或Lexer)。目前,我正在編寫一些將由我的掃描儀處理的常規定義。力圖打造他們中的一個,我的下一個問題運行:正則表達式 - 奇怪的行爲

我的測試,在RegExr,以下(非常簡單)的正則表達式:

r = /(a|ab)/ 

其中「R」是一個普通的定義;我的意思是,正則表達式只是(a|ab)

我認爲語言L(R)將是(按書Compilers: Principles, Techniques and Tools):

L(r) = {a, ab} 

出人意料的是,該工具相匹配{a}

所以我的問題是,爲什麼會這樣?

+0

在正則表達式中'''是一個交流發電機,即你的正則表達式將匹配'a'或'ab'。你想讓它匹配'a' _跟着by_'ab'嗎? – 2015-03-19 13:12:18

+0

嗨@JamesThorpe,其實我不想「找到」正則表達式。我在尋找的是理解上述奇怪的行爲。 – 2015-03-19 13:14:38

回答

2

正則表達式a|ab匹配「a」或「AB」(明顯),但一些工具/語言(如Java的)考慮輸入時整個輸入正則表達式匹配來匹配,而其他(如JavaScript)的考慮輸入匹配時的一些匹配。

您的工具必​​須是「一些」品種以匹配「{a}」。

+0

你知道一個像Java正則表達式工具一樣的在線工具嗎? – 2015-03-19 13:23:03

+0

@LeonardoManrique不,但你可以通過在前面添加'^'並且在末尾添加'$'來實現它,例如'^ a | ab $'。順便說一句你的正則表達式相當於'ab?' – Bohemian 2015-03-19 14:11:38

+0

你是指lexem?如果是這樣,我不想將一個lexem與一個模式相匹配,我只是設計了常規定義。當我嘗試使用該工具時,我用我們一直在討論的「錯誤」來運行。如果你正在引用正則表達式本身,它就相當於'a'。 – 2015-03-19 15:16:23

1

正則表達式從左到右解析文本,如果是交流發電機(|),它將首先瞄準與第一個候選人匹配。

如果你使用:

(ab|a) 

將同時匹配aba的。

問題是,一旦找到匹配,全局匹配器將在第一次匹配結束後開始下一個匹配嘗試

您可以輕鬆驗證匹配的語言是{a,ab}:使用正則表達式^c(a|ab)d並使用cabd。在這種情況下,正則表達式別無選擇,只能選擇第二個選項。

所以說正則表達式如下:(a|ab)和文本是ab。它將與a相匹配,接下來將在a之後開始,因此它將嘗試與b匹配,但失敗。

然而,大多數詞法分析器工具使用不同的方法來確定匹配。對於詞法分析器工具,「最長匹配」是重要的。所以匹配的字符數最長。

現在,如果您輸入(a|ba)作爲正則表達式,它將與之前的ba匹配。爲什麼?因爲它也旨在找到第一次嘗試。並且在文本cbad中,從索引1b)開始被認爲比起始於索引2a)更好。

+0

嗨CommuSoft。是的,你有權利,但如果我寫這個正則表達式:(a | ba),該工具匹配{a,ba}。 – 2015-03-19 13:16:18

+0

@LeonardoManrique:它匹配buth。如果你使用'^(a | ab)$'並且匹配'ab',它將匹配。 – 2015-03-19 13:17:08

+1

@LeonardoManrique:抱歉,您的評論錯了,請參閱修改後的答案。 – 2015-03-19 13:20:33

0

正如所說的@bohemian如果你想整個字符串匹配,你可以使用這樣的正則表達式正則表達式的一些評估只是一個字符串的一部分:

/^(a|ab)$/ 

其中僅接受一個ab