右から左へ構文解析

Question

私は式のパーサーを構築しています。

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

と対応するコード：

$ eval "3*1/3" 

：

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 

それは確かに失敗するほとんどの場合に適していますが、

は、ここに私の文法規則です

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

あなたはこれらのようなパーサコンビネータを実装できます。

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

をしかし、私はあなたをお勧めしますパッケージparsecのようなパーサライブラリを使用する。