代码之家 › 专栏 › 技术社区 › ChaosPandion

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

state-machine functional-programming data-structures language-agnostic parsing

ChaosPandion · 技术社区 · 14 年前

给定一个 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

请注意

我将提供一个很好的赏金给最好的答案,所以不要着急。只发布链接的答案与显示代码或包含详细解释的答案相比,权重更小。

期末笔记

我对这种东西真的很陌生,所以不要害怕叫我笨蛋。

3 回复 | 直到 14 年前

Heinrich Apfelmus 14 年前

你想解析抽象语法树中的内容。

在纯函数编程语言haskell中,可以使用 分析器组合器 表达你的语法。下面是一个解析微小表达式语言的示例:

编辑使用一元风格来匹配格雷厄姆·赫顿的书

    -- 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))

要了解更多关于解析器组合器的信息,请参见例如第8章 Graham Hutton's book "Programming in Haskell" 或 chapter 16 “现实世界的哈斯克尔”。

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

Brian 14 年前

一定要看看单语法分析器组合器方法;我已经在博客上写过了。 in C# 和 in F# .

Craig Stuntz 14 年前

Eric Lippert blog series on immutable binary trees 可能会有所帮助。显然,你需要一个不是二叉树的树,但是它会给你一个大致的概念。