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 回答