8

我正在尝试通过实现一个小型正则表达式解析器来学习 Parsec。在 BNF 中，我的语法类似于：

EXP  : EXP *
     | LIT EXP
     | LIT

我试图在 Haskell 中实现这一点：

expr = try star
       <|> try litE
       <|> lit

litE  = do c <- noneOf "*"
           rest <- expr
           return (c : rest)

lit   = do c <- noneOf "*"
           return [c]

star = do content <- expr
          char '*'
          return (content ++ "*")

但是这里有一些无限循环（例如 expr -> star -> expr 而不消耗任何令牌），这使得解析器永远循环。不过，我不确定如何修复它，因为它的本质star是它最终会消耗其强制性令牌。

有什么想法吗？

4

2 回答 2

12

你应该使用Parsec.Expr.buildExprParser; 它非常适合此目的。您只需描述您的运算符、它们的优先级和关联性，以及如何解析原子，组合器就会为您构建解析器！

您可能还希望添加使用括号对术语进行分组的功能，以便您可以应用于*多个文字。

这是我的尝试（我投入了|, +, 和?很好的衡量标准）：

import Control.Applicative
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr

data Term = Literal Char
          | Sequence [Term]
          | Repeat (Int, Maybe Int) Term
          | Choice [Term]
  deriving ( Show )

term :: Parser Term
term = buildExpressionParser ops atom where

  ops = [ [ Postfix (Repeat (0, Nothing) <$ char '*')
          , Postfix (Repeat (1, Nothing) <$ char '+')
          , Postfix (Repeat (0, Just 1)  <$ char '?')
          ]
        , [ Infix (return sequence) AssocRight
          ]
        , [ Infix (choice <$ char '|') AssocRight
          ]
        ]

  atom = msum [ Literal <$> lit
              , parens term
              ]

  lit = noneOf "*+?|()"
  sequence a b = Sequence $ (seqTerms a) ++ (seqTerms b)
  choice a b = Choice $ (choiceTerms a) ++ (choiceTerms b)
  parens = between (char '(') (char ')')

  seqTerms (Sequence ts) = ts
  seqTerms t = [t]

  choiceTerms (Choice ts) = ts
  choiceTerms t = [t]

main = parseTest term "he(llo)*|wor+ld?"
于 2012-01-27T17:28:52.047 回答
6

你的语法是左递归的，它不能很好地与try，因为 Parsec 会反复回溯。有几种方法可以解决这个问题。可能最简单的方法是*在另一个规则中设置可选：

lit :: Parser (Char, Maybe Char)
lit = do
  c <- noneOf "*"
  s <- optionMaybe $ char '*'
  return (c, s)

当然，无论如何，您可能最终都会将事物包装在数据类型中，并且有很多方法可以解决这个问题。这是一个，在我的脑海中：

import Control.Applicative ((<$>))

data Term = Literal Char
          | Sequence [Term]
          | Star Term

expr :: Parser Term
expr = Sequence <$> many term

term :: Parser Term
term = do
  c <- lit
  s <- optionMaybe $ char '*' -- Easily extended for +, ?, etc.
  return $ if isNothing s
    then Literal c
    else Star $ Literal c

也许更有经验的 Haskeller 会提供更好的解决方案。

于 2012-01-26T15:44:41.750 回答