Analyser une liste de jetons dans un arbre d'expression

algorithm expression-trees haskell

Question

Je veux analyser des expressions comme celles des sources typiques de Haskell. Je reçois un flux d’entrée, qui est déjà marqué et annoté avec fixité et priorité. L'ensemble des opérateurs n'est pas connu au moment de la compilation et peut être arbitraire. La sortie doit être un arbre représentant l'expression. Voici un peu de ce que j'ai essayé:

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

Par souci de simplicité, je ne traite pas les lambdas comme spéciaux, ce sont juste des atomes.

Mais maintenant, je suis complètement perdu. Comment puis-je convertir le flux d'atomes en un arbre? Quelqu'un peut-il m'indiquer un algorithme ou m'aider à en trouver un?

Réponse acceptée

En un mot, alors même si vous avez une liste de jetons, vous avez toujours besoin d'un analyseur.

Parsec peut gérer des flux de jetons alternatifs, mais vous devrez probablement vous reporter au manuel - un fichier PDF disponible sur la page d'accueil "héritée" de Daan Leijen - http://legacy.cs.uu.nl/daan/download/parsec/parsec .pdf . Vous pouvez lancer votre propre analyseur sans utiliser de bibliothèque de combinateur, mais vous allez ré-implémenter une fraction de Parsec. Autant que je me souvienne, UU_parsing s'attend à utiliser un scanner séparé, ce qui en fait une autre option.

Même s'il ne gère pas l'analyse, vous trouverez peut-être que le "calcul lambda cuit de quatre manières" de Lennart Augustsson est utile pour d'autres choses - http://www.augustsson.net/Darcs/Lambda/top.pdf

Modifier - Voici un plan en partie élaboré sur la façon de procéder avec Parsec. Pour plus de détails, vous devrez consulter la section 2.11 du manuel.

Supposons que vous ayez ce type de données pour des jetons concrets "internes":

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

Ensuite, vous finissez par obtenir ces types pour le jeton Parsec et parse:

type MyToken = Token InternalTok

type MyParser a = GenParser MyToken () a

Définissez une fonction d’aide selon le manuel Parsec - ceci gère les fonctions show et pos afin que les définitions individuelles soient plus courtes, cf. la fonction mytoken à la page 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

Pour le moment, votre type de jeton ne suit pas la position de la source, donc:

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

Pour chaque terminal, vous devez définir une fonction de jeton:

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)

Edit - pour gérer les opérateurs d'infixe personnalisés, vous aurez besoin de ces analyseurs de jetons:

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)

Vous pouvez maintenant définir l’analyseur. Vous devez au préalable fixer le nombre de niveaux de priorité. Il n’ya aucun moyen de contourner ce fait, car vous devez coder un analyseur pour chaque niveau.

L'analyse d'expression de niveau supérieur consiste simplement à appeler l'analyseur de précédence le plus élevé

pExpression :: Parser Expersion
pExpression = expression10

Pour chaque niveau de précédence, vous avez besoin d'un analyseur syntaxique à peu près semblable à celui-ci, vous devrez vous-même préparer des tâches non assoc. Vous devrez peut-être aussi travailler sur chainl / chainr - je n'ai écrit qu'un analyseur syntaxique dans ce style avec UU_Parsing, il pourrait être légèrement différent pour Parsec. Remarque Apply est généralement au niveau de priorité le plus élevé.

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

...

Vous devrez étendre votre syntaxe pour gérer les IntLiterals et les identifiants qui sont au niveau 0 en priorité:

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

Modifier - pour une priorité illimitée - peut-être que si vous ne disposez que d’une application et d’Atom, quelque chose comme cela fonctionnerait Notez que vous devrez modifier les analyseurs syntaxiques tokInfixL et tokInfixR pour qu'ils ne correspondent plus au niveau assoc. Vous devrez peut-être expérimenter avec l'ordre des alternatives.

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

Réponse populaire

Après avoir cherché sur le Web un autre sujet, j’ai trouvé cette belle pièce de code qui fait exactement ce que je veux. Regarde:

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"

(Je l'ai tiré de cette page: http://hackage.haskell.org/trac/haskell-prime/attachment/wiki/FixityResolution/resolve.hs )



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi