नियमित अभिव्यक्तियों को पार्स करने के लिए पारसेक का उपयोग

Question

मैं एक छोटे से नियमित अभिव्यक्ति पार्सर को लागू करके पारसी सीखने की कोशिश कर रहा हूं। > स्टार - -> 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:

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 के साथ अच्छा नहीं खेलता है, क्योंकि पारसेक बार-बार बैकट्रैक करेगा। इसके आसपास कुछ तरीके हैं। शायद सबसे सरल सिर्फ * एक और नियम में वैकल्पिक बना रही है:

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

बेशक

, तो आप शायद वैसे भी एक डेटा प्रकार में चीजों को लपेटकर खत्म कर देंगे, और तरीके से इसके बारे में जाने के लिए की एक बहुत कुछ कर रहे हैं। यहां एक है, मेरे सिर के ऊपर से:

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 

शायद एक और अनुभवी हास्केलर बेहतर समाधान के साथ आएगा।