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:

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

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.

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

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

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

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

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

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

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

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é

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

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

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

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

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

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.

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

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