根据规则集将字符串标记为字符串列表

Question

我有一个字符串需要标记为具有以下规则的列表：

'(' 和 ')' 括号
一个可能有小数点的数字
运算符（+、/、*、>= 等）
标识符以字母开头，字符串的其余部分可以是字母或数字

为此，我在 Haskell 代码中将上述规则创建为有限状态机：

data FsaState = R | Q -- start state: Q; success state R;
  deriving Show

输入：

tokenize “( (23.5+age) ∗ (20.99+adres))”

输出：

[ “(”, “ ”, “(”, “23.5”, “+”, “age”, “)”, “ ”, “∗”, “ ”, “(”, “20.99”, “+”, “adres”, “)”, “)” ]

（可能会过滤掉只有空格的字符串）

我应该如何开始？我陷入命令式思维，因为 Haskell 不是我的主要语言。

Answer 1

如果您担心效率，您可能应该定义一个标记数据类型 (data Token = ...)。也就是说，这是一个最小的分词器，它大致可以满足您的需求。它递归地工作（尾部），为每个递归调用咀嚼一个标记（或空格）。

我选择丢弃空格而不是将其变成标记。

import Data.Char

tokenize :: String -> [String]
tokenize "" = []
tokenize (c:cs)
  | isSpace c = tokenize cs
  | isAlpha c = let (i,cs') = span isAlphaNum cs in (c : i) : tokenize cs'
  | isDigit c = let (n,cs') = span isDigit cs
                in case cs' of
                     ('.':cs'') -> let (m,cs''') = span isDigit cs''
                                   in (c : n ++ "." ++ m) : tokenize cs'''
                     _ -> (c : n) : tokenize cs'
  | c `elem` "+/*-()" = [c] : tokenize cs
  | otherwise = error $ "unexpected character " ++ show c

这是实际操作：

ghci> tokenize "( (23.5+age) ∗ (20.99+adres))"
["(","(","23.5","+","age",")","*","(","20.99","+","adres",")",")"]

也就是说：我强烈建议您编写一个解析 monad（类似于 data Parser a = Parser { runParser :: String -> Maybe (a,String) }）以便您可以单子地编写解析器，或者使用现有的 library/tool（请参阅 Alex 和 megaparsec）

Answer 2

表示状态机的一种好方法是折叠。这是来自 Data.List 的 foldl' 的类型，一个 strict left fold:

foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

这种类型很一般，所以它可能有助于看到它的专业化，t ~ [] 和 a ~ Char:

foldl' :: (b -> Char -> b) -> b -> [Char] -> b

（还记得 type String = [Char]。）

所以foldl' step start input将从start状态开始运行对input的每个字符执行step函数，而[=76= 】最终状态。我们可以引入一种表示机器可能状态的类型，就像您在问题中开始做的那样：

data State
  = StartState
  | NameState String
  | IntegerState String
  | DecimalState String
  | OperatorState String
  | …

然而，我们的 step 函数不能只是类型 State -> Char -> State，因为我们也想要累积一个标记列表作为输出。我们可以只使用一对状态和累加器：

step :: (State, [Token]) -> Char -> (State, [Token])

（为了简单起见，我假设 type Token = String，但实际上您可能希望使用代数数据类型，例如 data Token = LeftParen | RightParen | Name String | Integer Int | …。）

所以到目前为止的基本结构是：

import Data.Char
import Data.List (foldl')

data State = …

tokenize :: String -> [Token]
tokenize input = reverse $ snd $ foldl' step (StartState, []) input
  where
    step :: (State, [Token]) -> Char -> (State, [Token])

（我们在最后使用 reverse 因为我们将通过将它们添加到列表中来累积标记 (O(1)) 而不是附加 (O(n))。）

现在您可以通过简单地填写案例来继续 - step 定义了机器中状态之间的转换。当我们想要发出一个令牌时，我们 return 一个新的令牌列表：

step (StartState, tokens) '(' = (StartState, "(" : tokens)
step (StartState, tokens) ')' = (StartState, ")" : tokens)

当我们想要执行状态转换时，我们return一个新的状态：

step (StartState, tokens) char

  -- Whitespace is ignored, looping back to the start state.
  | isSpace char = (StartState, tokens)

  -- Letters cause a transition to the “name” state.
  | isLetter char = (NameState [char], tokens)

  -- Digits, to the “integer” state.
  | isDigit char = (IntegerState [char], tokens)

  -- And so on.
  | char `elem` "+-*/^" = (OperatorState [char], tokens)
  | …

然后只需为所有其他状态实现转换即可。为了使这更容易，打开 -Wall 将产生有关您尚未处理的案例的警告。

例如，您可以通过以下方式实现 NameState 转换：

step (NameState name, tokens) char
  | isLetter char || isDigit char = (NameState (char : name), tokens)
  | otherwise = step (StartState, reverse name : tokens) char

当我们得到一个字母或数字时，我们将它累加到NameState；当我们得到其他东西时，我们将令牌和 return 发送到 StartState。但请注意，我们不只是说 otherwise = (StartState, reverse name : tokens)，因为这会丢弃该字符！相反，我们通过再次调用 step 来重试处于新状态的当前角色。

我将留给您解决如何处理输入结束的问题；提示：折叠完成后我们忘记检查一些东西。

这种方法相当有限；如果你想添加 monadic 效果，比如用 Either String [Token] 报告解析错误，那么你可能会发现它很笨拙。到那时，我会建议研究 monadic 解析库的工作原理。

根据规则集将字符串标记为字符串列表

Tokenize a string into a list of strings, dependent on set of rules

compiler-construction

string

haskell