Qu'est-ce qu'une structure de données ou un algorithme approprié pour produire un arbre de syntaxe concret immuable d'une manière fonctionnellement pure?

Question

Étant donné un LL (1) grammaire qu'est-ce qu'une structure de données ou un algorithme approprié pour produire un arbre de syntaxe concret immuable d'une manière fonctionnellement pure? N'hésitez pas à écrire un exemple de code dans la langue que vous préférez.

Mon idée

 
symbol : either a token or a node 

result : success or failure 

token : a lexical token from source text 
    value -> string : the value of the token 
    type -> integer : the named type code of the token 
    next -> token : reads the next token and keeps position of the previous token 
    back -> token : moves back to the previous position and re-reads the token 

node : a node in the syntax tree 
    type -> integer : the named type code of the node 
    symbols -> linkedList : the symbols found at this node 
    append -> symbol -> node : appends the new symbol to a new copy of the node 

Voici une idée que j'ai pensé à. Le problème principal ici est de gérer les erreurs de syntaxe. Je veux dire que je pourrais arrêter à la première erreur mais cela ne semble pas correct.

let program token = 
    sourceElements (node nodeType.program) token   

let sourceElements node token = 
    let (n, r) = sourceElement (node.append (node nodeType.sourceElements)) token 
    match r with 
    | success -> (n, r) 
    | failure -> // ???  

let sourceElement node token = 
    match token.value with 
    | "function" -> 
     functionDeclaration (node.append (node nodeType.sourceElement)) token 
    | _ -> 
     statement (node.append (node nodeType.sourceElement)) token 

S'il vous plaît noter

Je va offrir une belle prime à la meilleure réponse, alors ne se sentent pas bousculés. Les réponses qui affichent simplement un lien auront moins de poids sur les réponses qui affichent du code ou contiennent des explications détaillées.

Note finale

Je suis vraiment nouveau à ce genre de choses alors ne pas avoir peur de me appeler un crétin.

Answer 1

Vous souhaitez analyser quelque chose dans un arbre de syntaxe abstraite.

Dans le langage de programmation purement fonctionnel Haskell, vous pouvez utiliser combinateurs d'analyseurs pour exprimer votre grammaire. Voici un exemple qui parse une langue minuscule d'expression:

EDIT Utilisez le style monadique pour correspondre le livre de Graham Hutton

-- import a library of *parser combinators* 
import Parsimony 
import Parsimony.Char 
import Parsimony.Error 
(+++) = (<|>) 

    -- abstract syntax tree 
data Expr = I Int 
      | Add Expr Expr 
      | Mul Expr Expr 
      deriving (Eq,Show) 

    -- parse an expression 
parseExpr :: String -> Either ParseError Expr 
parseExpr = Parsimony.parse pExpr 
    where 

     -- grammar 
    pExpr :: Parser String Expr 
    pExpr = do 
     a <- pNumber +++ parentheses pExpr -- first argument 
     do 
      f <- pOp      -- operation symbol 
      b <- pExpr      -- second argument 
      return (f a b) 
     +++ return a      -- or just the first argument 

    parentheses parser = do     -- parse inside parentheses 
     string "(" 
     x <- parser 
     string ")" 
     return x 

    pNumber = do       -- parse an integer 
     digits <- many1 digit 
     return . I . read $ digits 

    pOp =         -- parse an operation symbol 
     do string "+" 
      return Add 
     +++ 
     do string "*" 
      return Mul 

Voici un exemple exécuté:

*Main> parseExpr "(5*3)+1" 
Right (Add (Mul (I 5) (I 3)) (I 1)) 

Pour en savoir plus sur combinateurs analyseur , voir par exemple le chapitre 8 de Graham Hutton's book "Programming in Haskell" ou chapter 16 de "Real World Haskell".

De nombreuses bibliothèques de combinateurs d'analyseurs peuvent être utilisées avec différents types de jetons, comme vous avez l'intention de le faire. Les flux de jetons sont généralement représentés sous la forme de listes de jetons [Token].

Answer 2

Eric Lippert's blog series on immutable binary trees peut vous être utile. Évidemment, vous avez besoin d'un arbre qui n'est pas binaire, mais il vous donnera l'idée générale.

Answer 3

Vérifiez définitivement l'approche du combinateur d'analyseur monadique; J'ai blogué à ce sujet in C# et in F#.