parsing - Haskell - Parsec 与状态

Question

我有一个文件，其中游戏状态保存在 String 中。格式。该字符串由一系列移动组成，由 , 分隔。 .从这个 Action 列表中，我必须重建游戏状态。因此，从概念上讲，对于我解析的每一步，我想适本地修改游戏状态并将这个游戏状态传递给下一步的解析。从概念上讲，这可能等同于在开始时有一个空列表，并且对于每个移动都将解析的移动到该列表。最后，您应该有一个包含所有解析 Action 的列表。

我将下面的代码示例作为一个简化版本来解析 alfabetic 字母并将它们推送到列表中。我想学习的核心概念是如何拥有一个初始状态，为每个解析周期传递它并使用 parsec 返回最终状态。 someState最初是空列表。

parseExample :: State -> Parser [Char]
parseExample someState = do spaces 
                            c <- char 
                            c : someState
                            return someState

Answer 1

将“状态”合并到解析器中的最简单方法是根本不这样做。假设我们有一个井字棋盘:

data Piece = X | O | N deriving (Show)
type Board = [[Piece]]

解析移动列表:

X11,O00,X01

成板 [[O,X,N],[N,X,N],[N,N,N]]代表游戏状态:

 O | X |
---+---+---
   | X |
---+---+---
   |   |

我们可以分离解析器，它只生成一个移动列表:

data Move = Move Piece Int Int
moves :: Parser [Move]
moves = sepBy move (char ',')
  where move = Move <$> piece <*> num <*> num
        piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

来自重新生成游戏状态的函数:

board0 :: Board
board0 = [[N,N,N],[N,N,N],[N,N,N]]

game :: [Move] -> Board
game = foldl' turn board0

turn :: Board -> Move -> Board
turn brd (Move p r c) = brd & ix r . ix c .~ p

然后将它们连接在一起 loadGame功能:

loadGame :: String -> Board
loadGame str =
  case parse moves "" str of
    Left err -> error $ "parse error: " ++ show err
    Right mvs -> game mvs

这应该是此类问题的首选解决方案:首先解析为简单的无状态中间形式，然后在“有状态”计算中处理该中间形式。

如果你真的想在解析过程中建立状态，有几种方法可以做到。在这种特殊情况下，给定 turn 的定义上面，我们可以直接解析成 Board通过合并来自 game 的折叠函数进入解析器:

moves1 :: Parser Board
moves1 = foldl' turn board0 <$> sepBy move (char ',')
  where move = Move <$> piece <*> num <*> num
        piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

但是如果您有多个解析器需要对单个底层状态进行操作，这将不会很好地概括。

要通过一组解析器实际线程化一个状态，您可以使用 Parsec 的“用户状态”功能。使用 Board 定义解析器用户状态:

type Parser' = Parsec String Board

然后是修改用户状态的单个移动的解析器:

move' :: Parser' ()
move' = do
  m <- Move <$> piece <*> num <*> num
  modifyState (flip turn m)
  where piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

请注意 move'的返回类型是 ()因为它的操作是作为对用户状态的副作用实现的。

现在，简单地解析移动列表的行为:

moves' :: Parser' ()
moves' = sepBy move' (char ',')

将生成最终的游戏状态:

loadGame' :: String -> Board
loadGame' str =
  case runParser (moves' >> getState) [[N,N,N],[N,N,N],[N,N,N]] "" str of
    Left err -> error $ "parse error: " ++ show err
    Right brd -> brd

在这里， loadGame'使用 moves' 在用户状态上运行解析器然后使用 getState调用以获取最终板。

一个几乎等效的解决方案，因为 ParsecT是一个monadtransformer，是创建一个 ParsecT ... (State Board)具有标准的 monad 变压器堆栈 State层。例如:

type Parser'' = ParsecT String () (Control.Monad.State.State Board)

move'' :: Parser'' ()
move'' = do
  m <- Move <$> piece <*> num <*> num
  modify (flip turn m)
  where piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

moves'' :: Parser'' ()
moves'' = void $ sepBy move'' (char ',')

loadGame'' :: String -> Board
loadGame'' str =
  case runState (runParserT moves'' () "" str) board0 of
    (Left err, _)   -> error $ "parse error: " ++ show err
    (Right (), brd) -> brd

然而，这两种在解析时建立状态的方法都是奇怪的和非标准的。以这种形式编写的解析器将比标准方法更难理解和修改。此外，用户状态的预期用途是维护解析器决定如何执行实际解析所必需的状态。例如，如果您正在解析具有动态运算符优先级的语言，您可能希望将当前的运算符优先级集保持为状态，因此在解析 infixr 8 ** 时行，您可以修改状态以正确解析后续表达式。使用用户状态来实际构建解析的结果不是预期的用途。

无论如何，这是我使用的代码:

import Control.Lens
import Control.Monad
import Control.Monad.State
import Data.Foldable
import Text.Parsec
import Text.Parsec.Char
import Text.Parsec.String

data Piece = X | O | N deriving (Show)
type Board = [[Piece]]

data Move = Move Piece Int Int

-- *Standard parsing approach

moves :: Parser [Move]
moves = sepBy move (char ',')
  where move = Move <$> piece <*> num <*> num
        piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

board0 :: Board
board0 = [[N,N,N],[N,N,N],[N,N,N]]

game :: [Move] -> Board
game = foldl' turn board0

turn :: Board -> Move -> Board
turn brd (Move p r c) = brd & ix r . ix c .~ p

loadGame :: String -> Board
loadGame str =
  case parse moves "" str of
    Left err -> error $ "parse error: " ++ show err
    Right mvs -> game mvs

-- *Incoporate fold into parser

moves1 :: Parser Board
moves1 = foldl' turn board0 <$> sepBy move (char ',')
  where move = Move <$> piece <*> num <*> num
        piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

-- *Non-standard effectful parser

type Parser' = Parsec String Board

move' :: Parser' ()
move' = do
  m <- Move <$> piece <*> num <*> num
  modifyState (flip turn m)
  where piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

moves' :: Parser' ()
moves' = void $ sepBy move' (char ',')

loadGame' :: String -> Board
loadGame' str =
  case runParser (moves' >> getState) board0 "" str of
    Left err -> error $ "parse error: " ++ show err
    Right brd -> brd

-- *Monad transformer stack

type Parser'' = ParsecT String () (Control.Monad.State.State Board)

move'' :: Parser'' ()
move'' = do
  m <- Move <$> piece <*> num <*> num
  modify (flip turn m)
  where piece = X <$ char 'X' <|> O <$ char 'O'
        num = read . (:[]) <$> digit

moves'' :: Parser'' ()
moves'' = void $ sepBy move'' (char ',')

loadGame'' :: String -> Board
loadGame'' str =
  case runState (runParserT moves'' () "" str) board0 of
    (Left err, _)   -> error $ "parse error: " ++ show err
    (Right (), brd) -> brd

-- *Tests

main = do
  print $ loadGame   "X11,O00,X01"
  print $ loadGame'  "X11,O00,X01"
  print $ loadGame'' "X11,O00,X01"