在基本表达式解析器中删除左递归
作为练习，我正在使用以下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))
由于表达式语法的左递归性质，当我尝试使用expr解析器解析1+1这样的简单内容时，解析器会陷入无限循环。
我已经看到了如何使用类似于以下内容的转换来分解网络中的左递归的示例：
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
假设你想解析包含文字，加法和乘法的非括号表达式。 您可以通过按优先顺序削减列表来完成此操作。 这里有一种方法可以在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)