Haskell-具有状态的Parsec

问题描述 投票：1回答：2

我有一个文件，其中游戏状态以String格式保存。该字符串包含一个动作列表，以,分隔。从这个动作列表中，我必须重构游戏状态。因此，从概念上讲，对于我解析的每个动作，我都希望适当地修改游戏状态，并将该游戏状态传递给下一个动作的解析。从概念上讲，这等效于在开始时有一个空列表，并且对于每个移动，将已解析的移动限制为该列表。最后，您应该具有所有已分析动作的列表。

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

parseExample :: State -> Parser [Char]
parseExample someState = do spaces 
                            c <- char 
                            c : someState
                            return someState
parsing haskell parsec
2个回答
0
投票

您可能想使用foldl（如果我正确理解了您的问题）。因此，您将得到一个类似如下的函数：

module Main where

import Data.Text
import Data.String

main :: IO ()
main =
  putStrLn (show $ parseGameState "a, b, c")

data State = State deriving (Show)

parseGameState :: String -> [State]
parseGameState stateString = parsedState where
  parsedState = Prelude.foldl mkNewStateFromPreviousAndMove [] moves where
    moves = splitOn (fromString ",") (fromString stateString)
    mkNewStateFromPreviousAndMove oldStates move = oldStates ++ [newState previousState move] where
      previousState = Prelude.last oldStates
      newState previousState move = State

这是在做：

以CSV移动字符串作为输入。

然后将字符串拆分为移动字符串列表。

然后，我们从一个空列表开始，通过将mkNewStateFromPreviousAndMove应用于移动列表中的每个元素以及该列表由折叠创建的最后一个元素，将移动字符串折叠到此列表中。

注意，您需要将以下deps添加到package.yaml文件中（如果使用堆栈）：

  • 文本

此dep用于拆分字符串。

0
投票

将“状态”合并到解析器中的最简单方法是完全不执行此操作。假设我们有一个井字游戏板：

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

这应该是您解决此类问题的最佳方法：首先解析为简单的无状态中间形式，然后以“有状态”计算处理该中间形式。

如果您really要在解析过程中建立状态，则有几种方法可以做到。在这种特殊情况下，给定上面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是monad变压器，所以将创建具有标准ParsecT ... (State Board)层的State monad变压器堆栈。例如：

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 **行时，可以修改状态以正确地解析后续表达式。使用用户状态实际建立解析的result不是预期的用法。

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

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"
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.