3

我在尝试用 Haskell 编写的这个程序方面需要帮助。我已经写了大部分内容，这就是我基本上想要做的事情：

  1. 当我写

解析“a + b”

在终端中，我希望将其作为输出：

加号（单词“a”）（单词“b”）

  1. 当我写

解析“a - 2 * b + c”

在终端中，我希望将其作为输出：

减号 (单词 "a") (加号 (Mult (Num 2) (单词 "b")) (单词 "c"))

到目前为止我的代码：

data Ast
    = Word String
    | Num Int
    | Mult Ast Ast
    | Plus Ast Ast
    | Minus Ast Ast
    deriving (Eq, Show)

tokenize :: [Char] -> [String]
tokenize [] = []
tokenize (' ' : s) = tokenize s
tokenize ('+' : s) = "+" : tokenize s
tokenize ('*' : s) = "*" : tokenize s
tokenize (c : s)
  | isDigit c =
    let (cs, s') = collectWhile isDigit s
     in (c : cs) : tokenize s'
  | isAlpha c =
    let (cs, s') = collectWhile isAlpha s
     in (c : cs) : tokenize s'
  | otherwise = error ("unexpected character " ++ show c)

collectWhile :: (Char -> Bool) -> String -> (String, String)
collectWhile p s = (takeWhile p s, dropWhile p s)

isDigit, isAlpha :: Char -> Bool
isDigit c = c `elem` ['0' .. '9']
isAlpha c = c `elem` ['a' .. 'z'] ++ ['A' .. 'Z']

parseU :: [String] -> (Ast, [String])
parseU ("+" : s0) =
  let (e1, s1) = parseU s0
      (e2, s2) = parseU s1
   in (Plus e1 e2, s2)
parseU ("*" : s0) =
  let (e1, s1) = parseU s0
      (e2, s2) = parseU s1
   in (Mult e1 e2, s2)
parseU (t : ts)
  | isNumToken t = (Num (read t), ts)
  | isWordToken t = (Word t, ts)
  | otherwise = error ("unrecognized token " ++ show t)
parseU [] = error "unexpected end of input"

isNumToken, isWordToken :: String -> Bool
isNumToken xs = takeWhile isDigit xs == xs
isWordToken xs = takeWhile isAlpha xs == xs

parse :: String -> Ast
parse s =
  case parseU (tokenize s) of
    (e, []) -> e
    (_, t : _) -> error ("unexpected token " ++ show t)

inn :: Ast -> String
inn (Plus x y) = innP x ++ " + " ++ innP y
inn (Mult x y) = innP x ++ " * " ++ innP y
inn ast = innP ast

innP :: Ast -> String
innP (Num n) = show n
innP (Plus x y) = "(" ++ innP x ++ " + " ++ innP y ++ ")"
innP (Mult x y) = "(" ++ innP x ++ " * " ++ innP y ++ ")"
innP (Word w) = w -- 

innfiks :: String -> String
innfiks s = inn (parse s)

现在我在终端中发布我写的文本时出错，但是当我这样写时：

解析“+ a b”

我得到正确的输出：

加号（单词“a”）（单词“b”）

我知道我必须更改代码，以便它接受我在此表单上发送到解析函数的内容：

值运算符值，

而不是这种形式：

运营商价值价值

但是我正在努力找出我必须在哪里以及在哪里做这个改变。

4

1 回答 1

3

为了处理具有优先级的中缀运算符，一种方法是引入与优先级相对应的一系列解析函数。因此，如果您有可以乘以创建“项”的“因素”，可以添加或减去创建“表达式”的“项”，您将需要为每个级别创建解析器函数。解析“因素”（即，单词或数字）很容易，因为您已经编写了代码：

parseFactor :: [String] -> (Ast, [String])
parseFactor (t : ts)
  | isNumToken t = (Num (read t), ts)
  | isWordToken t = (Word t, ts)
  | otherwise = error ("unrecognized token " ++ show t)
parseFactor [] = error "unexpected end of input"

解析一个术语比较棘手。您希望首先解析一个因子，然后可选地，a*后跟另一个因子，然后将其视为一个术语，以进一步可选地乘以另一个因子，依此类推。以下是一种方法：

parseTerm :: [String] -> (Ast, [String])
parseTerm ts
  =  let (f1, ts1) = parseFactor ts     -- parse first factor
     in  go f1 ts1
  where go acc ("*":ts2)                -- add a factor to an accumulating term
          = let (f2, ts3) = parseFactor ts2
            in go (Mult acc f2) ts3
        go acc rest = (acc, rest)       -- no more factors: return the term

如果您愿意，请尝试编写类似于parseExpr以+字符分隔的解析术语（暂时跳过减法），并在以下内容上进行测试：

parseExpr (tokenize "2 + 3 * 6 + 4 * 8 * 12 + 1")

对于剧透，这是一个同时处理+和的版本-，但请注意，您的标记器尚未正确处理减法，因此您必须先修复它。

parseExpr :: [String] -> (Ast, [String])
parseExpr ts
  =  let (f1, ts1) = parseTerm ts
     in  go f1 ts1
  where go acc (op:ts2)
          | op == "+" || op == "-"
          = let (f2, ts3) = parseTerm ts2
            in go ((astOp op) acc f2) ts3
        go acc rest = (acc, rest)
        astOp "+" = Plus
        astOp "-" = Minus

有了它，您可以指向parse正确的解析器：

parse :: String -> Ast
parse s =
  case parseExpr (tokenize s) of
    (e, []) -> e
    (_, t : _) -> error ("unexpected token " ++ show t)

你的例子应该有效：

λ> parse "a - 2 * b + c"
Plus (Minus (Word "a") (Mult (Num 2) (Word "b"))) (Word "c")

请注意，这与您所说的想要的输出略有不同，但这种排序对于左关联运算符是正确的（这对于正确处理很重要-）。也就是说，你想要：

5 - 4 + 1

解析为：

(5 - 4) + 1  -- i.e., (Plus (Minus (Num 5) (Num 4)) (Num 1))

以便评估者计算 2 的正确答案。如果将其解析为：

5 - (4 + 1)  -- i.e., (Minus (Num 5) (Plus (Num 4) (Num 1)))

您的评估员会计算出错误答案 0。

但是，如果您真的想使用右关联运算符进行解析，请参见下文。

左关联运算符的完整修改代码：

data Ast
    = Word String
    | Num Int
    | Mult Ast Ast
    | Plus Ast Ast
    | Minus Ast Ast
    deriving (Eq, Show)

tokenize :: [Char] -> [String]
tokenize [] = []
tokenize (' ' : s) = tokenize s
tokenize ('-' : s) = "-" : tokenize s
tokenize ('+' : s) = "+" : tokenize s
tokenize ('*' : s) = "*" : tokenize s
tokenize (c : s)
  | isDigit c =
    let (cs, s') = collectWhile isDigit s
     in (c : cs) : tokenize s'
  | isAlpha c =
    let (cs, s') = collectWhile isAlpha s
     in (c : cs) : tokenize s'
  | otherwise = error ("unexpected character " ++ show c)

collectWhile :: (Char -> Bool) -> String -> (String, String)
collectWhile p s = (takeWhile p s, dropWhile p s)

isDigit, isAlpha :: Char -> Bool
isDigit c = c `elem` ['0' .. '9']
isAlpha c = c `elem` ['a' .. 'z'] ++ ['A' .. 'Z']

parseFactor :: [String] -> (Ast, [String])
parseFactor (t : ts)
  | isNumToken t = (Num (read t), ts)
  | isWordToken t = (Word t, ts)
  | otherwise = error ("unrecognized token " ++ show t)
parseFactor [] = error "unexpected end of input"

parseTerm :: [String] -> (Ast, [String])
parseTerm ts
  =  let (f1, ts1) = parseFactor ts
     in  go f1 ts1
  where go acc ("*":ts2)
          = let (f2, ts3) = parseFactor ts2
            in go (Mult acc f2) ts3
        go acc rest = (acc, rest)

parseExpr :: [String] -> (Ast, [String])
parseExpr ts
  =  let (f1, ts1) = parseTerm ts
     in  go f1 ts1
  where go acc (op:ts2)
          | op == "+" || op == "-"
          = let (f2, ts3) = parseTerm ts2
            in go ((astOp op) acc f2) ts3
        go acc rest = (acc, rest)
        astOp "+" = Plus
        astOp "-" = Minus

isNumToken, isWordToken :: String -> Bool
isNumToken xs = takeWhile isDigit xs == xs
isWordToken xs = takeWhile isAlpha xs == xs

parse :: String -> Ast
parse s =
  case parseExpr (tokenize s) of
    (e, []) -> e
    (_, t : _) -> error ("unexpected token " ++ show t)

对于右结合运算符，修改这些定义：

parseTerm :: [String] -> (Ast, [String])
parseTerm ts
  =  let (fct, ts1) = parseFactor ts
     in  case ts1 of
           "*":ts2 -> let (trm, rest) = parseTerm ts2
                      in  (Mult fct trm, rest)
           _       -> (fct, ts1)

parseExpr :: [String] -> (Ast, [String])
parseExpr ts
  =  let (trm, ts1) = parseTerm ts
     in  case ts1 of
           op:ts2 | op == "+" || op == "-"
                   -> let (expr, rest) = parseExpr ts2
                      in  (astOp op trm expr, rest)
           _       -> (trm, ts1)
  where astOp "+" = Plus
        astOp "-" = Minus*
于 2020-09-24T17:42:00.967 回答