7

演習として、次の GADT を使用して、Haskell で定義された非常に単純な言語のパーサーを実装しています (私のプロジェクトの実際の文法にはさらに多くの式が含まれますが、この抜粋は質問に対して十分です)。

data Expr a where
    I   :: Int -> Expr Int
    Add :: [Expr Int] -> Expr Int

解析関数は次のとおりです。

expr :: Parser (Expr Int)
expr = foldl1 mplus
    [ lit 
    , add 
    ]   

lit :: Parser (Expr Int)
lit = I . read <$> some digit

add :: Parser (Expr Int)
add = do
  i0 <- expr
  is (== '+')
  i1 <- expr
  is <- many (is (== '+') *> expr)
  pure (Add (i0:i1:is))

式文法の左再帰の性質により、パーサーを1+1使用するような単純なものを解析しようとするexprと、パーサーが無限ループに陥ります。

次のような変換を使用して、ウェブ全体で左再帰を因数分解する方法の例を見てきました。

S -> S a | b

次のようなものに：

S -> b T
T -> a T

しかし、これをパーサーに適用する方法に苦労しています。

完全を期すために、パーサーを実際に実装するコードを次に示します。

newtype Parser a = Parser
    { runParser :: String -> [(a, String)]
    }   

instance Functor Parser where
    fmap f (Parser p) = Parser $ \s ->
      fmap (\(a, r) -> (f a, r)) (p s)

instance Applicative Parser where
    pure a = Parser $ \s -> [(a, s)] 
    (<*>) (Parser f) (Parser p) = Parser $ \s ->
      concat $ fmap (\(f', r) -> fmap (\(a, r') -> (f' a, r')) (p r)) (f >

instance Alternative Parser where
    empty = Parser $ \s -> []
    (<|>) (Parser a) (Parser b) = Parser $ \s ->
      case a s of
        (r:rs) -> (r:rs)
        []     -> case b s of
                    (r:rs) -> (r:rs)
                    []     -> []

instance Monad Parser where
    return = pure
    (>>=) (Parser a) f = Parser $ \s ->
      concat $ fmap (\(r, rs) -> runParser (f r) rs) (a s)

instance MonadPlus Parser where
    mzero = empty
    mplus (Parser a) (Parser b) = Parser $ \s -> a s ++ b s 

char  = Parser $ \case (c:cs) -> [(c, cs)]; [] -> []
is p  = char >>= \c -> if p c then pure c else empty
digit = is isDigit
4

1 に答える 1

3

リテラル、加算、および乗算を含む、括弧で囲まれていない式を解析したいとします。これを行うには、優先順位に従ってリストを削減します。attoparsecこれは、パーサーで行う方法とかなり似ているはずです。私は解析の専門家ではないので、エラーや不適切な点があるかもしれません。

import Data.Attoparsec.ByteString.Char8
import Control.Applicative

expr :: Parser (Expr Int)
expr = choice [add, mul, lit] <* skipSpace
-- choice is in Data.Attoparsec.Combinators, but is
-- actually a general Alternative operator.

add :: Parser (Expr Int)
add = Add <$> addList

addList :: Parser [Expr Int]
addList = (:) <$> addend <* skipSpace <* char '+' <*> (addList <|> ((:[]) <$> addend))

addend :: Parser (Expr Int)
addend = mul <|> multiplicand

mul :: Parser (Expr Int)
mul = Mul <$> mulList

mulList :: Parser [Expr Int]
mulList = (:) <$> multiplicand <* skipSpace <* char '*' <*> (mulList <|> ((:[]) <$> multiplicand))

multiplicand :: Parser (Expr Int)
multiplicand = lit

lit :: Parser (Expr Int)
lit = I <$> (skipSpace *> decimal)
于 2015-09-19T03:25:19.550 に答える