Che cos'è una struttura dati o un algoritmo appropriati per produrre un albero di sintassi concreto immutabile in modo funzionalmente puro?

Question

Data una grammatica LL (1) Che cos'è una struttura dati o un algoritmo appropriati per produrre un albero di sintassi concreto immutabile in modo funzionalmente puro? Non esitate a scrivere codice di esempio in qualsiasi lingua preferite.

mia Idea

 
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 

Ecco un'idea che ho pensato. Il problema principale qui è la gestione degli errori di sintassi. Intendo dire che potrei fermarmi al primo errore ma non mi sembra giusto.

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 

Nota Bene

mi offriranno un piacevole grazia per la migliore risposta in modo da non sentire affrettato. Le risposte che pubblicano semplicemente un link avranno meno peso sulle risposte che mostrano il codice o contengono spiegazioni dettagliate.

nota finale

Sono veramente nuovo a questo genere di cose, quindi non abbiate paura di chiamare me uno scemo.

Answer 1

Si desidera parsing qualcosa in un albero di sintassi astratto.

Nel linguaggio di programmazione puramente funzionale Haskell, è possibile utilizzare combinatori di parser per esprimere la grammatica. Ecco un esempio che analizza un piccolo linguaggio delle espressioni:

EDIT Usa stile monadico per abbinare il libro di 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 

Ecco un esempio eseguire:

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

Per saperne di più su combinatori parser , vedi ad esempio il capitolo 8 di Graham Hutton's book "Programming in Haskell" o chapter 16 di "Real World Haskell".

Molte librerie di parser combinator possono essere utilizzate con diversi tipi di token, come si intende fare. I flussi di token sono solitamente rappresentati come elenchi di token [Token].

Answer 2

Eric Lippert's blog series on immutable binary trees potrebbe essere utile. Ovviamente, hai bisogno di un albero che non sia binario, ma ti darà l'idea generale.

Answer 3

Verificare definitivamente l'approccio del combinatore del parser monadico; Ne ho scritto il blog in C# e in F#.