Düzenli ifadeleri ayrıştırmak için Parsec kullanma

Question

Parsec'i küçük bir normal ifade ayrıştırıcısı uygulayarak öğrenmeye çalışıyorum. > Yıldız - -> expr

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 ++ "*") 

bazı sonsuz döngüler var burada olsa (örneğin İfade: Ne kadar Haskell bu uygulamaya çalıştık

EXP : EXP * 
    | LIT EXP 
    | LIT 

: BNF, benim dilbilgisi şey gibi görünüyor ayrıştırıcı döngüsünü sonsuza kadar yapan herhangi bir belirteç tüketmeden). Ancak, bunun nasıl düzeltileceğinden emin değilim, çünkü star'un doğası, zorunlu jetonunu en sonunda tükettiğidir.

Herhangi bir düşünce?

Answer 1

Parsec.Expr.buildExprParser; bu amaç için idealdir. Sadece operatörlerinizi, bunların önceliklerini ve ilişkilerini ve bir atomu nasıl ayrıştıracağınızı ve birleştiricinin sizin için ayrıştırıcıyı nasıl oluşturduğunu anlatabilirsiniz!

Büyük olasılıkla, *'u yalnızca bir değişmezden daha fazlasına uygulayabilmeniz için, terimleri gruplarla gruplama özelliğini de eklemek istersiniz. Haklı olduğuna eminim, ama nedenini anlamıyorum

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

Dilbilginiz, tekrar tekrar geriye dönecek şekilde, try ile birlikte çalınamayan sola dönüşlüdür. Bunun etrafında birkaç yol var. Muhtemelen en basit sadece başka kuralda * opsiyonel yapıyor: Elbette

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

, muhtemelen yine bir veri türü şeyler sarma bitireceğiz, ve bu konuda gitmek için pek çok yolu vardır. İşte başımın üstü kapalı, bir tane:

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 

Belki daha tecrübeli Haskeller daha iyi bir çözüm ile birlikte gelecek.