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)

もちろん、最終的にデータ型でラップすることになるでしょう。それにはさまざまな方法があります。これが私の頭の上からの1つです：

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 に答える