Analisi corretta dei dati nidificati utilizzando megaparsec
Sto cercando di acquisire maggiore familiarità con megaparsec e sto riscontrando alcuni problemi con le presenze. Con "dati nidificati" nel titolo mi riferisco al fatto che sto cercando di analizzare i tipi, che a loro volta potrebbero contenere altri tipi . Se qualcuno potesse spiegare perché questo non si comporta come mi aspetterei, non esitare a dirmelo.
Sto cercando di analizzare tipi simili a quelli trovati in Haskell. Tipi sono o tipi di base Int, Bool, Floato variabili di tipo a(qualsiasi parola minuscole). Possiamo anche costruire tipi di dati algebrici da costruttori di tipi (parole maiuscole) come Maybee parametri di tipo (qualsiasi altro tipo). Gli esempi sono Maybe ae Either (Maybe Int) Bool. Le funzioni si associano a destra e sono costruite con ->, come Maybe a -> Either Int (b -> c). Le tuple n-arie sono una sequenza di tipi separati da ,e racchiusi in (e ), come (Int, Bool, a). Un tipo può essere racchiuso tra parentesi per aumentare il suo livello di precedenza (Maybe a). Viene ()anche definito un tipo di unità .
Sto usando questo ADT per descrivere questo.
newtype Ident = Ident String
newtype UIdent = UIdent String
data Type a
= TLam a (Type a) (Type a)
| TVar a Ident
| TNil a
| TAdt a UIdent [Type a]
| TTup a [Type a]
| TBool a
| TInt a
| TFloat a
Ho provato a scrivere un megaparsecparser per analizzare tali tipi, ma ottengo risultati imprevisti. Allego di seguito il relativo codice, dopodiché cercherò di descrivere quello che sto vivendo.
{-# LANGUAGE OverloadedStrings #-}
module Parser where
import AbsTinyCamiot
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as Lexer
import Text.Megaparsec.Debug
import Control.Applicative hiding (many, some, Const)
import Control.Monad.Combinators.Expr
import Control.Monad.Identity
import Data.Void
import Data.Text (Text, unpack)
type Parser a = ParsecT Void Text Identity a
-- parse types
pBaseType :: Parser (Type ())
pBaseType = choice [
TInt () <$ label "parse int" (pSymbol "Int"), TBool () <$ label "parse bool" (pSymbol "Bool"),
TFloat () <$ label "parse float" (pSymbol "Float"), TNil () <$ label "parse void" (pSymbol "()"),
TVar () <$> label "parse type variable" pIdent] pAdt :: Parser (Type ()) pAdt = label "parse ADT" $ do
con <- pUIdent
variables <- many $ try $ many spaceChar >> pType
return $ TAdt () con variables pType :: Parser (Type ()) pType = label "parse a type" $
makeExprParser
(choice [ try pFunctionType
, try $ parens pType , try pTupleType , try pBaseType , try pAdt ]) []--[[InfixR (TLam () <$ pSymbol "->")]]
pTupleType :: Parser (Type ())
pTupleType = label "parse a tuple type" $ do pSymbol "(" fst <- pType rest <- some (pSymbol "," >> pType) pSymbol ")" return $ TTup () (fst : rest)
pFunctionType :: Parser (Type ())
pFunctionType = label "parse a function type" $ do domain <- pType some spaceChar pSymbol "->" some spaceChar codomain <- pType return $ TLam () domain codomain
parens :: Parser a -> Parser a
parens p = label "parse a type wrapped in parentheses" $ do pSymbol "(" a <- p pSymbol ")" return a pUIdent :: Parser UIdent pUIdent = label "parse a UIdent" $ do
a <- upperChar
rest <- many $ choice [letterChar, digitChar, char '_'] return $ UIdent (a:rest)
pIdent :: Parser Ident
pIdent = label "parse an Ident" $ do a <- lowerChar rest <- many $ choice [letterChar, digitChar, char '_']
return $ Ident (a:rest)
pSymbol :: Text -> Parser Text
pSymbol = Lexer.symbol pSpace
pSpace :: Parser ()
pSpace = Lexer.space
(void spaceChar)
(Lexer.skipLineComment "--")
(Lexer.skipBlockComment "{-" "-}")
Questo potrebbe essere travolgente, quindi lascia che ti spieghi alcuni punti chiave. Capisco che ho molte costruzioni diverse che potrebbero corrispondere su una parentesi di apertura, quindi ho inserito quei parser try, in modo tale che se falliscono posso provare il parser successivo che potrebbe consumare una parentesi di apertura. Forse ne sto usando trytroppo? Influisce sulle prestazioni potenzialmente tornare indietro così tanto?
Ho anche provato a creare un parser di espressioni definendo alcuni termini e una tabella di operatori. Ora puoi vedere che ho commentato l'operatore (freccia di funzione), tuttavia. Dato che il codice appare in questo momento, faccio un ciclo infinito quando provo ad analizzare un tipo di funzione . Penso che ciò potrebbe essere dovuto al fatto che quando provo ad analizzare un tipo di funzione (invocato da pType) provo immediatamente ad analizzare un tipo che rappresenta il dominio della funzione, che di nuovo chiama pType. Come lo farei correttamente?
Se invece decido di utilizzare la tabella degli operatori e di non utilizzare il mio parser personalizzato per i tipi di funzione, analizzo le cose usando precedenza sbagliate. Ad esempio Maybe a -> bviene analizzato come Maybe (a -> b), mentre vorrei che fosse analizzato come (Maybe a) -> b. C'è un modo in cui posso usare la tabella degli operatori e avere ancora i costruttori di tipi legati più strettamente rispetto alla freccia della funzione ?
Infine, poiché sto imparando il megaparsec mentre vado, se qualcuno vede malintesi o cose che sono strane / inaspettate, per favore dimmelo . Ho letto la maggior parte di questo tutorial per arrivare fin qui.
Per favore fatemi sapere di eventuali modifiche che posso apportare per aumentare la qualità della mia domanda!
Risposte
Il tuo codice non gestisce affatto le precedenze e, di conseguenza, utilizza la ricorsione a sinistra del ciclo.
Per fornire un esempio di ricorsione a sinistra nel codice, pFunctionTypechiama pTypecome prima azione, che chiama pFunctionTypecome prima azione. Questo è chiaramente un loop.
Per le precedenti, consiglio di guardare i tutorial sull '"analisi dell'operatore di discesa ricorsiva", una rapida ricerca su Google rivela che ce ne sono diversi. Tuttavia posso riassumere qui i punti chiave. Scrivo del codice.
{-# language OverloadedStrings #-}
import Control.Monad.Identity
import Data.Text (Text)
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as Lexer
type Parser a = ParsecT Void Text Identity a
newtype Ident = Ident String deriving Show
newtype UIdent = UIdent String deriving Show
data Type
= TVar Ident
| TFun Type Type -- instead of "TLam"
| TAdt UIdent [Type]
| TTup [Type]
| TUnit -- instead of "TNil"
| TBool
| TInt
| TFloat
deriving Show
pSymbol :: Text -> Parser Text
pSymbol = Lexer.symbol pSpace
pChar :: Char -> Parser ()
pChar c = void (char c <* pSpace)
pSpace :: Parser ()
pSpace = Lexer.space
(void spaceChar)
(Lexer.skipLineComment "--")
(Lexer.skipBlockComment "{-" "-}")
keywords :: [String]
keywords = ["Bool", "Int", "Float"]
pUIdent :: Parser UIdent
pUIdent = try $ do a <- upperChar rest <- many $ choice [letterChar, digitChar, char '_']
pSpace
let x = a:rest
if elem x keywords
then fail "expected an ADT name"
else pure $ UIdent x pIdent :: Parser Ident pIdent = try $ do
a <- lowerChar
rest <- many $ choice [letterChar, digitChar, char '_'] pSpace return $ Ident (a:rest)
Fermiamoci qui.
- Ho cambiato i nomi dei costruttori in
Typeper conformarli a come vengono chiamati in Haskell. Ho anche rimosso il parametroType, per avere meno rumore nel mio esempio, ma puoi aggiungerlo di nuovo ovviamente. - Notare la modifica
pUIdente l'aggiunta dikeywords. In generale, se vuoi analizzare gli identificatori, devi disambigarli dalle parole chiave. In questo caso,Intpotrebbe analizzare sia comeIntche come identificatore maiuscolo, quindi dobbiamo specificare che nonIntè un identificatore.
Continuando:
pClosed :: Parser Type
pClosed =
(TInt <$ pSymbol "Int") <|> (TBool <$ pSymbol "Bool")
<|> (TFloat <$ pSymbol "Float") <|> (TVar <$> pIdent)
<|> (do pChar '('
ts <- sepBy1 pFun (pChar ',') <* pChar ')'
case ts of
[] -> pure TUnit
[t] -> pure t
_ -> pure (TTup ts))
pApp :: Parser Type
pApp = (TAdt <$> pUIdent <*> many pClosed) <|> pClosed pFun :: Parser Type pFun = foldr1 TFun <$> sepBy1 pApp (pSymbol "->")
pExpr :: Parser Type
pExpr = pSpace *> pFun <* eof
Dobbiamo raggruppare gli operatori in base alla forza vincolante. Per ogni forza, dobbiamo avere una funzione di analisi separata che analizzi tutti gli operatori di quella forza. In questo caso abbiamo pFun, pAppe pClosedin ordine crescente di forza legante. pExprè solo un wrapper che gestisce le espressioni di primo livello e si occupa degli spazi bianchi iniziali e corrisponde alla fine dell'input.
Quando si scrive un parser di operatori, la prima cosa da definire è il gruppo di espressioni chiuse. Le espressioni chiuse sono delimitate da una parola chiave o da un simbolo sia a sinistra che a destra. Questa è una forza vincolante concettualmente "infinita", poiché il testo prima e dopo tali espressioni non cambia affatto la loro analisi.
Le parole chiave e le variabili sono chiaramente chiuse, poiché consistono in un unico token. Abbiamo anche altri tre casi chiusi: il tipo di unità, le tuple e le espressioni tra parentesi. Poiché tutti questi iniziano con a (, lo prendo in considerazione . Dopodiché, abbiamo uno o più tipi separati da ,e dobbiamo diramare sul numero di tipi analizzati.
La regola nell'analisi di precedenza è che quando si analizza un'espressione di operatore di una determinata forza, viene sempre chiamato il successivo parser di espressioni più forte quando si leggono le espressioni tra i simboli di operatore.
,è l'operatore più debole, così chiamiamo la funzione per l'operatore secondo più debole, pFun.
pFuna sua volta chiama pApp, che legge le applicazioni ADT, o torna a pClosed. In pFunpuoi anche vedere la gestione della giusta associatività, come usiamo foldr1 TFunper combinare le espressioni. In un operatore infisso associativo a sinistra, dovremmo invece usare foldl1.
Notare che le funzioni del parser analizzano sempre anche tutte le espressioni più forti. Quindi pFunricade pAppquando non c'è ->(perché sepBy1accetta il caso senza separatori), e pAppricade pClosedquando non c'è applicazione ADT.