haskell - 如何检查 Haskell 中的数据类型？

Question

我正在尝试用 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]

到目前为止，我只能从 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实例，如果是这样，则不要在前面添加新的 Operator在列表中，将其添加到 SBracket 前面的Operator列表。

我尝试过模式匹配 ( toOp x ((SBracket list):xs) = ... ) 以及尝试显式检查列表的头部 ( if head acc == SBracket ... )，但这些都不能正常工作。

任何帮助都会很棒!

Answer 1

首先，我将 SBracket [Operator] 重新定义为 Bracket 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