Parsecを使って正規表現を解析する

Question

私は小さな正規表現パーサーを実装してParsecを学習しようとしています。 >スター - - > 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 ++ "*") 

いくつかの無限ループがここにありますが（例えば式expr：私のようにHaskellでこれを実装しようとした

EXP : EXP * 
    | LIT EXP 
    | LIT 

：BNFでは、私の文法は何かのように見えますトークンを消費することなく）、パーサーループを永久にループさせます。 starの本質は、最後に必須のトークンを消費するためです。

どのような考えですか？

Answer 1

Parsec.Expr.buildExprParserを使用してください。この目的には理想的です。演算子、優先順位、結合性、および原子の解析方法を記述するだけで、コンビネータはパーサーを構築します。

*を単一のリテラル以上に適用できるように、用語を括弧でグループ化する機能を追加することもできます。私はあなたが正しいと確信しているが、私はなぜ理解していない

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

あなたの文法は左回帰です。これは、tryでうまくいきません.Parsecは繰り返し戻ってくるでしょう。これにはいくつかの方法があります。おそらく最も簡単なだけで別のルールで*はオプション作っている：もちろん

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

、あなたはおそらく、とにかくデータ型で物事をラップ終わるだろう、とそれについて移動する方法はたくさんあります。私の頭の上から1つ、ここにある：

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 

多分、より経験豊かなハスケラーがよりよい解決策になるだろう。