3

私は Parsec を使って単純な Lisp パーサーを作成しています。

パーサー タイプにカスタム ADT を使用する場合と標準のツリーを使用する場合の (つまりData.Tree) 利点は何ですか?

両方の方法を試した後、カスタム ADT のいくつかのポイント (つまりParser ASTNode)を思いつきました。

  • はるかに明確で単純なようです
  • 他の人はこの方法でそれを行いました（Parsecにバンドルされている/バンドルされていたTigerを含む）

と反対（すなわちParser (Tree ASTNode)：

  • Data.TreeFunctor、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) []]])

    （書式設定については申し訳ありません-うまくいけば、それは明らかです）

4

1 に答える 1

4

解釈/コンパイル/言語分析は一般的にあなたの言語の構造によって非常に駆動されるので、私は絶対に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にどのようなものを持ちたいですか？タイプパラメータはありません...

于 2012-08-09T17:53:07.610 に答える