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

Question

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

与使用标准树(即 Data.Tree)相比，为解析器类型使用自定义 ADT 的优点是什么？

在尝试了这两种方法之后，我为自定义 ADT(即 Parser ASTNode)提出了几点:

• 似乎更清晰、更简单
• 其他人已经这样做了(包括 Tiger ，它与 Parsec 捆绑在一起)

和一个反对(即解析器(Tree ASTNode):

• Data.Tree已经有Functor、Monad等实例，这对于语义分析、评估、计算代码统计将会非常有帮助

<小时/>

例如:

1. 自定义 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]])
   

2. 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) []]])
   

   (对格式感到抱歉——希望它是清楚的)

Answer 1

我绝对会选择 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

无论如何，您希望在 AST 上使用哪种Functor？上面没有类型参数...