単一の入力で複数の正しいパーサーを選択する

Question

複数のパーサーが成功する入力を解析する最適な方法を知りたいと思います。私は最初に失敗した試みと、より熟達したものになることを願う控えめな解決策を概説しました。

たとえば私はlexのしたい「」、「速い」と、独自のデータ構築に次の文章から「キツネ」：

"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 

「選択肢は」私が本当にしたいことは、少なくとも文字を消費しながら成功した最初のパーサであるとき、成功した最初のパーサを返すため、所望の出力を生成しません「TEST1」の最初の試み。これは、入力が一度解析され、最も低いソース位置のパーサーを使用すると、ソースの位置を保持することによって次に試みます。

このケースは、私がいくつかの明白なコンビネータの呪文を紛失していると感じるほど一般的です。誰もより良い提案を提供できますか？

ありがとうございます！

-deech

Answer 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 

Answer 2

、あなたは何度見て最初に興味深い単語までを解析します。現時点では、それぞれの興味深い単語を解析して、あなたが見つけた興味深い単語が近いかどうかを確認しています。

私が提案するのは、現在興味深い単語があるかどうかを確認するパーサを定義することです（選択肢の1つだけが成功するため、単純な選択肢よりも魅力的なことをする必要はありません）。その後、最初のパーサーが成功するまで前進します。これは、あなたが興味深い言葉に遭遇したときに起こります。これは興味深い単語を含む前に何も知らないので、最初の興味深い単語を与えます。

はい、これは、どのパーサーが最も短いかを判断する質問には答えません。これは、どのパーサーのマッチが最短かを気にしないあなたの実際の問題を解決することによって、その質問を回避します。