Temel İfade Ayrıştırıcısındaki Sol Özyineyi Kaldırma

Question

Bir alıştırma olarak, aşağıdaki GADT'yi kullanarak Haskell'de tanımlanan son derece basit bir dil için bir ayrıştırıcı uygulayacağım (projem için gerçek dilbilgisi birçok ifadeyi içerir, ancak bu özüt yeterlidir sorusuna) için: aşağıdaki gibi

data Expr a where 
    I :: Int -> Expr Int 
    Add :: [Expr Int] -> Expr Int 

ayrıştırma fonksiyonları şunlardır: nedeniyle kullanıyorum 1+1 kadar basit bir şeyi ayrıştırmak girişiminde ifade dilbilgisi sol özyinelemeli yapısı nedeniyle

expr :: Parser (Expr Int) 
expr = foldl1 mplus 
    [ lit 
    , add 
    ] 

lit :: Parser (Expr Int) 
lit = I . read <$> some digit 

add :: Parser (Expr Int) 
add = do 
    i0 <- expr 
    is (== '+') 
    i1 <- expr 
    is <- many (is (== '+') *> expr) 
    pure (Add (i0:i1:is)) 

expr ayrıştırıcı, ayrıştırıcı sonsuz bir döngüde sıkışmış olsun.

Ben böyle bir şey gelen bir dönüşümü kullanılarak web üzerinde sol özyinelemeye faktörü dışında nasıl örneklerini gördük

: gibi bir şey içine

S -> S a | b 

:

S -> b T 
T -> a T 

Ama birlikte mücadele ediyorum Bunu çözümleyicime nasıl uygularım.

newtype Parser a = Parser 
    { runParser :: String -> [(a, String)] 
    } 

instance Functor Parser where 
    fmap f (Parser p) = Parser $ \s -> 
     fmap (\(a, r) -> (f a, r)) (p s) 

instance Applicative Parser where 
    pure a = Parser $ \s -> [(a, s)] 
    (<*>) (Parser f) (Parser p) = Parser $ \s -> 
     concat $ fmap (\(f', r) -> fmap (\(a, r') -> (f' a, r')) (p r)) (f > 

instance Alternative Parser where 
    empty = Parser $ \s -> [] 
    (<|>) (Parser a) (Parser b) = Parser $ \s -> 
     case a s of 
     (r:rs) -> (r:rs) 
     []  -> case b s of 
        (r:rs) -> (r:rs) 
        []  -> [] 

instance Monad Parser where 
    return = pure 
    (>>=) (Parser a) f = Parser $ \s -> 
     concat $ fmap (\(r, rs) -> runParser (f r) rs) (a s) 

instance MonadPlus Parser where 
    mzero = empty 
    mplus (Parser a) (Parser b) = Parser $ \s -> a s ++ b s 

char = Parser $ \case (c:cs) -> [(c, cs)]; [] -> [] 
is p = char >>= \c -> if p c then pure c else empty 
digit = is isDigit 

Answer 1

Eğer değişmezleri, toplama ve çarpma içeren olmayan parantez ifadeleri ayrıştırmak istediğinizi varsayalım:

tamlığı için buraya aslında çözümleyici uygular koddur. Bunu önceliğe göre listeyi azaltarak yapabilirsiniz. Burada, çözümleyicinizle ne yapacağınıza oldukça benzeyen attoparsec'da yapmanın bir yolu var. Ayrıştırma uzmanı değilim, bu yüzden bazı hatalar veya eksiklikler olabilir.

import Data.Attoparsec.ByteString.Char8 
import Control.Applicative 

expr :: Parser (Expr Int) 
expr = choice [add, mul, lit] <* skipSpace 
-- choice is in Data.Attoparsec.Combinators, but is 
-- actually a general Alternative operator. 

add :: Parser (Expr Int) 
add = Add <$> addList 

addList :: Parser [Expr Int] 
addList = (:) <$> addend <* skipSpace <* char '+' <*> (addList <|> ((:[]) <$> addend)) 

addend :: Parser (Expr Int) 
addend = mul <|> multiplicand 

mul :: Parser (Expr Int) 
mul = Mul <$> mulList 

mulList :: Parser [Expr Int] 
mulList = (:) <$> multiplicand <* skipSpace <* char '*' <*> (mulList <|> ((:[]) <$> multiplicand)) 

multiplicand :: Parser (Expr Int) 
multiplicand = lit 

lit :: Parser (Expr Int) 
lit = I <$> (skipSpace *> decimal)