Eine Liste von Token in einen Ausdrucksbaum einordnen

algorithm expression-trees haskell

Frage

Ich möchte Ausdrücke wie jene in einer typischen Haskell-Quelle parsen. Ich erhalte einen Eingabestream, der bereits in Token umgewandelt und mit Fixity und Precedence versehen wurde. Die Menge der Operatoren ist zur Kompilierzeit nicht bekannt und kann beliebig sein. Die Ausgabe sollte ein Baum sein, der den Ausdruck darstellt. Hier ist ein bisschen was ich versucht habe:

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

Der Einfachheit halber behandle ich Lambdas nicht speziell, sie sind nur Atome.

Aber jetzt bin ich völlig verloren. Wie kann ich den Atomstrom in einen Baum umwandeln? Kann mir jemand bitte einen Algorithmus zeigen oder mir helfen, einen zu finden?

Akzeptierte Antwort

Kurz gesagt, obwohl Sie eine Token-Liste haben, brauchen Sie immer noch einen Parser.

Parsec kann alternative Token-Streams verarbeiten, aber Sie müssen wahrscheinlich auf das Handbuch verweisen - ein PDF-Dokument, das auf der "Legacy" -Homepage von Daan Leijen verfügbar ist - http://legacy.cs.uu.nl/daan/download/parsec/parsec .pdf . Sie können Ihren eigenen Parser rollen, ohne eine Kombinator-Bibliothek zu verwenden, aber Sie werden einen Teil von Parsec erneut implementieren. Soweit ich mich erinnere, erwartet UU_parsing mit einem separaten Scanner zu arbeiten, also eine andere Option.

Obwohl es nicht mit Parsing umgehen kann, finden Sie Lennart Augustssons "Lambda-Kalkül, das auf vier Arten gekocht wird", hilfreich für andere Dinge - http://www.augustsson.net/Darcs/Lambda/top.pdf

Bearbeiten - Hier ist ein teilweise ausgearbeiteter Plan, wie Sie mit Parsec vorgehen können, für Details lesen Sie bitte Abschnitt 2.11 des Handbuchs.

Angenommen, Sie haben diesen Datentyp für konkrete "interne" Token:

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

Dann beendest du diese Typen für das Parsec-Token und parse:

type MyToken = Token InternalTok

type MyParser a = GenParser MyToken () a

Definieren Sie eine Hilfsfunktion gemäß dem Parsec-Handbuch - diese behandelt show und pos, so dass einzelne Definitionen kürzer sind, vgl. die mytoken Funktion auf Seite 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

Momentan verfolgt Ihr Tokentyp die Quellposition nicht, also:

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

Für jedes Terminal müssen Sie eine Token-Funktion definieren:

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)

Bearbeiten - Um mit benutzerdefinierten Infix-Operatoren umgehen zu können, benötigen Sie diese Token-Parser:

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)

Jetzt können Sie den Parser definieren - Sie müssen die Anzahl der Rangstufen vorher korrigieren, es gibt keinen Weg um diese Tatsache zu umgehen, da Sie einen Parser für jede Ebene programmieren müssen.

Der Ausdruck der obersten Ebene wird einfach als höchster Präzedenz-Parser bezeichnet

pExpression :: Parser Expersion
pExpression = expression10

Für jede Präzedenzstufe benötigen Sie einen Parser, ungefähr so, Sie müssen für sich selbst nicht assoziieren. Vielleicht müssen Sie auch etwas an Chainl / Chainr arbeiten - ich habe nur einen Parser in diesem Stil mit UU_Parsing geschrieben, der für Parsec etwas anders sein könnte. Hinweis: Anwenden hat normalerweise die höchste Priorität.

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

...

Sie müssen Ihre Syntax so erweitern, dass sie IntLiterals und Identifiers behandelt, die auf Stufe 0 Vorrang haben:

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

Edit - für unbegrenzte Präzedenz - vielleicht, wenn Sie nur Anwendung und Atom vielleicht etwas wie das funktionieren würde. Beachten Sie, dass Sie die tokInfixL- und tokInfixR-Parser so ändern müssen, dass sie nicht mehr auf assoziativer Ebene liegen, und Sie müssen möglicherweise mit der Reihenfolge der Alternativen experimentieren.

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 = ??

Beliebte Antwort

Nachdem ich im Internet nach einem anderen Thema gesucht habe, fand ich dieses nette Stück Code, um genau das zu tun, was ich möchte. Guck mal:

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"

(Ich habe es von dieser Seite genommen: http://hackage.haskell.org/trac/haskell-prime/attachment/wiki/FixityResolution/resolve.hs )



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum