parsing - 自定义 ADT 与解析器返回值的树

Question

我正在使用 Parsec 构建一个简单的 Lisp 解析器。

对解析器类型使用自定义 ADT 与使用标准树（即Data.Tree）相比有什么（缺点）优势？

在尝试了两种方式之后，我为自定义 ADT 提出了几点意见（即Parser ASTNode）：

似乎更加清晰和简单
其他人已经这样做了（包括Tiger，它与 Parsec 捆绑在一起）

一个反对（即Parser (Tree ASTNode)：

Data.Tree已经有Functor、Monad等实例，对语义分析、评估、计算代码统计会有很大帮助

例如：

自定义 ADT

import Text.ParserCombinators.Parsec


data ASTNode 
  = Application ASTNode [ASTNode]
  | Symbol String
  | Number Float
  deriving (Show)


int :: Parser ASTNode
int = many1 digit >>= (return . Number . read)


symbol :: Parser ASTNode
symbol = many1 (oneOf ['a'..'z']) >>= (return . Symbol)


whitespace :: Parser String
whitespace = many1 (oneOf " \t\n\r\f")


app :: Parser ASTNode
app =
  char '(' >>
  sepBy1 expr whitespace >>= (\(e:es) ->
  char ')' >>
  (return $ Application e es))


expr :: Parser ASTNode
expr =  symbol  <|>  int  <|>  app

示例使用：

ghci> parse expr "" "(a 12 (b 13))"
Right 
  (Application 
    (Symbol "a") 
    [Number 12.0, Application 
                    (Symbol "b") 
                    [Number 13.0]])

Data.Tree

import Text.ParserCombinators.Parsec
import Data.Tree


data ASTNode 
  = Application (Tree ASTNode)
  | Symbol String
  | Number Float
  deriving (Show)


int :: Parser (Tree ASTNode)
int = many1 digit >>= (\x -> return $ Node (Number $ read x) [])


symbol :: Parser (Tree ASTNode)
symbol = many1 (oneOf ['a' .. 'z']) >>= (\x -> return $ Node (Symbol x) [])


whitespace :: Parser String
whitespace = many1 (oneOf " \t\n\r\f")


app :: Parser (Tree ASTNode)
app =
  char '(' >>
  sepBy1 expr whitespace >>= (\(e:es) ->
  char ')' >>
  (return $ Node (Application e) es))


expr :: Parser (Tree ASTNode)
expr =  symbol  <|>  int  <|>  app

和示例使用：

ghci> parse expr "" "(a 12 (b 13))"
Right
 (Node
   (Application 
     (Node (Symbol "a") []))
   [Node (Number 12.0) [],
    Node 
      (Application 
        (Node (Symbol "b") []))
      [Node (Number 13.0) []]])

（对不起格式 - 希望它很清楚）

score 4 · Accepted Answer

我绝对会选择 AST，因为解释/编译/语言分析通常很大程度上取决于您的语言结构。AST 将简单自然地代表和尊重该结构，而Tree两者都不会。

例如，语言实现技术的一种常见形式是通过翻译来实现一些复杂的特性：将涉及这些特性或结构的程序翻译成不使用它们的语言子集的程序（例如，Lisp 宏都是对这个）。例如，如果您使用 AST，类型系统通常会禁止您生成非法翻译作为输出。而不了解您的程序的Tree类型将无济于事。

您的 AST 看起来并不复杂，因此为它编写实用函数应该不难。以这个为例：

foldASTNode :: (r -> [r] -> r) -> (String -> r) -> (Float -> r) -> r
foldASTNode app sym num node = 
    case node of
      Application f args -> app (subfold f) (map subfold args)
      Symbol str         -> sym str
      Number n           -> num n
    where subfold = foldASTNode app sym num

无论如何，Functor你希望在你的 AST 上有什么类型的？上面没有类型参数...

parsing - 自定义 ADT 与解析器返回值的树

1 回答 1

Related

Reference