Parsec.Expr ripetuto prefisso con priorità differenti

Question

La documentazione per Parsec.Expr.buildExpressionParser dice:

prefisso e suffisso operatori con la stessa precedenza può avvenire solo una volta (cioè --2 non è consentito se - è prefisso negato).

Tuttavia, vorrei analizzare tali stringhe.

In concreto, si consideri la seguente grammatica:

sentence: 
    | identifier 
    | "~" sentence 
    | sentence & sentence 
    | "!" sentence 

Dove precedenza degli operatori è: "~" si lega più forte di "&" si lega più forte di "!"

Per esempio, vorrei la frase

! ~a & b 

da analizzare come

! ((~a) & b) 

E la frase

~ ! a & b 

come

~(! (a & b)) 

Parsec mi permette di fare questo (e specificare la precedenza degli operatori), però, mi piacerebbe essere in grado di prefissi a catena, per esempio ~ ~ ! ~ a. Parsec non consente questo. Ho trovato la soluzione for chaining prefixes, ma questa soluzione non mi consente di specificare una priorità operatore diversa per i diversi operatori di prefisso (sia "~" che "!" Vincolano più forte di "&" o nessuno di loro lo fa)

Qualcuno ha una soluzione per questo?

Edit:

soluzione parziale che ottiene le associazioni degli operatori corretti, ma permette nessuna concatenazione: http://lpaste.net/143362

soluzione parziale con concatenamento ma che ha un torto vincolante per l'operatore "~": http://lpaste.net/143364

Modifica: Altri chiarimenti relativi allo latest answer.

In realtà desidero associare lo &. Sinistra o destra non importa. L'associatività sinistra-destra riguarda solo gli operatori con la stessa precedenza. Per i tuoi esempi, è tutto risolto osservando che & lega più forte di ! (& ha all'operatore maggiore precedenza)

Quindi, l'espressione si erano preoccupati:

a & ! b & c dovrebbe diventare: (prima legarsi & se possibile) a & ! (b & c)

Analogamente, ! a & ! b & c devono essere analizzati (prima impegnare &) ! a & ! (b & c), quindi ! a & (! (b & c)), quindi ! (a & (! (b & c)))

Answer 1

Non ero soddisfatto con la mia risposta originale poiché non risolve il caso generale di operatori prefissi e postfissi a varie precedenze, e richiede al programmatore di pensare alla grammatica invece di affidarsi semplicemente allo buildExpressionParser per fare la cosa giusta.

Ho dato la caccia online e ho scoperto lo Pratt method for recursive descent parsing of expressions. Sono stato in grado di implementare una versione compatta di Haskell che sostituisce buildExpressionParser. Ha esattamente la stessa interfaccia di buildExpressionParser, ma non richiede di usare i combinatori di prefissi concatenati o di muckare con il termine parser. Ho suonato in giro con la grammatica, cambiando l'associatività di &, e passando gli operatori prefissi di operatori in forma suffissa, e tutto sembra funzionare ...

buildPrattParser table termP = parser precs where 

    precs = reverse table 

    prefixP = choice prefixPs <|> termP where 
    prefixPs = do 
     precsR@(ops:_) <- tails precs 
     Prefix opP <- ops 
     return $ opP <*> parser precsR 

    infixP precs lhs = choice infixPs <|> pure lhs where 
    infixPs = do 
     precsR@(ops:precsL) <- tails precs 
     op <- ops 
     p <- case op of 
     Infix opP assoc -> do 
      let p precs = opP <*> pure lhs <*> parser precs 
      return $ case assoc of 
      AssocNone -> error "Non associative operators are not supported" 
      AssocLeft -> p precsL 
      AssocRight -> p precsR 
     Postfix opP -> 
      return $ opP <*> pure lhs 
     Prefix _ -> mzero 
     return $ p >>= infixP precs 

    parser precs = prefixP >>= infixP precs 

Answer 2

Un problema con la mia soluzione parziale al http://lpaste.net/143362 è che non riconosce ~ ! a.

Tuttavia, se si modifica la tabella all'operatore di:

table = [ [ Prefix tilde ] 
      , [ Infix amper AssocLeft ] 
      , [ Prefix bang ] 
      , [ Prefix tilde ] 
      ] 

è in grado di analizzare l'espressione così come ! ~a & b, ~ ! a & b correttamente. Codice: http://lpaste.net/143370

Così ora si combinano questa idea con il concatenamento e provare:

table = [ [ Prefix (chained tilde) ] 
      , [ Infix amper AssocLeft ] 
      , [ Prefix (chained bang) ] 
      , [ Prefix (chained tilde) ] 
      ] 

chained p = chainl1 p $ return (.) 

Codice: http://lpaste.net/143371

Answer 3

una nuova risposta ...

hai pensato l'associatività del & operatore?

Ecco un'altra idea che ho trovato supponendo che & sia associativo giusto.

1. Raccogliere la sequenza di operatori di prefisso che precedono un termine.
2. analizzare il termine (un ident o un'espressione paren)
3. sistemare il termine spostando oltre ~ operatori dalla sequenza raccolte nel passaggio 1.
4. Se il token successivo è un &, il LHS dell'operatore amper è il termine fisso. Gli operatori rimanenti vengono applicati all'espressione amper.
5. Altrimenti il ​​risultato è solo l'operatore del prefisso applicato al termine.

Credo associatività dei & questioni, per esempio dobbiamo:

a & ! b & c --> a & (! b & c) --> a & ! (b & c) 

o

a & ! b & c --> (a & (! b)) & c 

Un altro caso da pensare è ! a & ! b & c - Come vuoi che analizzato?

Un'implementazione:

{-# LANGUAGE NoMonomorphismRestriction, FlexibleContexts #-} 

import Text.Parsec 
import Control.Monad 
import Text.ParserCombinators.Parsec hiding (runParser, try) 
import Text.Parsec.Char 

data Sentence = Ident String | Bang Sentence | Tilde Sentence | Amper Sentence Sentence 
    deriving (Show) 

lexer p = do x <- p; spaces; return x 
ident = lexer (many1 letter) 
sym ch = lexer (char ch) 

tilde = sym '~' 
bang = sym '!' 
amper = sym '&' 

parens p = between (sym '(') (sym ')') p 

term = parens expr 
      <|> (fmap Ident ident) 
      <?> "simple expression" 

prefixOps = many (try tilde <|> bang) 

expr = do 
    ops <- fmap reverse prefixOps 
    lhs <- term 

    let (ops', lhs') = popTildes ops lhs 
     pre = mkPrefixNode ops' 

    mrhs <- try (fmap Just (amper >> expr)) <|> (return Nothing) 

    case mrhs of 
    Nothing -> return $ pre lhs' 
    Just rhs -> return $ pre (Amper lhs' rhs) 

popTildes :: [Char] -> Sentence -> ([Char], Sentence) 
popTildes ('~':rest) s = popTildes rest (Tilde s) 
popTildes ops s  = (ops, s) 

mkPrefixNode :: [Char] -> (Sentence -> Sentence) 
mkPrefixNode [] = id 
mkPrefixNode ('~':rest) = mkPrefixNode rest . Tilde 
mkPrefixNode ('!':rest) = mkPrefixNode rest . Bang 
mkPrefixNode _   = error "can't happen" 

check :: String -> IO() 
check input = do 
    let padded = input ++ (replicate (15-length input) ' ') 
    case parse expr "-" input of 
    Left e -> do putStrLn $ "FAILED: " ++ input 
        putStrLn $ " " ++ show e 
    Right x -> do putStrLn $ "OK: " ++ padded ++ " -> " ++ show x 

inputs = [ "a", "! a", "~ a", "a & b", "! a & b", "~ a & b", "! ~ a & b" 
      , "~ ! a", "! ~a & b", "~ ! a & b ", "! ~ ! a 2" 
      ] 

main = mapM_ check inputs 

Answer 4

La grammatica sinistra presi per il parser che volete è:

sentence : '!' sentence 
     | sentence1 

sentence1 : sentence2 '&' sentence1 
      | sentence2 

sentence2 : '~' sentence2 
      | term 

term : '!' sentence 
    | ident 

Che può essere riscritto in EBNF come:

sentence : '!'* sentence1 

sentence1 : sentence2 ('&' sentence2)* 

sentence2 : '~'* term 

term : '!' sentence 
    | ident 

Il parser generato da buildExpressionParser utilizzando gli operatori con prefisso concatenato quasi genera questo parser, tranne che o non includere la regola ! nel parser termine; da qui l'errore di analisi quando si incontra uno ! dopo un ~.

Dato il seguente:

{-# LANGUAGE NoMonomorphismRestriction #-} 
module Main where 

import Control.Monad 
import Text.Parsec 
import Text.Parsec.Expr 
import Text.Parsec.Char 
import Control.Applicative ((<*), (*>), (<*>), (<$), (<$>)) 

data Sentence = Tilde Sentence 
       | Bang Sentence 
       | Amper Sentence Sentence 
       | Ident String 
    deriving (Eq, Ord, Show) 

bangP = Bang <$ lexeme (char '!') 
amperP = Amper <$ lexeme (char '&') 
tildeP = Tilde <$ lexeme (char '~') 
identP = Ident <$> lexeme (many1 alphaNum) 

lexeme = (<* spaces) 

parser = spaces *> sentence <* eof 

main = do 
    let inputs = [ "a", "! a", "~ a", "a & b", "! a & b" 
       , "~ a & b", "! ~ a & b", "~ ! a & b", "! ~ ! a" 
       , "~ a & b", "a & ! b & c & d" 
       ] 
    forM_ inputs $ \input -> do 
    putStr input 
    putStr " -> " 
    parseTest parser input 

possiamo definire la sentence parser a mano:

sentence = sentence0 where 
    sentence0 = chainl bangP (return (.)) id <*> sentence1 
    sentence1 = chainl1 sentence2 amperP 
    sentence2 = chainl tildeP (return (.)) id <*> term 
    term = (bangP <*> sentence0) <|> identP 

o possiamo usare buildExpressionParser se aggiungiamo la regola ! nella term parser:

sentence = buildExpressionParser table term where 
    table = [ [prefix tildeP] 
      , [Infix amperP AssocLeft] 
      , [prefix bangP] 
      ] 
    term = (bangP <*> sentence) <|> identP 
    prefix p = Prefix . chainl1 p $ return (.)