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

Question

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

我的想法

symbol : either a token or a noderesult : success or failuretoken : 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 tokennode : 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

Here is an idea I have been thinking about. The main issue here is handling syntax errors.I mean I could stop at the first error but that doesn't seem right.

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 中，您可以使用解析器组合器来表达您的语法。这是一个解析小型表达式语言的示例:

编辑使用单子(monad)风格来匹配 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's book "Programming in Haskell" 的第 8 章。或chapter 16 “现实世界的 Haskell”。

许多解析器组合器库可以按照您的意愿与不同的标记类型一起使用。 token 流通常表示为 token 列表[Token]。