Designing a Loose Grammar Parser with Monads in Scala

Question

I need help developing a non-strict grammar parser with monads. The structure of the grammar is as follows:

• heading
• section1
• section2
• ...

Each of these sections may be missing, and the thread may terminate anywhere, so I need to return what I have analyzed so far.

I managed to use the state monad to structure my parser in a function like s => (a, s) for each section. State s contains the rest of the input and data currently captured. In Scala-like pseudo-code:

val parser = for {
  _ <- readHeader
  _ <- readSection1
  _ <- readSection2
  - <- ...
} yield ()

parser(input)

, EOF. , EOF , .

:

import scalaz._
import Scalaz._

object Playground extends App {
  type Stream = String
  type Mined = List[String]
  type ParserState = (Stream, Mined)

  type MyEither[+T] = Either[ParserState, T]

  val s1 = StateT[MyEither, ParserState, Unit] { s =>
    Right((("input at s1", add(s, "header")), ()))
  }
  val s2 = StateT[MyEither, ParserState, Unit] { s =>
    Right((("input at s2", add(s, "section1")), ()))
  }
  val s3 = StateT[MyEither, ParserState, Unit] { s =>
    Left(s)
  }
  val s4 = StateT[MyEither, ParserState, Unit] { s =>
    Right((("input at s4", add(s, "section3")), ()))
  }

  def add(s: ParserState, mined: String): Mined = mined :: s._2

  val parser =
    for {
      _ <- s1
      _ <- s2
      _ <- s3
      _ <- s4
    } yield ()
  println(parser.run(("input", List())))
}

Left((input at s2,List(section1, header)))

? , ?