2

演習/楽しいプロジェクトとして、Haskell でブレイン インタープリターを作成しようとしていますが、少し問題が発生しました。

Brainfuck の "while ループ" 構造は、一連のコマンドを括弧で囲んだだけです。[データコンストラクター内のループ内に演算子を格納する方法で構文ツリーを構築しようとしています。

これは、コマンドと構文「ツリー」のデータ宣言が現時点でどのように見えるかです。

data Operator = Plus
                | Minus
                | RShift 
                | LShift
                | Dot
                | Comma
                | SBracket [Operator]
                | EBracket
                deriving (Show, Eq)


type STree = [Operator]

私がやろうとしているのは、次のようStringなコマンドを取得して、次のよう"+><[.>]"に解析することSTreeです。

[Plus, RShift, LShift, SBracket [Dot, RShift], EBracket]

これまでのところ、 から 1 次元のリストしか取得できません。新しい演算子を の代わりに演算子リストに入れるためにString、リストの先頭が であるかどうかを確認する方法がわからないためです。SBracketメインリストの先頭。

解析を行うために使用している関数は次のとおりです。

matchChar :: Char -> Maybe Operator
matchChar c = case c of 
                '+' -> Just Plus
                '-' -> Just Minus
                '>' -> Just RShift  
                '<' -> Just LShift
                '.' -> Just Dot
                ',' -> Just Comma
                '[' -> Just (SBracket [])
                ']' -> Just EBracket
                _   -> Nothing

getChars :: [Char] -> STree
getChars str = foldr toOp [] str
    where 
            toOp x acc = case matchChar x of
                            Just a -> a:acc
                            Nothing -> acc

私ができるようにしたいのhead accは、 がSBracketインスタンスであるかどうかを確認することです。そうであれば、 newOperatorをリストに追加する代わりに、SBracketのリストに追加しOperatorます。

パターン マッチング ( toOp x ((SBracket list):xs) = ...) とリストの先頭の明示的なif head acc == SBracket ...チェック ( ) を試しましたが、どちらも正しく動作しません。

どんな助けでも素晴らしいでしょう！

4

1 に答える 1

7

まず、私はSBracket [Operator]justBracket STreeを再定義して を取り除きEBracketます。次に、パーサーを変更して、「現在の STree」と親のリストの両方を追跡します。ブラケットに遭遇するたびに、現在のツリーを親リストにプッシュし、新しいツリーを作成します。そして、終了ブラケットに遭遇したら、現在のツリーを取得し、Bracketコンストラクターでラップし、最初の親をポップオフし、その末尾にブラケットを追加して、それを現在のツリーにします。

これは完全にテストされていない (このコンプには ghc がない) バージョンで、動作する場合と動作しない場合があります。

data Operator = Plus
                | Minus
                | RShift
                | LShift
                | Dot
                | Comma
                | Bracket [Operator]
                deriving (Show, Eq)

parse :: [Char] -> Either String [Operator]
parse str = parse' str [] []
  where parse' :: [Char] -> [Operator] -> [[Operator]] -> Either String [Operator]
        parse' [] context [] = Right (reverse context)
        parse' [] context _ = Left "unclosed []"
        parse' (']':cs) _ [] = Left "unexpected ]"
        parse' (c:cs) ctx stack
            | c == '+' = parse' cs (Plus:ctx) stack
            | c == '-' = parse' cs (Minus:ctx) stack
            | c == '>' = parse' cs (RShift:ctx) stack
            | c == '<' = parse' cs (LShift:ctx) stack
            | c == '.' = parse' cs (Dot:ctx) stack
            | c == ',' = parse' cs (Comma:ctx) stack
            | c == '[' = parse' cs [] (ctx:stack)
            | c == ']' = parse' cs (Bracket (reverse ctx):s) tack
            | otherwise = parse' cs ctx stack
          where (s:tack) = stack
于 2012-07-13T03:04:45.497 に答える