如何使用GADT解析字符串到語法樹

我正在閱讀GADT介紹here，它發現限制程序員只創建正確類型的語法樹的想法很好，我把這個想法放入我的簡單lambda演算解釋器中，但後來我意識到我無法解析字符串到這個語法樹，因爲一個解析函數需要根據輸入返回不同類型的語法樹。這裏有一個例子：如何使用GADT解析字符串到語法樹

{-# LANGUAGE GADTs #-} 
data Ident 
data Lambda 
data Application 

data Expr a where 
    Ident :: String -> Expr Ident 
    Lambda :: Expr Ident -> Expr a -> Expr Lambda 
    Application :: Expr a -> Expr a -> Expr Application

使用GADTs之前，我用的是這樣的：

data Expr = Lambda Expr Expr 
      | Ident String 
      | Application Expr Expr

GADTs這裏有很大的優勢，bacuse現在我無法創建無效語法樹像Lambda (Application ..) ..。

但是對於GADT，我無法解析字符串並創建解析樹。下面是LAMBDA，訂貨號和應用表達式解析器：

ident :: Parser (Expr Ident) 
ident = ... 

lambda :: Parser (Expr Lambda) 
lambda = ... 

application :: Parser (Expr Application) 
application = ...

現在的問題是：

expr = choice [ident, application, lambda]

這顯然是行不通的，因爲每個解析器將返回不同的類型。

那麼，有沒有辦法解析一個字符串，並創建一個語法樹，與GADTs？

來源

2012-06-19 sinan

對於某些未知的a，您可以使用GADT製作一個包含Expr a的類型。

data AnyExpr where AnyExpr :: Expr a -> AnyExpr

在你不想限制Expr到一個特定的類型，使用AnyExpr情況。

anyExpr :: Parser (Expr a) -> Parser AnyExpr 
anyExpr p = fmap AnyExpr p 

expr :: Parser AnyExpr 
expr = choice [anyExpr ident, anyExpr application, anyExpr lambda]

來源

2012-06-19 15:45:35 Heatsink

這是一個好主意，謝謝！但我仍然懷疑我們是否有其他方法來做我想做的事情，以及我所做的是否是一個好主意。 – sinan

@sinan - 這很好，但另一種方法是定義兩個AST，一個用於解析輸出，另一個用於實際使用。解析輸出樹將是無類型的，工作AST將使用GADT，就像您已經實現的一樣。 –

如何使用GADT解析字符串到語法樹

回答

相關問題