正規表現エンジン(失敗)

Haskell 30分プログラム Haskell

30分プログラム、その69。
正規表現をパースしようとして失敗した。

*Main> parseRegexp "A"
[Char 'A']
*Main> parseRegexp "ABC"
[Char 'A',Char 'B',Char 'C']
*Main> parseRegexp "A*"
[Many (Char 'A')]
*Main> parseRegexp "ABC*"
[Char 'A',Char 'B',Many (Char 'C')]
*Main> parseRegexp "(ABC)*"
*** Exception: "regexp" (line 1, column 3):
unexpected "B"
expecting ")"

import Text.ParserCombinators.Parsec

data Regexp = Char Char -- A
	    | Select Regexp Regexp -- F | G
	    | Connect [Regexp] -- FG
	    | Many Regexp -- F*
              deriving Show

-- parser 
pRegexp =  try pMany <|> pAtom

pAtom = pChar <|> pParen
pParen = do char '('
            r <- pRegexp
            char ')'
            return r
pChar = do c <- letter <|> digit
           return $ Char c

pMany = do r <- pAtom
           char '*'
           return $ Many r
pMain = do x <- many pRegexp;eof;return x

parseRegexp s = case parse pMain "regexp" s of
                  Left err -> error $ show err
                  Right val -> val
  • 正規表現のパースが意外と難しい。少くとも、正則言語のクラスには入ってないよなぁ
  • 本当にLL(k)でできるのかしら
  • ぬぉぉ。インデントがずれとる