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]

到目前为止，我只能从 中得到一个一维列表String，因为我不确定如何检查列表的头部是否是 aSBracket以便将新运算符放入它的运算符列表而不是 at主列表的负责人。

这是我用来进行解析的函数：

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列表中，而是将其添加到列表中。SBracketOperator

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

任何帮助都会很棒！

4

1 回答 1

7

首先，我将重新定义SBracket [Operator]为 justBracket STree并摆脱EBracket. 然后我会更改您的解析器以跟踪“当前 STree”以及父母列表。每次遇到括号时，都会将当前树推送到父列表并创建新树。当你遇到一个结束括号时，你取出你当前的树，用Bracket构造函数包装它，弹出你的第一个父级，将括号添加到它的末尾并使其成为你当前的树。

这是一个完全未经测试的（在这个 comp 上没有 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 回答