在函数式编程中，生成不可变的具体语法树的适当数据结构或算法是什么？

Question

在函数式编程中，生成不可变的具体语法树的适当数据结构或算法是什么？

parsinglanguage-agnosticdata-structuresfunctional-programmingstate-machine

7

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

symbol：标记或节点
result：成功或失败
token：源文本中的词汇标记
    value->string：标记的值
    type->integer：标记的命名类型代码
    next->token：读取下一个标记并保留上一个标记的位置
    back->token：返回到上一个位置并重新读取标记
node：语法树中的节点
    type->integer：节点的命名类型代码
    symbols->linkedList：在此节点找到的符号
    append->symbol->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

请注意

我将为最佳答案提供慷慨的奖励，所以不要感到匆忙。仅发布链接的答案比展示代码或包含详细解释的答案权重更小。

最后声明

我对这种东西真的很新，所以不要害怕称呼我为笨蛋。

- ChaosPandion

1

自下而上组成的树有什么问题吗？ - Ira Baxter

@Ira - 你告诉我吧，我对这一切都很新。 - ChaosPandion

由于猜测之前的知识很难，您可能希望对答案进行评论并要求澄清。 - Heinrich Apfelmus

@Heinrich - 我打算这么做，只是需要一些时间来处理信息。 - ChaosPandion

3个回答

2

一定要查看单子解析器组合方法；我已经在C#和F#中写过博客。

- Brian

0

Eric Lippert的关于不可变二叉树的博客系列可能会有所帮助。显然，你需要一个不是二叉的树，但它会给你一个大致的想法。

- Craig Stuntz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Heinrich Apfelmus · Accepted Answer

你想将某些东西解析为抽象语法树。

在纯函数式编程语言Haskell中，您可以使用解析器组合器来表达您的语法。这里是一个解析微小表达语言的示例：编辑使用单子样式匹配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编程》的第8章或者《Real World Haskell》的第16章。

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