Używanie Parsera do parsowania wyrażeń regularnych

Question

Próbuję nauczyć się Parsec przez zaimplementowanie małego parsera wyrażeń regularnych. W BNF, moja gramatyka wygląda mniej więcej tak:

EXP : EXP * 
    | LIT EXP 
    | LIT 

Próbowałem zaimplementować to w Haskell jak:

expr = try star 
     <|> try litE 
     <|> lit 

litE = do c <- noneOf "*" 
      rest <- expr 
      return (c : rest) 

lit = do c <- noneOf "*" 
      return [c] 

star = do content <- expr 
      char '*' 
      return (content ++ "*") 

Istnieją pewne nieskończone pętle tutaj chociaż (np expr -> star -> wyrażenie bez zużywania żadnych tokenów), co sprawia, że ​​pętla parsera trwa wiecznie. Naprawdę nie jestem pewien, jak to naprawić, ponieważ z natury star wynika, że ​​zużywa on swój obowiązkowy token na końcu.

Jakieś myśli?

Answer 1

Powinieneś użyć Parsec.Expr.buildExprParser; jest idealny do tego celu. Po prostu opisujesz swoich operatorów, ich pierwszeństwo i powiązanie oraz jak analizować atom, a kombinator buduje dla ciebie parser!

Prawdopodobnie chcesz również dodać możliwość grupowania terminów z parens, aby móc zastosować * do więcej niż jednego literału.

Oto moja próba (wrzuciłem w |, + i ? na dokładkę):

import Control.Applicative 
import Control.Monad 
import Text.ParserCombinators.Parsec 
import Text.ParserCombinators.Parsec.Expr 

data Term = Literal Char 
      | Sequence [Term] 
      | Repeat (Int, Maybe Int) Term 
      | Choice [Term] 
    deriving (Show) 

term :: Parser Term 
term = buildExpressionParser ops atom where 

    ops = [ [ Postfix (Repeat (0, Nothing) <$ char '*') 
      , Postfix (Repeat (1, Nothing) <$ char '+') 
      , Postfix (Repeat (0, Just 1) <$ char '?') 
      ] 
     , [ Infix (return sequence) AssocRight 
      ] 
     , [ Infix (choice <$ char '|') AssocRight 
      ] 
     ] 

    atom = msum [ Literal <$> lit 
       , parens term 
       ] 

    lit = noneOf "*+?|()" 
    sequence a b = Sequence $ (seqTerms a) ++ (seqTerms b) 
    choice a b = Choice $ (choiceTerms a) ++ (choiceTerms b) 
    parens = between (char '(') (char ')') 

    seqTerms (Sequence ts) = ts 
    seqTerms t = [t] 

    choiceTerms (Choice ts) = ts 
    choiceTerms t = [t] 

main = parseTest term "he(llo)*|wor+ld?" 

Answer 2

Twoja gramatyka jest lewostronna, co nie jest miłe z try, ponieważ Parsec będzie wielokrotnie cofać się. Jest na to kilka sposobów. Prawdopodobnie najprostszym jest tylko czyniąc * opcjonalnie w innej zasady:

lit :: Parser (Char, Maybe Char) 
lit = do 
    c <- noneOf "*" 
    s <- optionMaybe $ char '*' 
    return (c, s) 

Oczywiście, będziesz prawdopodobnie skończyć owijania rzeczy w rodzaju danych i tak, i istnieje wiele sposobów, aby przejść o nim. Oto jeden, od początku mojej głowy:

import Control.Applicative ((<$>)) 

data Term = Literal Char 
      | Sequence [Term] 
      | Star Term 

expr :: Parser Term 
expr = Sequence <$> many term 

term :: Parser Term 
term = do 
    c <- lit 
    s <- optionMaybe $ char '*' -- Easily extended for +, ?, etc. 
    return $ if isNothing s 
    then Literal c 
    else Star $ Literal c 

Może bardziej doświadczony Haskeller będzie miał lepsze rozwiązanie.