使用哈斯克爾秒差距在一通解析正則表達式

Question

我試圖做一些測試與自定義正則表達式引擎，但我厭倦了手工出寫的NFA的初步解釋，所以我試着讓一個解析器成功一點點。通常當人們解析一個正則表達式時，他們會創建多箇中間結構，最終轉換成最終的機器。對於我簡單的NFA定義，我相信解析實際上可以一次完成，儘管我還沒有確定（a）爲什麼它實際上不能或（b）怎麼做，雖然我的解析器可以解析非常簡單聲明。

的（簡化的）狀態的實體一樣定義，以便[1]：

type Tag = Int 

data State a = 
    Literal Tag a (State a) 
    | Split (State a) (State a) 
    | OpenGroup Tag (State a) 
    | CloseGroup Tag (State a) 
    | Accept      -- end of expression like "abc" 
    | Final      -- end of expression like "abc$" 

的標籤，以允許顯示和等式實例即使最終NFA可包含週期。例如，爲了表達

-- "^a+(b*)c$" 

我可以通過移植C實現用[2]

c = Literal 3 'c' $ Final 1 
b = OpenGroup 1 $ Literal 2 'b' bs 
bs = Split b $ CloseGroup 1 c 
expr = Literal 1 'a' $ Split expr bs 

我製成的運作基於堆棧的機器解析器此語法（SAN的組標籤）進行建模的Thompson NFA實現到Haskell，但這需要兩次通過[3]來構建，並且需要三分之一才能以上述結構結束。

因此構建經秒差距這個結構，我讀到遞歸建立一個列表狀結構本網站上的條目，並想出了以下內容：

import   Control.Applicative 
import   Text.Parsec   hiding (many, optional, (<|>)) 
import   Text.ExpressionEngine.Types 
import qualified Text.ExpressionEngine.Types as T 

type ParserState = Int 
type ExpParser = Parsec String ParserState 
type ExpParserS a = ExpParser (T.State a) 

parseExpression :: String -> T.State Char 
parseExpression e = case runParser p 1 e e of 
    Left err -> error $ show err 
    Right r -> r 
where 
    p = p_rec_many p_char $ p_end 1 

p_rec_many :: ExpParser (T.State a -> T.State a) -> ExpParserS a -> ExpParserS a 
p_rec_many p e = many' 
    where 
    many' = p_some <|> e 
    p_some = p <*> many' 

p_end :: Int -> ExpParserS a 
p_end n = (Final n <$ char '$') <|> (Accept n <$ eof) 

step_index :: ExpParser Int 
step_index = do 
    index <- getState 
    updateState succ 
    return index 

p_char = do 
    c <- noneOf "^.[$()|*+?{\\" 
    i <- step_index 
    return $ Literal i c 

有一點是可以充分解析字符串像「ab」和「abc $」[4]。

問題

當我下一步的問題就來了：解析「|」或陳述。這應該工作的方式是，一個字符串，如：

-- "(a|b|c)$" 

應該創建以下結構：

final = Final 1 
c = Literal 3 'c' final 
b = Split (Literal 2 'b' final) c 
a = Split (Literal 1 'a' final) b 

因此，這意味着，將建立或聲明必須經過它自帶的另一種表達解析器並將其傳遞給所有分支（我不相信將Split改爲列表會改變任何內容，因爲每個條目都必須接收相同的下列表達式）。我的嘗試是：

p_regex :: T.State Char -> ExpParser (T.State Char) 
p_regex e = do 
    first <- p_rec_many p_char $ pure e 
    (Split first <$> (char '|' *> p_regex e)) <|> return first 

和主解析器變化：

parseExpression :: String -> T.State Char 
parseExpression e = case runParser p 1 e e of 
    Left err -> error $ show err 
    Right r -> r 
    where 
    p = p_regex <*> p_end 1 

但這未能類型檢查[5]。我希望這是正確的，因爲p_regex必須有一個構建的（State a）對象，並且使用p_rec_many構建「Literal」鏈似乎也可以這樣工作。

也許我應該使用buildExpressionTable？這可能有助於解決這個特定問題，因爲我可以將（'$'< |> eof）作爲最高優先級。我開始嘗試它，但我無法想象我將如何處理諸如明星加號和問號運算符之類的事情，因爲這些都必須引用自己。 （編輯：我再次嘗試buildExpressionTable，它在我看來，它是太簡單了，我想做什麼。它不能本地處理堆疊後綴運算符[例如「a？*」]，和我的計劃是讓$'< |> eof「最高優先級將不起作用，因爲它只會附加到最後解析的'term'，而不是整個字符串。即使我可以這樣做，'$ 「運營商將反向應用：它應該是最後解析的詞，並輸送到前面的術語我這個工作，我就越想知道如果我不應該只是分析前反向表達串越）

。

問題

那麼，我做錯了什麼？我確信有一種方法可以做我想做的事情，但到目前爲止我還沒有弄明白。感謝您的時間。

腳註

[1]如果你想看到什麼我真正使用它可以發現here。

[2]爲打開/ CloseGroup標籤的想法是跟蹤而NFA運行組相匹配。列出的表達式中的位置可能不完全正確，但如果遇到CloseGroup標記，只有在找到相應的OpenGroup時纔會創建捕獲組，則此方法將正常工作（即，在上例中，如果至少有一個'b'被看到）。

所有其它標記建設是正確的，我測試過，這個NFA預期相匹配的字符串。

[3]湯普森的實現描述爲here，我的端口可以看到here。這完美地構建了NFA子集，但是在所產生的結構中，每個下一個狀態都將被包裝在一個Just中。這是因爲我使用Nothing來表示懸掛指針，並且稍後的步驟將在正確的下一步中進行修補。我可以通過將所有（Just狀態）條目轉換爲（狀態）條目來將此結構轉換爲上面列出的結構，但這將是第三遍。這個實現已經需要第一遍將正則表達式轉換爲後綴表示法。

[4]在

Literal 1 'a' (Literal 2 'b' (Accept 1)) 

和

Literal 1 'a' (Literal 2 'b' (Literal 3 'c' (Final 1))) 

分別得到的。

[5]

Couldn't match expected type `a0 -> b0' 
     with actual type `ExpParser (T.State Char)' 
Expected type: T.State Char -> a0 -> b0 
Actual type: T.State Char -> ExpParser (T.State Char) 
In the first argument of `(<*>)', namely `p_regex' 
In the expression: p_regex <*> p_end 1 

Answer 1

好了，所以問題是基本上是：給定一個遞歸數據結構（在這個問題中定義）如何可以創建一個解析器，將建立在一次通過我的表達。我最初的嘗試本質上是「適用的」。如果沒有條件分支，我可以構建遞歸結構。但對於正則表達式解析，需要分支，這就是爲什麼我的方法不適用於or語句。

因此，要解決這個問題，我需要有一些狀態。在功能語言中攜帶狀態的好方法是部分應用功能。我已經爲這個基地在上面p_char的簽名是：

p_char :: ExpParser (T.State Char -> T.State Char) 

所以我需要將它們結合起來是組成多個(T.State Char -> T.State Char)功能一起組合程序。因此，有了這種認識，排序變爲：

p_many1 :: ExpParser (T.State Char -> T.State Char) -> ExpParser (T.State Char -> T.State Char) 
p_many1 p = do 
    f <- p 
    (p_many1 p >>= return . (f .)) <|> return f 

現在爲or聲明我們所需要的是什麼，需要一個表達，如「A | B | C」，並創建一個功能，如：

\e -> Split (Literal 1 'a' e) (Split (Literal 2 'b' e) (Literal 3 'c' e)) 

所以要做到這一點，我們可以用這個：

p_splitBy1 :: ExpParser (T.State Char -> T.State Char) -> Parsec String ParserState Char -> ExpParser (T.State Char -> T.State Char) 
p_splitBy1 p sep = do 
    f <- p 
    (sep >> p_splitBy1 p sep >>= return . (\f' e -> Split (f e) (f' e))) <|> return f 

這確實創建了我需要的結構。所以如果其他人將來遇到類似的問題，也許這個問題/答案可能是有用的。

Answer 2

你可能不會得到很多答案，因爲這是一個巨大的問題，這需要讀取一個巨大的文件之前，任何人都可以想一想書面答覆。

話雖如此，由反常的巧合，我只是碰巧是想這周成建從正則表達式自己的NFA。;-)

---

OK，所以立即問題是

Couldn't match expected type `x -> y` with actual type `Parser`. 

在英語中，這意味着什麼地方你有一個函數，而不是一個解析器。在你的代碼快速瀏覽表明，你已經寫

where 
    p = p_regex <*> p_end 1 

但p_regex需要1個參數，並且您還沒有提供一個。 那就是爲什麼你的代碼不能進行類型檢查。

---

OK，所以退一步，什麼是您的實際問題？你想要將一個正則表達式解析成NFA，但是這篇文章希望你將正則表達式轉換爲後綴表示法，然後解析它，然後構建NFA？

它看起來像它應該是可能的。當我執行此操作時，我將解析和NFA生成作爲單獨的步驟進行，純粹是爲了檢查解析器的工作原理以及NFA生成是否單獨運行。但這聽起來應該是可能的。 Parsec允許您擁有用戶狀態，因此您可以將其用作堆棧來存儲NFA片段。 （或者明確地傳遞它身邊，如果你喜歡。）

如果你想要一個更確切的答案，你可能會需要修剪下來到一個更小，更集中的問題。