3
\$\begingroup\$

I've been developing a compiler for a programming language I'm working on in Scala, and after having used Haskell's Parsec a lot for this sort of thing in the past I decided to reimplement the library in Scala (which can be found here). I'm pretty happy with the result, and it definitely works but I'd like to get a review primarily on;

  1. How to improve the quality of the Scala code itself
  2. Ways to improve the performance of the parsers themselves

In this review I'll only target the core code for the project, and not the additional combinators that are defined such as Tokeniser classes and the convenience combinators, I'll save those for a separate review.

At the end of the code I'll provide some example parsers that can be used to play with the implementation and to illustrate how it is used.

We'll start with the package object, then get into the implementation itself.

package parsec
import scala.annotation.tailrec
import parsec._
import parsec.Parsec._
import parsec.ParseError._

// This is really package object parsec, but since I removed the parent package, this was the simplest way to get it working for the review!
object `package`
{
    type Parser[A] = Parsec[Stream[String, Char], Unit, A]
    type Result[S <: Stream[_, _], U] = Bounce[Consumed[Reply[S, U, _]]]

    // This method feeds a Parsec object its terminal functions in the continuation
    // Which returns the final result of executing a parser on some input
    final def runParsec[S <: Stream[_, _], U, A](p: Parsec[S, U, A], s: State[S, U]): Consumed[Reply[S, U, A]] =
    {
        val cok: A => State[S, U] => ParseError => Result[S, U] = a => s => err => Chunk(ConsumedA(Ok(a, s, err)))
        val cerr: ParseError => Result[S, U] = err => Chunk(ConsumedA(Error(err)))
        val eok: A => State[S, U] => ParseError => Result[S, U] = a => s => err => Chunk(Empty(Ok(a, s, err)))
        val eerr: ParseError => Result[S, U] = err => Chunk(Empty(Error(err)))
        // the result of p.unparser is guaranteed to be a Consumed[Reply[S, U, A]], but the compiler complains, hence the asInstanceOf
        return p.unParser(s)(cok)(cerr)(eok)(eerr).run.asInstanceOf[Consumed[Reply[S, U, A]]]
    }

    // This is the method one uses in order to run a parser, it serves as a wrapper around runParsec
    final def runParser[S <: Stream[_, _], U, A](p: Parsec[S, U, A], u: U, name: String, s: S, line: Int = 1, column: Int = 1): Either[ParseError, A] =
    {
        try
        {
            val res = runParsec(p, State(s, SourcePos(name, line, column), u)) match
            {
                case ConsumedA(r) => r
                case Empty(r) => r 
            }
            res match
            {
                case Ok(x, _, _) => Right(x)
                case Error(err) => Left(err)
            }
        }
        catch
        {
            // It used to be the case that the parsers could stack overflow the JVM
            // as far as I can tell that is no longer the case, thanks to Bounce
            case e: StackOverflowError => { System.err.println(s"""Exceeded maximum stack depth whilst attempting to parse; 
                                                                  |\t$s
                                                                  |Try increasing the stack depth for the JVM on the command line with "-Xss0000k" (KB) or "-Xss00m" (MB)
                                                                  |replacing 0000 with the desired size in KB (recommended 16MB, but if that isn't enough feel free to increase it!)""".stripMargin);
                                            return Left(unknownError(State(s, SourcePos(name, line, column), u)))}
        }
    }

    // Bounce, Chunk and Thunk are very important;
    // It allows us to make the execution of the parser continuations
    // be tail recursive, even though Scala doesn't allow sibling call
    // optimisation. The runParsec method creates Chunks which are the
    // final part of a Bounce chain, and the primitive combinators create
    // Thunks, which has the effect of trading stack space for heap!
    // Correct me if I'm wrong, but I believe the heap consumed for the
    // Bounce objects is O(1)? The next Thunk isn't created until the
    // previous is executed?
    sealed trait Bounce[A]
    {
        @tailrec
        final def run: A = this match
        {
            case Thunk(f) => f().run
            case Chunk(x) => x
        }
    }
    case class Thunk[A](f: () => Bounce[A]) extends Bounce[A]
    case class Chunk[A](result: A) extends Bounce[A]

    protected sealed trait Consumed[A]
    protected case class ConsumedA[A](a: A) extends Consumed[A]
    protected case class Empty[A](a: A) extends Consumed[A]
    protected sealed trait Reply[S <: Stream[_, _], U, A]
    protected case class Ok[S <: Stream[_, _], U, A](a: A, s: State[S, U], err: ParseError) extends Reply[S, U, A]
    protected case class Error[S <: Stream[_, _], U, A](err: ParseError) extends Reply[S, U, A]

    final case class State[S <: Stream[_, _], U](stateInput: S, statePos: SourcePos, stateUser: U)
    final object State
    {
        final def getPosition[S <: Stream[_, _], U]: Parsec[S, U, SourcePos] = for (state <- getParserState[S, U]) yield statePos(state)
        final def getInput[S <: Stream[_, _], U]: Parsec[S, U, S] = for (state <- getParserState[S, U]) yield stateInput(state)
        final def setPosition[S <: Stream[_, _], U](pos: SourcePos): Parsec[S, U, Unit] = updateParserState[S, U]{case State(input, _, user) => State(input, pos, user)}
        final def setInput[S <: Stream[_, _], U](input: S): Parsec[S, U, Unit] = updateParserState[S, U]{case State(_, pos, user) => State(input, pos, user)}

        final def getParserState[S <: Stream[_, _], U]: Parsec[S, U, State[S, U]] = updateParserState(x=>x)
        final def setParserState[S <: Stream[_, _], U](st: State[S, U]): Parsec[S, U, State[S, U]] = updateParserState(_=>st)
        final def updateParserState[S <: Stream[_, _], U](f: State[S, U] => State[S, U]) = 
        {
            new Parsec[S, U, State[S, U]](s => _ => _ => eok => _ =>
            {
                val s_ = f(s)
                Thunk(() => eok(s_)(s_)(newErrorUnknown(s_.statePos)))
            })
        }

        final def getState[S <: Stream[_, _], U] = getParserState[S, U] <#> stateUser
        final def putState[S <: Stream[_, _], U](u: U) =
        {
            new Parsec[S, U, Unit](s => _ => _ => eok => _ =>
            {
                val s_ = State(s.stateInput, s.statePos, u)
                Thunk(() => eok(())(s_)(newErrorUnknown(s_.statePos)))
            })
        }
        final def modifyState[S <: Stream[_, _], U](f: U => U) =
        {
            new Parsec[S, U, Unit](s => _ => _ => eok => _ =>
            {
                val s_ = State(s.stateInput, s.statePos, f(s.stateUser))
                Thunk(() => eok(())(s_)(newErrorUnknown(s_.statePos)))
            })
        }

        // Here we provide Haskell style accessors, which aren't really necessary
        final def stateInput[S <: Stream[_, _], U](s: State[S, U]): S = s.stateInput
        final def statePos[S <: Stream[_, _], U](s: State[S, U]): SourcePos = s.statePos
        final def stateUser[S <: Stream[_, _], U](s: State[S, U]): U = s.stateUser
    }

    // The Stream class is how the parsers accept their input
    // We use implicit classes to allow the user to simply pass
    // acceptable input mediums into parsers without needing to
    // even think about the underlying Streams.
    sealed trait Stream[S, X]
    {
        def uncons(): Option[(X, Stream[S, X])]
    }

    implicit class StringStream(s: String) extends Stream[String, Char]
    {
        def uncons(): Option[(Char, Stream[String, Char])] = 
        {
            if (s.isEmpty()) None
            else Some(s.head, s.tail)
        }
        override def toString = s
    }

    implicit class ListStream[X](xs: List[X]) extends Stream[List[X], X]
    {
        def uncons(): Option[(X, Stream[List[X], X])] = xs match
        {
            case List() => None
            case x::xs => Some(x, xs)
        }
        override def toString = xs.toString
    }

    implicit class SeqStream[X](xs: Seq[X]) extends Stream[Seq[X], X]
    {
        def uncons(): Option[(X, Stream[Seq[X], X])] = xs match
        {
            case Seq() => None
            case x::xs => Some(x, xs)
        }
        override def toString = xs.toString
    }

    implicit class StreamStream[X](xs: scala.Stream[X]) extends Stream[scala.Stream[X], X]
    {
        def uncons(): Option[(X, Stream[scala.Stream[X], X])] = xs match
        {
            case scala.Stream() => None
            case x#::xs => Some(x, xs)
        }
    }

    // This allows us to use () as a parser that does nothing, purely to
    // remove the need to write pure[S, U, Unit](()) all over the place
    implicit def asParser[S <: Stream[_, _], U](u: Unit): Parsec[S, U, Unit] = pure[S, U, Unit](())
    // This allows us to always ignore the result of a parser if necessary
    implicit def asUnitParser[S <: Stream[_, _], U, A](p: Parsec[S, U, A]): Parsec[S, U, Unit] = p.unit()
}

Now onto the main implementation (we'll cover Message, ParseError and Pos afterwards);

package parsec

import annotation.tailrec
import parsec._
import Parsec._
import ParseError._

// Most of the time, we use call by name and then laziness to emulate Haskell
// This ensures that the parsers done get caught in infinite loops trying to construct
// It's likely a lot of them can be removed but it's a little tricky
// At it's heart, a parser is a function, that, given 4 continuation functions
// will perform some action and then execute the correct continuation
// or pass on modified versions of them. The 4 continuations are (in order);
// Consumed Input and Didn't Fail
// Consumed Input and Failed
// Didn't Consume and Didn't Fail
// Didn't Consume and Failed
final class Parsec[S <: Stream[_, _], U, A](unParser_ : =>State[S, U] => 
                                                        (A => State[S, U] => ParseError => Result[S, U]) =>
                                                        (ParseError => Result[S, U]) =>
                                                        (A => State[S, U] => ParseError => Result[S, U]) =>
                                                        (ParseError => Result[S, U]) => Result[S, U])
{
    lazy val unParser = unParser_
    // Monadic operation for parsers; We execute the first parser, and feed it's result into a function that produces us the next parser to execute.
    // (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    @inline
    final def flatMap[B](f: =>A => Parsec[S, U, B]): Parsec[S, U, B] = 
    {
        new Parsec[S, U, B](s => cok => cerr => eok => eerr => 
        {
            val mcok: (A => State[S, U] => ParseError => Result[S, U]) = x => s_ => err => 
            {
                Thunk(() => f(x).unParser(s_)(cok)(cerr)(x => s_ => err_ => cok(x)(s_)(err ++ err_))(err_ => cerr(err ++ err_)))
            }
            val meok: (A => State[S, U] => ParseError => Result[S, U]) = x => s_ => err =>
            {
                Thunk(() => f(x).unParser(s_)(cok)(cerr)(x => s_ => err_ => eok(x)(s_)(err ++ err_))(err_ => eerr(err ++ err_)))
            }
            Thunk(() => unParser(s)(mcok)(cerr)(meok)(eerr))
        })
    }
    @inline
    final def >>=[B](f: =>A => Parsec[S, U, B]): Parsec[S, U, B] = flatMap(f)
    @inline
    final def >>[B](mb: =>Parsec[S, U, B]): Parsec[S, U, B] = this >>= (_ => mb)
    // This one is the applicative operator for parsers
    // (<*>) :: Parser (a -> b) -> Parser a -> Parser b
    // First we run the parser ff, which gives us a function we can map
    // onto `this`, also passing on the remaining unconsumed input to it.
    // This provides us with a new parser.
    // This is equivalent, but more optimal than; for (f <- ff, x <- this) yield f(x)
    @inline
    final def <*>:[B](ff: =>Parsec[S, U, A => B]): Parsec[S, U, B] =
    {
        new Parsec[S, U, B](s => cok => cerr => eok => eerr => 
        {
            val mcok: ((A => B) => State[S, U] => ParseError => Result[S, U]) = f => s_ => err => 
            {
                Thunk(() => unParser(s_)(cok compose f)(cerr)(x => s_ => err_ => cok(f(x))(s_)(err ++ err_))(err_ => cerr(err ++ err_)))
            }
            val meok: ((A => B) => State[S, U] => ParseError => Result[S, U]) = f => s_ => err =>
            {
                Thunk(() => unParser(s_)(cok compose f)(cerr)(x => s_ => err_ => eok(f(x))(s_)(err ++ err_))(err_ => eerr(err ++ err_)))
            }
            Thunk(() => ff.unParser(s)(mcok)(cerr)(meok)(eerr))
        })
    }
    @inline
    final def <*[B](mb: =>Parsec[S, U, B]): Parsec[S, U, A] = for (x <- this; _ <- mb) yield x
    @inline
    final def *>[B](mb: =>Parsec[S, U, B]): Parsec[S, U, B] = this >> mb
    @inline
    final def map[B](f: =>A => B): Parsec[S, U, B] = new Parsec[S, U, B](s => cok => cerr => eok => eerr => Thunk(() => unParser(s)(cok compose f)(cerr)(eok compose f)(eerr)))
    @inline
    final def unit(): Parsec[S, U, Unit] = new Parsec[S, U, Unit](s => cok => cerr => eok => eerr => Thunk(() => unParser(s)(_ => cok(()))(cerr)(_ => eok(()))(eerr)))
    @inline
    final def <#>[B](f: =>A => B): Parsec[S, U, B] = map(f)
    @inline
    final def <#>:[B](f: =>A => B): Parsec[S, U, B] = map(f)
    @inline
    final def #>[B](b: =>B): Parsec[S, U, B] = map(_ => b)
    // This combinator is choice, either we run `this` and it succeeds
    // or it fails (without consuming input) and we attempt to run parser      
    // `n` instead. If `this` consumed input but failed, then this combinator fails
    @inline
    final def <|>(n: =>Parsec[S, U, A]): Parsec[S, U, A] = 
    {
        new Parsec[S, U, A](s => cok => cerr => eok => eerr =>
        {
            val meerr: ParseError => Result[S, U] = err =>
            {
                val neok: A => State[S, U] => ParseError => Result[S, U] = y => s_ => err_ => eok(y)(s_)(err ++ err_)
                val neerr: ParseError => Result[S, U] = err_ => eerr(err ++ err_)
                Thunk(() => n.unParser(s)(cok)(cerr)(neok)(neerr))
            }
            Thunk(() => unParser(s)(cok)(cerr)(eok)(meerr))
        })
    }
    // This sets the error message for a parser to not be the one generated
    // by default, allowing us to be more descriptive
    final def ?(msg: =>String): Parsec[S, U, A] = 
    {
        val msgs = List(msg)
        @inline
        def setExpectErrors(err: ParseError, msgs: List[String]) = msgs match 
        {
            case List() => err.setErrorMessage(Expect(""))
            case msg :: List() => err.setErrorMessage(Expect(msg))
            case msg :: msgs => msgs.foldLeft(err.setErrorMessage(Expect(msg)))((err_, msg_) => err_ + Expect(msg_))
        }
        new Parsec[S, U, A](s => cok => cerr => eok => eerr =>
        {
            lazy val eok_ : A => State[S, U] => ParseError => Result[S, U] = x => s_ => error => eok(x)(s_)(if (error.errorIsUnknown) error else setExpectErrors(error, msgs))
            lazy val eerr_ : ParseError => Result[S, U] = err => eerr(setExpectErrors(err, msgs))
            Thunk(() => unParser(s)(cok)(cerr)(eok_)(eerr_))
        })
    }
}

final object Parsec
{
    @inline
    final def pure[S <: Stream[_, _], U, A](a: =>A) = new Parsec[S, U, A](s => _ => _ => eok => _ => eok(a)(s)(unknownError(s)))
    @inline
    final def join[S <: Stream[_, _], U, A](mma: =>Parsec[S, U, Parsec[S, U, A]]) = mma >>= (x => x)

    // Parser that consumes no input and generates an error
    @inline
    final def empty[S <: Stream[_, _], U, A]() = new Parsec[S, U, A](s => _ => _ => _ => eerr => Thunk(() => eerr(unknownError(s))))

    // More optimal version of: for (x <- p; y <- q) yield f(x)(y)
    @inline
    final def lift2[S <: Stream[_, _], U, A, B, C](f: =>A => B => C, p: Parsec[S, U, A], q: Parsec[S, U, B]): Parsec[S, U, C] =
    {
        new Parsec[S, U, C](s => cok => cerr => eok => eerr => 
        {
            val mcok: (A => State[S, U] => ParseError => Result[S, U]) = x => s_ => err => 
            {
                Thunk(() => q.unParser(s_)(cok compose f(x))(cerr)(y => s_ => err_ => cok(f(x)(y))(s_)(err ++ err_))(err_ => cerr(err ++ err_)))
            }
            val meok: (A => State[S, U] => ParseError => Result[S, U]) = x => s_ => err =>
            {
                Thunk(() => q.unParser(s_)(cok compose f(x))(cerr)(y => s_ => err_ => eok(f(x)(y))(s_)(err ++ err_))(err_ => eerr(err ++ err_)))
            }
            Thunk(() => p.unParser(s)(mcok)(cerr)(meok)(eerr))
        })
    }
    @inline
    final def fail[S <: Stream[_, _], U, A](msg: =>String)= new Parsec[S, U, A](s => _ => _ => _ => eerr => eerr(newErrorMessage(RawMessage(msg), s.statePos)))
    @inline
    final def label[S <: Stream[_, _], U, A](p: =>Parsec[S, U, A])(msg: String) = p ? msg

    // Provides a way of running a parser and if it fails ensures that
    // No input is consumed (i.e. we substitute cerr for eerr)
    @inline
    final def tryParse[S <: Stream[_, _], U, A](p: =>Parsec[S, U, A]) = new Parsec[S, U, A](s => cok => _ => eok => eerr => Thunk(() => p.unParser(s)(cok)(eerr)(eok)(eerr)))
}

// Here are the primitive parsers that actually affect the input
// that is stored in the parser State
object Prim
{
    def tokenPrim[S, T, U, A](showToken: =>T => String, 
                              nextpos: =>SourcePos => T => Stream[S, T] => SourcePos, 
                              test: =>T => Option[A]): Parsec[Stream[S, T], U, A] = tokenPrimEx(showToken, nextpos, None, test)
    @inline
    def tokenPrimEx[S, T, U, A](showToken : T => String,
                                nextpos :SourcePos => T => Stream[S, T] => SourcePos,
                                optionNextState : =>Option[SourcePos => T => Stream[S, T] => U => U],
                                test : T => Option[A]) =
    {
        new Parsec[Stream[S, T], U, A]({ case State(input, pos, user) => cok => cerr => eok => eerr =>
        {        
            input.uncons match
            {
                case None => eerr(newErrorMessage(SysUnExpect(""), pos))
                case Some((c, cs)) => test(c) match
                {
                    case Some(x) => optionNextState match
                    {
                        case None => 
                        {
                            lazy val newpos = nextpos(pos)(c)(cs)
                            lazy val newstate = State(cs, newpos, user)
                            cok(x)(newstate)(newErrorUnknown(newpos))
                        }
                        case Some(nextState) =>
                        {
                            lazy val newpos = nextpos(pos)(c)(cs)
                            lazy val newUser = nextState(pos)(c)(cs)(user)
                            lazy val newstate = State(cs, newpos, newUser)
                            cok(x)(newstate)(newErrorUnknown(newpos))
                        }
                    }
                    case None => eerr(newErrorMessage(SysUnExpect(showToken(c)), pos))
                }
            }
        }})
    }                
    def many[S <: Stream[_, _], U, A](p: =>Parsec[S, U, A]): Parsec[S, U, List[A]] = for (xs <- manyAccum[S, U, A](a => as => a::as, p)) yield xs.reverse
    def skipMany[S <: Stream[_, _], U, A](p: =>Parsec[S, U, A]): Parsec[S, U, Unit] = manyAccum[S, U, A](_ => _ => List(), p)
    def manyAccum[S <: Stream[_, _], U, A](acc: A => List[A] => List[A], p_ : =>Parsec[S, U, A]) = 
    {
        lazy val p = p_
        new Parsec[S, U, List[A]](s => cok => cerr => eok => eerr =>
        {
            val manyErr: A => State[S, U] => ParseError => Result[S, U] = 
                _ => _ => _ => throw new Exception("Combinator 'many' is applied to a parser that accepts an empty string")
            def walk(xs: List[A])(x: A)(s_ : State[S, U])(err: ParseError): Result[S, U] =
            {
                Thunk(() => p.unParser(s_)(walk(acc(x)(xs)))(cerr)(manyErr)(e => cok(acc(x)(xs))(s_)(e)))
            }
            Thunk(() => p.unParser(s)(walk(List()))(cerr)(manyErr)(e => eok(List())(s)(e)))
        })
    }

    def tokens[S, T, U](showTokens : List[T] => String, 
                        nextposs : SourcePos => List[T] => SourcePos, 
                        tts : =>List[T]): Parsec[Stream[S, T], U, List[T]] = tts match
    {
        case List() => new Parsec[Stream[S, T], U, List[T]](s => _ => _ => eok => _ => eok(List())(s)(newErrorUnknown(s.statePos)))
        case tok::toks => 
            new Parsec[Stream[S, T], U, List[T]](s => cok => cerr => eok => eerr => 
            {
                lazy val State(input, pos, u) = s
                val errEof: ParseError = newErrorMessage(SysUnExpect(""), pos).setErrorMessage(Expect(showTokens(tts)))
                val errExpect: T => ParseError = x => newErrorMessage(SysUnExpect(showTokens(List(x))), pos).setErrorMessage(Expect(showTokens(tts)))
                val ok: Stream[S, T] => Result[Stream[S, T], U] = rs =>
                {
                    val pos_ = nextposs(pos)(tts)
                    val s_ : State[Stream[S, T], U] = State(rs, pos_, u)
                    cok(tts)(s_)(newErrorUnknown(pos_))
                }
                @tailrec
                def walk(tts: List[T], rs: Stream[S, T]): Result[Stream[S, T], U] = tts match
                {
                    case List() => ok(rs)
                    case t::ts => rs.uncons() match
                    {
                        case None => cerr(errEof)
                        case Some((x, xs)) => if (t == x) walk(ts, xs) else cerr(errExpect(x))
                    }
                }
                input.uncons() match
                {
                    case None => eerr(errEof)
                    case Some((x, xs)) => if (tok == x) walk(toks, xs) else eerr(errExpect(x))
                }
            })
    }

    def lookAhead[S <: Stream[_, _], U, A](p: Parsec[S, U, A]) = new Parsec[S, U, A](s => _ => cerr => eok => eerr =>
    {
        val eok_ : A => State[S, U] => ParseError => Result[S, U] = a => _ => _ => eok(a)(s)(newErrorUnknown(s.statePos))
        Thunk(() => p.unParser(s)(eok_)(cerr)(eok_)(eerr))
    })

    def unexpected[S <: Stream[_, _], U, A](msg: =>String): Parsec[S, U, A] = new Parsec[S, U, A](s => _ => _ => _ => eerr => eerr(newErrorMessage(UnExpect(msg), s.statePos)))
}

Finally here are the Pos, Message and ParseError classes;

package parsec

case class SourcePos(name: String, line: Int, column: Int)
{
    final def compare(pos2: SourcePos): Int = 
    {
        val SourcePos(_, line2, column2) = pos2
        if (line > line2) 1 else if (line2 > line) -1 else 
        if (column > column2) 1 else if (column2 > column) -1 else 0
    }
    final def incSourceLine(n: Int) = SourcePos(name, line + n, column)
    final def incSourceColumn(n: Int) = SourcePos(name, line, column + n)
    final def setSourceName(name: String) = SourcePos(name, line, column)
    final def setSourceLine(line: Int) = SourcePos(name, line, column)
    final def setSourceColumn(column: Int) = SourcePos(name, line, column)
    final def updatePosChar(c: Char) = c match 
    {
        case '\n' => SourcePos(name, line+1, 1)
        case '\t' => SourcePos(name, line, column + 8 - ((column-1) % 8))
        case _ => SourcePos(name, line, column + 1)
    }
    final def updatePosString(s: List[Char]) = s.foldLeft(this)((pos, c) => pos.updatePosChar(c))

    final override def toString() = 
    {
        val showLineColumn = s"(line ${line}, column ${column})"
        if (name.isEmpty()) showLineColumn
        else s"""\"$name\" $showLineColumn"""
    }
}

case object SourcePos
{
    final def initialPos(name: String) = SourcePos(name, 1, 1)
    final val sourceName: SourcePos => String = { case SourcePos(name, _, _) => name }
    final val sourceLine: SourcePos => Int = { case SourcePos(_, line, _) => line }
    final val sourceColumn: SourcePos => Int = { case SourcePos(_, _, column) => column }
    final val incSourceLine: SourcePos => Int => SourcePos = { case SourcePos(name, line, column) => n => SourcePos(name, line + n, column) }
    final val incSourceColumn: SourcePos => Int => SourcePos = { case SourcePos(name, line, column) => n => SourcePos(name, line, column + n) }
}

import scala.math.Ordering

sealed trait Message
{
    def messageString(): String
    def toEnum(): Int
    final def ==(that: Message) = toEnum == that.toEnum
    final def !=(that: Message) = toEnum != that.toEnum
    final def compare(that: Message) = if (toEnum < that.toEnum) -1 else if (toEnum > that.toEnum) 1 else 0
    final def <(that: Message) = toEnum < that.toEnum
}
case class SysUnExpect(msg: String) extends Message { final def messageString(): String = msg; final def toEnum(): Int = 0 }
case class UnExpect(msg: String) extends Message { final def messageString(): String = msg; final def toEnum(): Int = 1 }
case class Expect(msg: String) extends Message { final def messageString(): String = msg; final def toEnum(): Int = 2 }
case class RawMessage(msg: String) extends Message { final def messageString(): String = msg; final def toEnum(): Int = 3 }

case class ParseError(pos: SourcePos, msgs: List[Message])
{
    final def ++(e2: ParseError) =
    {
        val ParseError(pos2, msgs2) = e2
        if (msgs2.isEmpty && !msgs.isEmpty) this
        else if (msgs.isEmpty && !msgs2.isEmpty) e2
        else pos compare pos2 match 
        {
            case 0 => ParseError(pos, msgs ++ msgs2)
            case 1 => this
            case -1 => e2
        }
    }

    final def errorIsUnknown(): Boolean = msgs.isEmpty
    final def errorMessages(): List[Message] = msgs.sortWith(_ < _)
    final def +(msg: Message) = ParseError(pos, msgs :+ msg)
    final def setErrorPos(pos: SourcePos) = ParseError(pos, msgs)
    final def setErrorMessage(msg: Message) = ParseError(pos, msg :: (msgs filter (_ != msg)))

    final def ==(that: ParseError): Boolean = 
    {
        val messageStrs: ParseError => List[String] = _.errorMessages().map(_.messageString)
        pos == that.pos && messageStrs(this) == messageStrs(that)
    }

    final override def toString() = 
    {
        def showErrorMessages(msgOr: String, msgUnknown: String, msgExpecting: String, msgUnExpected: String, msgEndOfInput: String, msgs: List[Message]): String = 
        {
            @inline
            def clean(msgs: List[String]) = msgs.filter(!_.isEmpty).distinct
            @inline
            def commaSep(ms: List[String]) = clean(ms).mkString(", ")
            def commasOr(ms: List[String]) = ms match
            {
                case List() => ""
                case List(m) => m
                case ms => s"${commaSep(ms.init)} $msgOr ${ms.last}"
            }
            val showMany: (String, List[Message]) => String = (pre, msgs) => clean(msgs map (_.messageString)) match
            {
                case List() => ""
                case ms => if (pre.isEmpty) commasOr(ms) else pre + " " + commasOr(ms)     
            }
            val (sysUnExpect, msgs1) = msgs span (SysUnExpect("") == _)
            val (unExpect, msgs2) = msgs1 span (UnExpect("") == _)
            val (expect, messages) = msgs2 span (Expect("") == _)
            val showExpect = showMany(msgExpecting, expect)
            val showUnExpect = showMany(msgUnExpected, unExpect)
            val showSysUnExpect = 
            {
                lazy val firstMsg = sysUnExpect.head.messageString
                if (!unExpect.isEmpty || sysUnExpect.isEmpty) ""
                else if (firstMsg.isEmpty) msgUnExpected + " " + msgEndOfInput
                else msgUnExpected + " " + firstMsg
            }
            val showMessages = showMany("", messages)
            if (msgs.isEmpty) msgUnknown
            else clean(List(showSysUnExpect, showUnExpect, showExpect, showMessages)).map("\n"+_).mkString
        }
        pos.toString() + ":" + showErrorMessages("or", "unknown parse error", "expecting", "unexpected", s"end of ${ParseError.inputName}", errorMessages)
    }
}

case object ParseError
{
    var inputName: String = "input"
    final def unknownError[S <: Stream[_, _], U](s: State[S, U]) = ParseError(s.statePos, List())
    final def newErrorUnknown(pos: SourcePos) = ParseError(pos, List())
    final def newErrorMessage(msg: Message, pos: SourcePos) = ParseError(pos, List(msg))
}

And, as promised, some example parsers;

/**`char(c)` parses a single character `c`. Returns the parsed character.*/
def char[S, U](c: Char) = satisfy[S, U](_==c) ? c.toString

/**This parser succeeds for any character. Returns the parsed character.*/
def anyChar[S, U] = satisfy[S, U](_ => true) ? "any character"

/**The parser `satisfy(f)` succeeds for any character for which the supplied function `f` returns
* true. Returns the character that is actually parsed.*/
@inline
def satisfy[S, U](f: Char => Boolean): Parsec[Stream[S, Char], U, Char] = 
    tokenPrim[S, Char, U, Char]("\"" + _.toString + "\"", pos => c => _ => pos.updatePosChar(c), c => if (f(c)) Some(c) else None)

/**`string(s)` parses a sequence of characters given by `s`. Returns the parsed string.*/
def string[S, U](s: String) = tokens[S, Char, U](_.mkString, _.updatePosString, s.toList) <#> (_.mkString)

// Running ss on "hello world! " will print "hello world"
val ss: Parser[String] = (string("hello world") <* char[String, Unit]('!'))
println(runParser[Stream[String, Char], Unit, String](ss, (), "", "hello world! "))

//Running as on "aaaaabbaa" will print "aaaaa"
val as: Parser[String] = (many(char[String, Unit]('a'))) <#> (_.mkString)
println(runParser[Stream[String, Char], Unit, String](as, (), "", "aaaaabbaa"))
\$\endgroup\$
1
\$\begingroup\$

The use of stack tracers is somewhat unconventional in a standard parsec implementation, however this appears to be functional. I would recommend having a look at "implementing parsec compilers in Functional Scala" by Shenzun Wong, this should give you a more grounded understanding of the intricacies of the process.

I would recommend replacing the use of streams with a standardised StreamBuf monad. This would allow you to abstract away some of the additional complexity introduced when you create parsers. It would also allow you to directly translate certain parser definition languages into a use-able parser with minimal additional overhead.

Finally, I would look into improving the verbosity of your code. It is rather difficult to extract the semantic meaning when you consistently use inconsistent patterns. Have a look into code normalisation, this helped me a great deal when writing a modular parser.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.