4

だから私は、MegaParsec とモナド トランスフォーマーを理解するために、標準的な「スキームのような言語のパーサーを自分で作成する」演習を実行しようとしています。多くのチュートリアルやブログ投稿の提案に従って、レキシカル スコープを実装するためにReaderTandを使用しています。local

を実装しようとすると問題が発生しますlet*。と はどちらも同じ構文letをlet*共有し、後続の式で使用する変数をバインドします。2 つの違いはlet*、後続のバインドでバインディングを使用できることですが、そうではありletません。

(let ((x 1) (y 2)) (+ x y))       ; 3
(let* ((x 1) (y (+ x x)) (+ x y)) ; 3
(let ((x 1) (y (+ x x)) (+ x y))  ; Error unbound symbol "x"

私の問題は、式を解析するときlet*に、バインディングを現在のスコープに 1 つずつ追加して、各バインディングを後続のバインディングで使用できるようにする必要があることです。これはStateT;の良い使用例のようです。一度に 1 つのバインディングでローカル スコープを構築できます。次に、すべての新しいバインディングを解析した後、これらを親スコープから継承されたものと一緒に、 .let*経由で式の 3 番目の引数に渡すことができますlocal。

次のようにモナド変換スタックを構築します。

type Parser = Parsec Void String
type Env = Map.Map String Float
type RSParser = ReaderT Env (StateT Env Parser)

そして、ここにパーサーを示します。これは、要点を述べながら、できる限り単純化したものです。特に、Floatが唯一のデータ型であり+、 、*、およびlet*が唯一のコマンドです。

data Op = Plus | Times

spaceConsumer :: Parser ()
spaceConsumer = Lexer.space space1
                            (Lexer.skipLineComment ";")
                            (Lexer.skipBlockComment "#|" "|#")
lexeme :: Parser a -> RSParser a
lexeme = lift . lift . Lexer.lexeme spaceConsumer

lParen, rParen :: RSParser Char
lParen = lexeme $ char '('
rParen = lexeme $ char ')'

plus, times :: RSParser Op
plus = lexeme $ char '+' $> Plus
times = lexeme $ char '*' $> Times

keyValuePair :: RSParser ()
keyValuePair = between lParen rParen $ do
    state <- get
    name  <- lift . lift $ Lexer.lexeme spaceConsumer (some letterChar)
    x     <- num
    modify (union (fromList [(name, x)]))

keyValuePairs :: RSParser ()
keyValuePairs = between lParen rParen (many keyValuePair) $> ()

num :: RSParser Float
num = lexeme $ Lexer.signed (return ()) Lexer.float

expr, var :: RSParser Float
expr = num <|> var <|> between lParen rParen (arithExpr <|> letStarExpr)
var = do
    env <- ask
    lift . lift $ do
        name <- Lexer.lexeme spaceConsumer (some letterChar)
        case Map.lookup name env of
            Nothing -> mzero
            Just x  -> return x
arithExpr = do
    op   <- (plus <|> times) <?> "operation"
    args <- many (expr <?> "argument")
    return $ case op of
        Plus  -> sum args
        Times -> product args
letStarExpr = lexeme (string "let*") *> do
    keyValuePairs
    bindings <- get
    local (Map.union bindings) expr

main :: IO ()
main = do
    parseTest (runStateT (runReaderT expr (fromList [("x", 1)])) Map.empty)
              "(+ (let* ((x 666.0)) x) x)"
        -- (667.0,fromList [("x",666.0)]) Ok
    parseTest (runStateT (runReaderT expr (fromList [("x", 1)])) Map.empty)
              "(+ (let* ((x 666.0)) x) (let* ((w 0.0)) x))"
        -- (1332.0,fromList [("x",666.0)]) Wrong

上記の最初のテストは成功しますが、2 番目のテストは失敗します。x最初の式で のバインディングを保持する可変状態let*が 2 番目の式に引き継がれるため、失敗しますlet*。この可変状態を問題の計算に対してローカルにする方法が必要ですが、これは私が行う方法がわかりません。forlocalからのコマンドの類似物はありますか? 間違ったモナド変換スタックを使用していませんか? 私のアプローチは根本的に間違っていますか？ReaderState

私が試した単純な（振り返ってみると）解決策は、ステートメントを次のようにlet*追加して、各式で可変状態をリセットすることです。put Map.emptyletStarExpr

letStarExpr = lexeme (string "let*") *> do
    keyValuePairs
    bindings <- get
    put Map.empty
    local (Map.union bindings) expr

しかし、これはネストされた式と互換性がありませんlet*:

parseTest (runStateT (runReaderT expr (fromList [("x", 1)])) Map.empty)
    (let* ( (x 666.0) (y (let* ((z 3.0)) z)) ) x)

666.0 の代わりに 1.0 を返します。

何か案は？

4

1 に答える 1