4

複数のパーサーが成功できる入力を解析する最良の方法を知りたいです。私は最初に失敗した試みと、より慣用的なものにできることを願っているエレガントでない解決策の概要を説明しました。

たとえば、次の文の「the」、「quick」、「fox」を独自のデータコンストラクターに入れたいと思います。

"the quick brown fox jumps over the lazy dog".

したがって、次の型構築子が与えられます。

data InterestingWord = Quick | The | Fox deriving Show
data Snippet = Word InterestingWord | Rest String deriving Show

解析の出力を次のようにしたいと思います。

[Word The,
 Rest " ", Word Quick,
 Rest " brown ", Word Fox,
 Rest " jumped over ", Word The,
 Rest " lazy dog"]

2つの解決策は次のとおりです。

import Text.Parsec
import Data.Maybe
import Data.Ord    
import Data.List

data InterestingWord = Quick | The | Fox deriving Show
data Snippet = Word InterestingWord | Rest String deriving Show

testCase = "the quick brown fox jumped over the lazy dog"
-- Expected output:
-- [Word The,
--  Rest " ", Word Quick,
--  Rest " brown ", Word Fox,
--  Rest " jumped over ", Word The,
--  Rest " lazy dog"]

toString Quick = "quick"
toString The = "the"
toString Fox = "fox"

-- First attempt

-- Return characters upto the intended word along
-- with the word itself
upto word = do
  pre <- manyTill anyChar $ lookAhead $ string (toString word)
  word' <- try $ string (toString word)
  return [Rest pre, Word word]

-- Parsers for the interesting words
parsers = [upto Quick,
           upto The, 
           upto Fox]

-- Try each parser and return its results with the 
-- rest of the input.
-- An incorrect result is produced because "choice"
-- picks the first successful parse result.
wordParser = do
  snippets <- many $ try $ choice parsers
  leftOver <- many anyChar
  return $ concat $ snippets ++ [[Rest leftOver]]

-- [Rest "the ",Word Quick,Rest " brown fox jumped over the lazy dog"]        
test1 = parseTest wordParser testCase

-- Correct

-- In addition to the characters leading upto the 
-- word and the word, the position is also returned
upto' word = do
  result <- upto word
  pos <- getPosition
  return (pos, result)

-- The new parsers         
parsers' = [upto' Quick,
            upto' The, 
            upto' Fox]

-- Try each of the given parsers and 
-- possibly returning the results and
-- the parser but don't consume
-- input.
tryAll = mapM (\p -> do
                 r <- optionMaybe $ try (lookAhead p)
                 case r of
                   Just result -> return $ Just (p, result)
                   Nothing -> return $ Nothing
              )

-- Pick the parser that has consumed the least.             
firstSuccess ps = do
  successes <- tryAll ps >>= return . catMaybes
  if not (null successes) then
      return $ Just (fst $ head (sortBy (comparing (\(_,(pos,_)) -> pos)) successes))
  else return $ Nothing

-- Return the parse results for the parser that 
-- has consumed the least
wordParser' = do
  parser <- firstSuccess parsers'
  case parser of
    Just p -> do
      (_,snippet) <- p
      return snippet
    Nothing -> parserZero

-- Returns the right result
test2 = parseTest (many wordParser' >>= return . concat) testCase

「choice」は、私が本当に必要としているのが最小の文字を消費しながら成功する最初のパーサーである場合に成功する最初のパーサーを返すため、最初の試行「test1」は目的の出力を生成しません。これは、入力が解析された後のソース位置を保持し、ソース位置が最も低いパーサーを使用して次に試みることです。

このケースは十分に一般的であるように思われるので、明らかなコンビネータの呪文が欠けているように感じます。誰かがより良い提案を提供できますか？

ありがとう！

-ディーチ

4

2 に答える 2

1

これは特に一般的なニーズではありませんが、実装は次のとおりです。

import Control.Monad
import "parsec3" Text.Parsec
import Data.Maybe
import Data.List
import Data.Ord

longestParse :: [Parsec String () a] -> Parsec String () a
longestParse parsers = do
  allParses <- sequence [lookAhead $ optionMaybe $ try $ 
    liftM2 (,) parse getPosition | parse <- parsers]
  -- allParses :: [Maybe (a, SourcePos)]
  (bestParse, bestPos) <- case catMaybes allParses of
    [] -> fail "No valid parse" -- maybe we can do something better?
    successfulParses -> return $ minimumBy (comparing snd) successfulParses
  setPosition bestPos
  return bestParse
于 2012-02-10T18:42:40.420 に答える
0

私が理解しているように、あなたは最初に見た興味深い単語まで繰り返し解析したいと思っています。現在、あなたはそれぞれの興味深い単語を解析し、見つけたどの興味深い単語がより近いかを確認しています。

私の提案は、あなたが現在興味深い単語にいるかどうかをチェックするパーサーを定義することです（選択肢の1つだけが成功できるので、単純な選択よりも凝ったことをする必要はありません）。次に、最初のパーサーが成功するまで先に進みます。これは、興味深い単語に遭遇したときに発生します。これにより、最初の興味深い単語が得られます。これは、興味深い単語が含まれる前は何も知らないためです。

はい、これはどのパーサーの一致が最短であるかを判断するという質問には答えません。これは、どのパーサーの一致が最短であるかを気にしない実際の問題の解決策を提供することによって、その質問を回避します。

于 2012-02-10T21:33:27.983 に答える