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

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

8 голосов
/ 26 января 2012

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

Есть мысли?

Ответы [ 2 ]

12 голосов
/ 27 января 2012

Вы должны использовать 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?"
6 голосов
/ 26 января 2012

Ваша грамматика является леворекурсивной, что не очень хорошо с 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

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

...