Использование Parsec для разбора регулярных выражений

Question

Я пытаюсь изучить 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 является то, что он потребляет свой обязательный токен в конце.

Какие-нибудь мысли?

Answer 1

Вы должны использовать 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?"

Answer 2

Ваша грамматика является леворекурсивной, что не очень хорошо tryПарсек будет неоднократно возвращаться. Есть несколько способов обойти это. Наверное, самое простое - это просто * необязательно в другом правиле:

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

Возможно, более опытный Хаскеллер найдет лучшее решение.