删除基本表达式解析器中的左递归

Question

作为练习，我正在使用以下 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

Answer 1

假设您要解析涉及文字、加法和乘法的非括号表达式。您可以通过按优先级减少列表来做到这一点。这是 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)

删除基本表达式解析器中的左递归

Removing Left Recursion in a Basic Expression Parser

parsing

haskell

left-recursion