Парсек разбора и разделения различных структур - PullRequest
Новая
       40

Парсек разбора и разделения различных структур

2 голосов
/ 06 января 2012

Допустим, у меня есть разные парсеры p<sub>1</sub>, ..., p<sub>k</sub>.Я хочу определить функцию p<sub>k</sub> :: Parser ([t<sub>1</sub>], ..., [t<sub>k</sub>]), где p<sub>i</sub> :: Parser t<sub>i</sub>.

, которая будет анализировать набор строк (одна за другой), которые соответствуют любому из p 1 ... p k и разделите их в соответствующих списках.Предположим для простоты, что ни одна из строк не совпадает с двумя парсерами.

Мне удалось это сделать, но я действительно изо всех сил пытаюсь найти элегантный способ (предпочтительно используя много или любой другой встроенный парсер parsec).

Ответы [ 3 ]

5 голосов
/ 06 января 2012

Первый шаг - превратить каждый из ваших парсеров в парсер большого типа: 

p1 :: Parser t1
p2 :: Parser t2
p3 :: Parser t3
p1 = undefined
p2 = undefined
p3 = undefined

p1', p2', p3' :: Parser ([t1], [t2], [t3])
p1' = fmap (\x -> ([x], [], [])) p1
p2' = fmap (\x -> ([], [x], [])) p2
p3' = fmap (\x -> ([], [], [x])) p3

Теперь мы неоднократно выбираем из этих последних парсеров и объединяем результаты в конце: 

parser :: Parser ([t1], [t2], [t3])
parser = fmap mconcat . many . choice $ [p1', p2', p3']

Есть Monoid экземпляров для кортежей до пятого размера;кроме того, вы можете использовать вложенные кортежи или более подходящую структуру данных.

5 голосов
/ 06 января 2012

К сожалению, вы не можете сделать это вообще без хитрости на уровне типов.Тем не менее, подход в соответствии с предложением Даниэля Вагнера может быть построен в стиле DIY, используя полиморфные комбинаторы и некоторые ранее существовавшие рекурсивные примеры.Я приведу простой пример для демонстрации.

Сначала несколько простых анализаторов для тестирования: 

type Parser = Parsec String ()

parseNumber :: Parser Int
parseNumber = read <$> many1 digit

parseBool :: Parser Bool
parseBool = string "yes" *> return True
        <|> string "no" *> return False

parseName :: Parser String
parseName = many1 letter

Затем мы создадим тип "base case", чтобы отметить конецвозможности, и дать ему синтаксический анализатор, который всегда завершается успешно без ввода. 

data Nil = Nil deriving (Eq, Ord, Read, Show, Enum, Bounded)
instance Monoid Nil where 
    mempty = Nil
    mappend _ _ = Nil

parseNil :: Parser Nil
parseNil = return Nil

Это, конечно, эквивалентно () - я создаю только новый тип для устранения неоднозначности в случае, если мы действительно хотимразобрать ().Затем комбинатор, который объединяет синтаксические анализаторы: 

infixr 3 ?|>
(?|>) :: (Monoid b) => Parser a -> Parser b -> Parser ([a], b)
p1 ?|> p2 = ((,) <$> ((:[]) <$> p1) <*> pure mempty)
        <|> ((,) <$> pure [] <*> p2)

Здесь происходит то, что p1 ?|> p2 пытается p1, и, если это удастся, переносит его в список синглтона и заполняет mempty дляВторой элемент кортежа.Если p1 терпит неудачу, если заполняет пустой список и использует p2 для второго элемента. 

parseOne :: Parser ([Int], ([Bool], ([String], Nil)))
parseOne = parseNumber ?|> parseBool ?|> parseName ?|> parseNil

Комбинирование синтаксических анализаторов с новым комбинатором является простым, а тип результата довольно понятен.

parseMulti :: Parser ([Int], ([Bool], ([String], Nil)))
parseMulti = mconcat <$> many1 (parseOne <* newline)

Мы полагаемся на рекурсивный экземпляр Monoid для кортежей и обычный экземпляр для списков для объединения нескольких строк.Теперь, чтобы показать, что это работает, определите быстрый тест: 

runTest = parseTest parseMulti testInput

testInput = unlines [ "yes", "123", "acdf", "8", "no", "qq" ]

, который успешно разбирается как Right ([123,8],([True,False],(["acdf","qq"],Nil))).

5 голосов
/ 06 января 2012

Представление синтаксических анализаторов в виде списка облегчает это. Использование: 

choice :: [Parser a] -> Parser a
many :: Parser a -> Parser [a]

Мы можем написать: 

combineParsers :: [Parser a] -> Parser [a]
combineParsers = many . choice

Это не совсем правильно, так как объединяет их все в один список. Давайте свяжем каждый парсер с уникальным идентификатором: 

combineParsers' :: [(k, Parser a)] -> Parser [(k, a)]
combineParsers' = many . choice . combine
  where combine = map (\(k,p) -> (,) k <$> p)

Затем мы можем преобразовать это обратно в форму списка: 

combineParsers :: [Parser a] -> Parser [[a]]
combineParsers ps = map snd . sortBy fst <$> combineParsers' (zip [0..] ps)

Возможно, вы могли бы сделать это более эффективным, написав вместо этого combineParsers' :: [(k, Parser a)] -> Parser (Map k [a]), используя, например, combine = map $ \(k,p) -> fmap (\a -> Map.insertWith (++) k [a]) p.

Для этого требуется, чтобы все анализаторы имели одинаковый тип результата, поэтому вам нужно будет обернуть каждый их результат в тип данных с Cons <$> p для каждого p . Затем вы можете развернуть конструктор из каждого списка. Следует признать, что это довольно уродливо, но чтобы сделать это неоднородно с кортежами, потребуются еще более уродливые хаки класса типов.

Возможно, для вашего конкретного варианта использования может быть более простое решение, но это самый простой способ сделать это в общем случае, о котором я могу подумать.

...