Analisi di un elenco di token in un albero di espressioni

algorithm expression-trees haskell

Domanda

Voglio analizzare espressioni come quelle della tipica fonte Haskell. Ottengo un flusso di input, che è già tokenizzato e annotato con fissità e precedenza. L'insieme di operatori non è noto al momento della compilazione e potrebbe essere arbitrario. L'output dovrebbe essere un albero che rappresenta l'espressione. Ecco un po 'di quello che ho provato:

-- A single token of the input stream
data Token a
  = Prefix a
  | Infix a Int Fixity -- The Int parameter represents the precedence
  | LBrace
  | RBrace
  deriving (Show,Eq)

data Fixity
  = InfixL
  | InfixR
  | InfixC
  deriving (Show,Eq)

data Expression a
  = Atom a
  | Apply a a
  deriving Show

-- Wrapped into either, if expression is malformed.
exprToTree :: [Token a] -> Either String (Expression a)
exprToTree = undefined

Per ragioni di semplicità, non considero i lambda speciali, sono solo degli atomi.

Ma ora, sono completamente perso. Come posso convertire il flusso di atomi in un albero? Qualcuno può indicarmi un algoritmo o aiutarmi a trovarne uno.

Risposta accettata

In poche parole, anche se hai una lista di token hai ancora bisogno di un parser.

Parsec può gestire flussi di token alternativi, ma probabilmente dovrai fare riferimento al manuale: un PDF disponibile nella home page "legacy" di Daan Leijen - http://legacy.cs.uu.nl/daan/download/parsec/parsec .pdf . Puoi eseguire il rollup del parser senza utilizzare una libreria combinator, ma applicherai di nuovo alcune parti di Parsec. Per quanto mi ricordo, UU_parsing si aspetta di lavorare con uno scanner separato, quindi la sua altra opzione.

Sebbene non gestisca l'analisi, potresti trovare utile il "calcolo Lambda cucinato in quattro modi" di Lennart Augustsson per altre cose - http://www.augustsson.net/Darcs/Lambda/top.pdf

Modifica : ecco un piano parzialmente elaborato su come procedere con Parsec, per i dettagli dovrai consultare la sezione 2.11 del manuale.

Supponiamo di avere questo tipo di dati per i token "interni" concreti:

data InternalTok = Ident String
                 | BinOpPlus
                 | BinOpMinus
                 | UnaryOpNegate
                 | IntLiteral Int
  deriving (Show)

Quindi si finisce per ottenere questi tipi per il token Parsec e analizzare:

type MyToken = Token InternalTok

type MyParser a = GenParser MyToken () a

Definisci una funzione di supporto come da manuale di Parsec - questo gestisce show e pos in modo che le singole definizioni siano più brevi cf. la funzione mytoken a pagina 19.

mytoken :: (MyToken -> Maybe a) -> MyParser a
mytoken test = token showToken posToken testToken
  where
    showToken tok = show tok
    posToken tok = no_pos
    testToken tok = test tok

Per il momento il tuo tipo di token non traccia la posizione della sorgente, quindi:

no_pos :: SourcePos
no_pos = newPos "" 0 0 0 

Per ogni terminale devi definire una funzione token:

identifier :: MyParser MyToken
identifier =  mytoken (\tok -> case tok of
                         a@(Prefix (Ident _)) -> Just a
                         _                    -> Nothing)

intLiteral :: MyParser MyToken
intLiteral =  mytoken (\tok -> case tok of
                         a@(Prefix (IntLiteral _)) -> Just a
                         _                         -> Nothing)

binPlus :: MyParser MyToken
binPlus =  mytoken (\tok -> case tok of
                      a@(Infix BinOpPlus _ _) -> Just a
                      _                       -> Nothing)


binMinus :: MyParser MyToken
binMinus =  mytoken (\tok -> case tok of
                      a@(Infix BinOpMinus _ _) -> Just a
                      _                        -> Nothing)

unaryNegate :: MyParser MyToken
unaryNegate =  mytoken (\tok -> case tok of
                        a@(Prefix UnaryNegate _ _) -> Just a
                        _                          -> Nothing)

Modifica : per gestire gli operatori di infissi personalizzati avrai bisogno di questi parser di token:

tokInfixL :: Int -> MyParser MyToken
tokInfixL n = mytoken $ \tok -> case tok of
    a@(Infix _ i InfixL) | i == n -> Just a
    _                             -> Nothing)


tokInfixR :: Int -> MyParser MyToken
tokInfixR n = mytoken $ \tok -> case tok of
    a@(Infix _ i InfixR) | i == n -> Just a
    _                             -> Nothing)

tokInfixC :: Int -> MyParser MyToken
tokInfixC n = mytoken $ \tok -> case tok of
    a@(Infix _ i InfixC) | i == n -> Just a
    _                             -> Nothing)


tokPrefix :: MyParser MyToken
tokPrefix = mytoken (\tok -> case tok of
                       a@(Prefix _) -> Just a
                       _            -> Nothing)

Ora puoi definire il parser - devi prima correggere il numero di livelli di precedenza, non c'è modo di aggirare questo fatto dato che devi codificare un parser per ogni livello.

L'analisi delle espressioni di livello superiore chiama semplicemente il parser con la precedenza più alta

pExpression :: Parser Expersion
pExpression = expression10

Per ogni livello di precendenza hai bisogno di un parser all'incirca come questo, dovrai allenarti da non-socio per te stesso. Potrebbe anche essere necessario lavorare su chainl / chainr - Ho solo scritto un parser in questo stile con UU_Parsing potrebbe essere leggermente diverso per Parsec. Nota Applica è solitamente al livello più alto della precedenza.

expression10 :: Parser Expression
expression10 = 
        Apply   <$> identifier <*> pExpression
    <|> Prefix  <$> tokPrefix  <*> pExpression
    <|> chainl (Infix <$> tokInfixL 10) expression9
    <|> chainr (Infix <$> tokInfixR 10) expression9

expression9 :: Parser Expression
expression9 = 
        Prefix  <$> tokPrefix  <*> pExpression
    <|> chainl (Infix <$> tokInfixL 9) expression8
    <|> chainr (Infix <$> tokInfixR 9) expression8

...

Dovrai estendere la tua sintassi per gestire Intliterals e Identifier che sono al livello 0 in precedenza:

expression0 :: Parser Expression
expression0 = 
        IntLit  <$> intLiteral 
    <|> Ident   <$> identifier
    <|> ...

Modifica - per la precedenza illimitata - forse se hai solo un'applicazione e Atom forse qualcosa del genere funzionerebbe. Nota che dovrai modificare i parser tokInfixL e tokInfixR per non abbinare più il livello assoc e potresti dover sperimentare l'ordine delle alternative.

expression :: Parser Expression
expression = 
        Apply   <$> identifier <*> expression
    <|> Prefix  <$> tokPrefix  <*> expression
    <|> chainl (Infix <$> tokInfixL) expression
    <|> chainr (Infix <$> tokInfixR) expression
    <|> intLiteral
    <|> identifier

intLiteral :: Parser Expression
intLiteral = Atom . convert <$> intLiteral
  where
    convert = ??

identifier :: Parser Expression
identifier = Atom . convert <$> intLiteral
  where
    convert = ??

Risposta popolare

Dopo aver cercato sul web un altro argomento, ho trovato questo bel pezzo di codice per fare esattamente quello che volevo. Dare un'occhiata:

data Op     = Op String Prec Fixity          deriving Eq
data Fixity = Leftfix | Rightfix | Nonfix    deriving Eq
data Exp    = Var Var | OpApp Exp Op Exp     deriving Eq
type Prec   = Int
type Var    = String

data Tok = TVar Var | TOp Op

parse :: [Tok] -> Exp
parse (TVar x : rest) = fst (parse1 (Var x) (-1) Nonfix rest)

parse1 :: Exp -> Int -> Fixity -> [Tok] -> (Exp, [Tok])
parse1 e p f [] = (e, [])
parse1 e p f inp@(TOp op@(Op _ p' f') : TVar x : rest) 
  | p' == p && (f /= f' || f == Nonfix)
  = error "ambiguous infix expression"
  | p' < p  ||  p' == p && (f == Leftfix || f' == Nonfix)
  = (e, inp)
  | otherwise
  = let (r,rest') = parse1 (Var x) p' f' rest in
    parse1 (OpApp e op r) p f rest'

-- Printing

instance Show Exp where
  showsPrec _ (Var x) = showString x
  showsPrec p e@(OpApp l (Op op _ _) r) = 
        showParen (p > 0) $ showsPrec 9 l . showString op . showsPrec 9 r

-- Testing

plus   = TOp (Op "+" 6 Leftfix)
times  = TOp (Op "*" 7 Leftfix)
divide = TOp (Op "/" 7 Leftfix)
gt     = TOp (Op ">" 4 Nonfix)
ex     = TOp (Op "^" 8 Rightfix)

lookupop '+' = plus
lookupop '*' = times
lookupop '/' = divide
lookupop '>' = gt
lookupop '^' = ex

fromstr [x]     = [TVar [x]]
fromstr (x:y:z) = TVar [x] : lookupop y : fromstr z

test1 = fromstr "a+b+c"
test2 = fromstr "a+b+c*d"
test3 = fromstr "a/b/c"
test4 = fromstr "a/b+c"
test5 = fromstr "a/b*c"
test6 = fromstr "1^2^3+4"
test7 = fromstr "a/1^2^3"
test8 = fromstr "a*b/c"

(L'ho preso da questa pagina: http://hackage.haskell.org/trac/haskell-prime/attachment/wiki/FixityResolution/resolve.hs )



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché