पारस्क्रिप्ट अभिव्यक्ति दाएं से बाएं

Question

मैं अभिव्यक्ति के लिए एक पार्सर बना रहा हूं।

expr ::= term (+ expr | - expr | null) 
term ::= expo (* term |/term | null) 
expo ::= factor (^ expo | null) 
factor ::= (expr) | int 

और इसी कोड:

expr :: Parser Int 
expr = do t <- term 
      do _ <- symbol "+" 
      e <- expr 
      return (t + e) 
      <|> do _ <- symbol "-" 
        e <- expr 
        return (t - e) 
        <|> return t 

term :: Parser Int 
term = do ep <- expo 
      do _ <- symbol "*" 
      t <- term 
      return (ep * t) 
      <|> do _ <- symbol "/" 
        t <- term 
        return (ep `div` t) 
        <|> return ep 

expo :: Parser Int 
expo = do f <- factor 
      do _ <- symbol "^" 
      e <- expo 
      return (f^e) 
      <|> return f 

factor :: Parser Int 
factor = do _ <- symbol "(" 
      e <- expr 
      _ <- symbol ")" 
      return e 
      <|> integer 

यह सबसे मामले के लिए अच्छी तरह से काम करता है, लेकिन कुछ के लिए असफल:

$ eval "3*1/3" 

यहाँ मेरी व्याकरण नियम है

3 * 1/3 के बाद से 4 - 3 - 2 के बाद से 3 * (1/3)

(*) 
/\ 
3 (/) 
/\ 
    1 3 

और

$ eval "4-3-2" 

को पार्स किया गया है 4 - (3 - 2)

को पार्स किया गया है

(-) 
/\ 
4 (-) 
/\ 
    3 2 

मुझे एहसास है कि यह पार्सिंग दिशा (सही सहयोगीता) के बारे में सब कुछ है।

मैं क्या उम्मीद जिसका मतलब है कि मैं right-left पार्स और यह व्याख्या left-right (या इसे रिकर्सिवली पार्स) हैं (4 - 3) - 2

(-) 
/\ 
(-) 2 
/\ 
4 3 

है।

मुझे नहीं पता कि इसे कैसे प्राप्त किया जाए। foldl कुछ भी नहीं, लेकिन अब तक मेरे दिमाग में आता है।

क्या कोई सुझाव दे सकता है कि इसे ठीक करने के लिए मुझे क्या करना चाहिए?

कुल कार्यक्रम:

{-# OPTIONS_GHC -Wall #-} 

import Control.Applicative 
import Data.Char 

newtype Parser a = P (String -> [(a, String)]) 

parse :: Parser a -> String -> [(a, String)] 
parse (P p) inp = p inp 

instance Functor Parser where 
    fmap g p = P (\inp -> case parse p inp of 
           []   -> [] 
           [(v, out)] -> [(g v, out)] 
           _   -> undefined) 

instance Applicative Parser where 
    pure v = P (\inp -> [(v, inp)]) 
    pg <*> px = P (\inp -> case parse pg inp of 
           []   -> [] 
           [(g, out)] -> parse (fmap g px) out 
           _   -> undefined) 

instance Monad Parser where 
    p >>= f = P (\inp -> case parse p inp of 
           []   -> [] 
           [(v, out)] -> parse (f v) out 
           _   -> undefined) 

instance Alternative Parser where 
    empty = P (\_ -> []) 
    p <|> q = P (\inp -> case parse p inp of 
           []   -> parse q inp 
           [(v, out)] -> [(v, out)] 
           _   -> undefined) 
    many x = some x <|> pure [] 
    some x = pure (:) <*> x <*> many x 

item :: Parser Char 
item = P (\inp -> case inp of 
         []  -> [] 
         (x : xs) -> [(x, xs)]) 

sat :: (Char -> Bool) -> Parser Char 
sat p = do x <- item 
      if p x 
       then return x 
       else empty 

digit :: Parser Char 
digit = sat isDigit 

char :: Char -> Parser Char 
char x = sat (== x) 

string :: String -> Parser String 
string []  = return [] 
string (x : xs) = do _ <- char x 
        _ <- string xs 
        return (x : xs) 

space :: Parser() 
space = do _ <- many (sat isSpace) 
      return() 

nat :: Parser Int 
nat = do xs <- some digit 
     return (read xs) 

int :: Parser Int 
int = do _ <- char '-' 
     n <- nat 
     return (-n) 
     <|> nat 

token :: Parser a -> Parser a 
token p = do _ <- space 
      v <- p 
      _ <- space 
      return v 

integer :: Parser Int 
integer = token int 

symbol :: String -> Parser String 
symbol = token . string 

expr :: Parser Int 
expr = do t <- term 
      do _ <- symbol "+" 
      e <- expr 
      return (t + e) 
      <|> do _ <- symbol "-" 
        e <- expr 
        return (t - e) 
        <|> return t 

term :: Parser Int 
term = do ep <- expo 
      do _ <- symbol "*" 
      t <- term 
      return (ep * t) 
      <|> do _ <- symbol "/" 
        t <- term 
        return (ep `div` t) 
        <|> return ep 

expo :: Parser Int 
expo = do f <- factor 
      do _ <- symbol "^" 
      e <- expo 
      return (f^e) 
      <|> return f 

factor :: Parser Int 
factor = do _ <- symbol "(" 
      e <- expr 
      _ <- symbol ")" 
      return e 
      <|> integer 

eval :: String -> Int 
eval xs = case (parse expr xs) of 
       [(n, [])] -> n 
       [(_, out)] -> error ("Unused input " ++ out) 
       []   -> error "Invalid input" 
       _   -> undefined 

Answer 1

आप लागू कर सकते हैं इस तरह के पार्सर combinators:

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a 
chainl1 p op = p >>= rest 
    where 
    rest x = do{ f <- op 
       ; y <- p 
       ; rest (f x y) 
       } 
     <|> pure x 

chainr1 :: Parsec a -> Parsec (a -> a -> a) -> Parsec a 
chainr1 p op = scan 
    where 
    scan = p >>= rest 
    rest x = (\f y -> f x y) <$> op <*> scan <|> pure x 

तो फिर तुम इस तरह अपने व्याकरण के नियमों को लागू कर सकते हैं:

expr = term `chainl1` addop 
term = expo `chainl1` mulop 
expo = factor `chainr1` expop 
factor = parens expr <|> integer 

addop = (+) <$ symbol "+" <|> (-) <$ symbol "-" 
mulop = (*) <$ symbol "*" <|> (div) <$ symbol "/" 
expop = (^) <$ symbol "^" 

parens p = symbol "(" *> p <* symbol ")" 

लेकिन मैं आपको सलाह देते हैं पैकेज पारसी जैसे पार्सर लाइब्रेरी का उपयोग करने के लिए।