什么是用于以功能纯粹的方式生成不可变具体语法树的适当数据结构或算法？

Question

给定LL(1)语法什么是以功能纯粹的方式生成不可变具体语法树的适当数据结构或算法？请随意用您喜欢的任何语言编写示例代码.

我的想法

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

这是我一直在思考的一个想法.这里的主要问题是处理语法错误.我的意思是我可以停在第一个错误,但这似乎不对.

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 

请注意

我将提供一个很好的赏金给最好的答案,所以不要感到匆忙.简单地发布链接的答案对显示代码或包含详细解释的答案的权重较小.

最后的说明

我对这种东西真的很陌生,所以不要害怕称我为傻瓜.

Answer 1

您想要将某些内容解析为抽象语法树.

在纯函数式编程语言Haskell中,您可以使用解析器组合器来表达您的语法.这是一个解析微小表达式语言的例子:

编辑使用monadic风格来匹配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

这是一个示例运行:

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

要了解有关解析器组合器的更多信息,请参阅Graham Hutton的书"Haskell中的编程"或"Real World Haskell"的第16章中的第8 章.

许多解析器组合器库可以与您打算使用不同的令牌类型一起使用.令牌流通常表示为令牌列表[Token].