Combinator parsing… library bug?

4 replies

Fri, 2009-07-10, 16:26

Andrew Forrest

Joined: 2008-12-20,

Hi all,
I’ve been writing some Scala code to parse a simple programming language. The language’s syntax is similar to JavaScript, so it has block comments (/* like this */), line comments (// like this) and strings ("in double quotes" or in 'single quotes'.) It has a lexer component and a parser component. The lexer was originally based on scala.util.parsing.combinator.lexical.StdLexical, specifically these bits:
def token: Parser[Token] = ( letter ~ rep( letter | digit ) ^^ { case first ~ rest => processIdent(first :: rest mkString "") } | digit ~ rep( digit ) ^^ { case first ~ rest => NumericLit(first :: rest mkString "") } | '\'' ~ rep( chrExcept('\'', '\n', EofCh) ) ~ '\'' ^^ { case '\'' ~ chars ~ '\'' => StringLit(chars mkString "") } | '\"' ~ rep( chrExcept('\"', '\n', EofCh) ) ~ '\"' ^^ { case '\"' ~ chars ~ '\"' => StringLit(chars mkString "") } | EofCh ^^^ EOF | '\'' ~> failure("unclosed string literal") | '\"' ~> failure("unclosed string literal") | delim | failure("illegal character") )
// see `whitespace in `Scanners' def whitespace: Parser[Any] = rep( whitespaceChar | '/' ~ '*' ~ comment | '/' ~ '/' ~ rep( chrExcept(EofCh, '\n') ) | '/' ~ '*' ~ failure("unclosed comment") )
protected def comment: Parser[Any] = ( '*' ~ '/' ^^ { case _ => ' ' } | chrExcept(EofCh) ~ comment )
Note the 3 'failure' lines for unclosed comments or strings. I was seeing odd behaviour in my own code in that none of these ‘unclosed’ failures seemed to be firing. For the strings, I got
`"' expected but X found (where X was a newline or the end-of-file character); for the block-comments, I had other code which was picking up the ‘/*’ as an identifier. (Like Scala, my language allows symbolic identifiers, so if it wasn't the start of a comment, "/*" would be a legal identifier.)
I think there are two problems here:
1. The 'failure's should be 'err's. Otherwise,
a. because of the way Parser.Failures compose, the last parse failure is the one returned, so in the case of strings, the fact it's found the end of the file (or the end of the line) is returned rather than the 'failure' at the start of the unclosed string; b. inside the 'rep' in 'whitespace', the failure is just treated as a failure to match, and it's merrily ignored!

However, even this does not solve the problem. If a parser returns a Parsers.Failure, any attempt to backtrack will never return a Parsers.Error (only Parsers.Success, if one is found).
To make parsing code work with ‘err’s, you need to positively search for the error condition (an unterminated string/comment) BEFORE anything which could return a parse failure later in the stream.
I’m on shakier ground here, in terms of my understanding of the whole thing, but I believe that scala.util.parsing.combinator.Parsers.Failure could (should?) be changed:
case class Failure(override val msg: String, override val next: Input) extends NoSuccess(msg, next) { /** The toString method of a Failure yields an error message */ override def toString = "["+next.pos+"] failure: "+msg+"\n\n"+next.pos.longString def append[U >: Nothing](a: => ParseResult[U]): ParseResult[U] = { val alt = a; alt match { case _: Success => alt case _: Error => alt case _: Failure => if (alt.next.pos < next.pos) this else alt }} }
I believe this would allow the parsing to backtrack from a ‘Failure’ to an ‘Error’. Which makes sense, because otherwise ‘Error’s don’t stop the parse, like they’re supposed to. I don’t have my head round combinator parsing enough to know if this would have other horrible side effects, though.
In my case, rather than modifying the scala-library, I found that I could achieve what I wanted by making my ‘Failure’s into ‘Success’es, and returning ‘ErrorToken’s directly, (instead of trying to indirectly cause them through ‘err’):
| '\'' ^^^ ErrorToken("unclosed string literal") | '\"' ^^^ ErrorToken("unclosed string literal")

Anybody any comments?
–Andrew