Indentation-aware parsing of expression trees

Question

As a follow-up to this question, I am now trying to parse an expression language that has variables and case ... of ... expressions. The syntax should be indentation-based:

• Expressions can span multiple lines, as long as every line is indented relative to the first one; i.e. this should be parsed as a single application:

  f x y
    z
   q
  

• Each alternative of a case expression needs to be on its own line, indented relative to the case keyword. Right-hand sides can span multiple lines.

  case E of
    C -> x
    D -> f x
     y
  

  should be parsed into a single case with two alternatives, with x and f x y as the right-hand sides

I've simplified my code into the following:

import qualified Text.Megaparsec.Lexer as L
import Text.Megaparsec hiding (space)
import Text.Megaparsec.Char hiding (space)
import Text.Megaparsec.String
import Control.Monad (void)
import Control.Applicative

data Term = Var String
          | App [Term]
          | Case Term [(String, Term)]
          deriving Show

space :: Parser ()
space = L.space (void spaceChar) empty empty

name :: Parser String
name = try $ do
    s <- some letterChar
    if s `elem` ["case", "of"]
      then fail $ unwords ["Unexpected: reserved word", show s]
      else return s

term :: Parser () -> Parser Term
term sp = App <$> atom `sepBy1` try sp
  where
    atom = choice [ caseBlock
                  , Var <$> L.lexeme sp name
                  ]

    caseBlock = L.lineFold sp $ \sp' ->
        Case <$>
        (L.symbol sp "case" *> L.lexeme sp (term sp) <* L.symbol sp' "of") <*>
        alt sp' `sepBy` try sp' <* sp

    alt sp' = L.lineFold sp' $ \sp'' ->
        (,) <$> L.lexeme sp' name <* L.symbol sp' "->" <*> term sp'' 

As you can see, I am trying to use the technique from this answer to separate alternatives with sp'aces that are more indented than the case keyword.

Problems

This seems to work for single expressions made up of application only:

λ» parseTest (L.lineFold space term) "x y\n z"
App [Var "x",Var "y",Var "z"]

It doesn't work for list of such expressions using the technique from the linked answer:

λ» parseTest (L.lineFold space $ \sp -> (term sp `sepBy` try sp)) "x\n y\nz"
3:1:
incorrect indentation (got 1, should be greater than 1)

case expressions fail out of the gate when trying to use line-folding:

λ» parseTest (L.lineFold space term) "case x of\n C -> y\n D -> z"
1:5:
Unexpected: reserved word "case"

case works without line folding for the outermost expression, for one alternative only:

λ» parseTest (term space) "case x of\n C -> y\n  z"
App [Case (App [Var "x"]) [("C",App [Var "y",Var "z"])]]

But case fails as soon as I have multiple alternatives:

λ» parseTest (term space) "case x of\n C -> y\n D -> z"
3:2:
incorrect indentation (got 2, should be greater than 2)

What am I doing wrong?

Answer 1

I'm answering since I promised to take a look at this. This problem represents a rather difficult problem for Parsec-like parsers in their current state. I probably could make it work after spending much more time that I have available, but in the slot of time I can spend answering this, I only got this far:

module Main (main) where

import Control.Applicative
import Control.Monad (void)
import Text.Megaparsec
import Text.Megaparsec.String
import qualified Data.List.NonEmpty    as NE
import qualified Text.Megaparsec.Lexer as L

data Term = Var String
          | App [Term]
          | Case Term [(String, Term)]
          deriving Show

scn :: Parser ()
scn = L.space (void spaceChar) empty empty

sc :: Parser ()
sc = L.space (void $ oneOf " \t") empty empty

name :: Parser String
name = try $ do
  s <- some letterChar
  if s `elem` ["case", "of"]
    then (unexpected . Label . NE.fromList) ("reserved word \"" ++ s ++ "\"")
    else return s

manyTerms :: Parser [Term]
manyTerms = many pTerm

pTerm :: Parser Term
pTerm = caseBlock <|> app -- parse a term first

caseBlock :: Parser Term
caseBlock = L.indentBlock scn $ do
  void (L.symbol sc "case")
  t <- Var <$> L.lexeme sc name -- not sure what sort of syntax case of
       -- case expressions should have, so simplified to vars for now
  void (L.symbol sc "of")
  return (L.IndentSome Nothing (return . Case t) alt)

alt :: Parser (String, Term)
alt = L.lineFold scn $ \sc' ->
  (,) <$> L.lexeme sc' name <* L.symbol sc' "->" <*> pTerm -- (1)

app :: Parser Term
app = L.lineFold scn $ \sc' ->
  App <$> ((Var <$> name) `sepBy1` try sc' <* scn)
  -- simplified here, with some effort should be possible to go from Var to
  -- more general Term in applications

Your original grammar is left-recursive because every term can be either a case expression or an application and if it's an application, then the first part of it again can be either case expression or application, etc. You'll need to deal with that somehow.

Here is a session:

λ> parseTest pTerm "x y\n z"
App [Var "x",Var "y",Var "z"]
λ> parseTest pTerm "x\n y\nz"
App [Var "x",Var "y"]
λ> parseTest manyTerms "x\n y\nz"
[App [Var "x",Var "y"],App [Var "z"]]
λ> parseTest pTerm "case x of\n C -> y\n D -> z"
Case (Var "x") [("C",App [Var "y"]),("D",App [Var "z"])]
λ> parseTest pTerm "case x of\n C -> y\n  z"
3:3:
incorrect indentation (got 3, should be equal to 2)

This last result is because of (1) in the code. Introducing a parameter to app makes it impossible to use it without thinking of context (it would be no longer stand-alone expression, but factored-out part of something). We can see that if you indent z with respect to start of y application, not the entire alternative, it works:

λ> parseTest pTerm "case x of\n C -> y\n           z"
Case (Var "x") [("C",App [Var "y",Var "z"])]

Finally, case expression works:

λ> parseTest pTerm "case x of\n C -> y\n D -> z"
Case (Var "x") [("C",App [Var "y"]),("D",App [Var "z"])]

My advice here would be to take a look at some pre-processor and use Megaparsec on top of that. The tools in Text.Megaparsec.Lexer are not that easy to apply in this case, but they are the best we could come up with and they work fine for simple indentation-sensitive grammars.