Biểu thức phân tích cú pháp từ phải sang trái

Question

Tôi đang tạo trình phân tích cú pháp cho biểu thức.

Dưới đây là quy tắc của tôi ngữ pháp:

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

và mã tương ứng:

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 

Nó hoạt động tốt đối với trường hợp nhất nhưng không chắc chắn:

$ eval "3*1/3" 

từ 3 * 1/3 được phân tách để 3 * (1/3)

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

và

$ eval "4-3-2" 

từ 4 - 3 - 2 được phân tách để 4 - (3 - 2)

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

Tôi nhận ra đó là tất cả về hướng phân tích cú pháp (kết hợp phải).

Những gì tôi mong đợi là (4 - 3) - 2

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

có nghĩa là tôi sẽ phân tích right-left và giải thích nó left-right (hoặc phân tích nó một cách đệ quy).

Tôi không biết làm thế nào để đạt được điều đó. Không có gì, nhưng foldl đến với tâm trí của tôi cho đến nay.

Ai đó có thể đề xuất tôi nên làm gì để khắc phục sự cố?

tổng chương trình:

{-# 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

Bạn có thể thực hiện combinators phân tích cú pháp như thế này:

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 

Sau đó, bạn có thể thực hiện quy tắc ngữ pháp của bạn như thế này:

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

Nhưng tôi khuyên bạn nên sử dụng thư viện phân tích cú pháp như gói parsec.