Каскадные парсеры в Haskell - PullRequest
Новая
       23

Каскадные парсеры в Haskell

4 голосов
/ 15 февраля 2020

Мой тип синтаксического анализатора 

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

У меня есть два синтаксических анализатора:

1) a = (satisfy isAlpha), который знает, как сопоставить первый буквенный символ c в строке.

Запуск parse a "k345" дает Just ('k',"345")

2) b = many (satisfy isDigit), который знает, как сопоставить любое количество цифр. Выполнение parse b "1234 abc" дает Just ("1234"," abc")

Теперь я хочу объединить эти два парсера и сопоставить одиночный символ alphanumeri c, за которым следует любое количество цифр.

Я пытался:

parse (a *> b) "k1234 7" и получил Just ("1234"," 7 "). Похоже, что 'k', соответствующий первому парсеру, a пропал с выхода. Как мне решить эту проблему?

Спасибо!

Ответы [ 2 ]

3 голосов
/ 15 февраля 2020

Для парсера игрушек посмотрите следующий код: 

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
module Parse where

import Data.Char
import Data.List

newtype Parser a = Parser 
  { parse :: String -> Maybe (a, String) }

satisfy :: (Char -> Bool) -> Parser Char
satisfy cond = Parser $ \s ->
   case s of 
     "" -> Nothing 
     (c:cs) -> if cond c then Just (c, cs) else Nothing

many :: Parser a -> Parser [a]
many p = Parser $ \s -> 
  case parse p s of 
    Nothing -> Just ([], s)
    Just (c, cs) -> let Just (cc, cs') = parse (many p) cs
                     in Just (c:cc, cs')

string :: String -> Parser String 
string str = Parser $ \s -> if isPrefixOf str s 
                               then Just (str, drop (length str) s)
                               else Nothing

instance Functor Parser where 
  fmap f (Parser g) = Parser $ \s -> 
    case g s of
      Nothing -> Nothing
      Just (r, remain) -> Just (f r, remain)

instance Applicative Parser where
  pure a = Parser $ \s -> Just (a, s)
  -- (<*>) :: f (a -> b) -> f a -> f b
  (Parser f) <*> (Parser g) = Parser $ \s -> 
    case f s of
      Nothing -> Nothing
      Just (ab, remain) -> case g remain of
                            Nothing -> Nothing
                            Just (r, remain1) -> Just (ab r, remain1)

instance Semigroup a => Semigroup (Parser a) where 
  (Parser p1) <> (Parser p2) = Parser $ \s -> 
    case p1 s of 
      Nothing -> Nothing 
      Just (r1, s1) -> case p2 s1 of 
                         Nothing -> Nothing 
                         Just (r2, s2) -> Just (r1 <> r2, s2)

instance (Monoid a, Semigroup (Parser a))=> Monoid (Parser a) where
  mempty = Parser $ \s -> Just (mempty, s)
  mappend = (<>)

a = satisfy isAlpha
b = many (satisfy isDigit)

λ> parse a "k345"
Just ('k',"345")
λ> parse b "12345 abc"
Just ("12345"," abc")
λ> parse (a *> b) "k1234 7"
Just ("1234"," 7")
λ> parse (string "k" <> b) "k1234 7"
Just ("k1234"," 7")

Так что, возможно, вам следует найти несколько уроков и попытаться ознакомиться с Functor, Applicative и Monad , Видите, вы можете реализовать экземпляр Monoid для вашего типа Parser, а затем вы можете использовать (<>) для объединения ваших проанализированных результатов.

3 голосов
/ 15 февраля 2020

Похоже, это работает нормально: 

parse  (fmap  (:)  (satisfy isAlpha)  <*>  many (satisfy isDigit))   "k1234 7"

И возвращает то, что хотел 

Just ("k1234"," 7")
...