Home » forums » LtU Forum

Parser error handling without exceptions

In brief
------

I'm porting an existing compiler/interpreter framework to Swift, from a more imperative code base. It currently exists in JavaScript (feh), Dart, and Objective-C. It has more-or-less the same (recursive descent) structure in all three languages; in particular, I use exceptions to immediately bail when I encounter a syntax error.

My proximal question is: how can I structure an exception-free parser to conveniently handle syntax errors? My more global question is: how do people do that in an idiomatically functional way?

Remarks
-------

Just about every line of parser code can (transitively) result in a syntax error. For example, to parse the language construct "split x into y" I write (roughly):

acceptToken(split)      // Could fail if split is misspelled
source = expression()   // Could fail if expression is faulty or missing
acceptToken(into)       // Could fail
dest = expression()     // Could fail
acceptToken(newline)    // Could fail
return new JoinNode(source, dest)

It is convenient to expect that any of these calls will throw an exception, in particular that lines subsequent to the failure will not execute. Repeated wrapping and testing each line is just the sort of thing exceptions are supposed to save us from. (Although I agree the details of handling exceptions — rolling back the program state — are almost impossible to get right.)

What I am looking for is a design architecture that will let me continue exploit the isomorphism between the grammar and the code structure: one term in the grammar maps to one line of parser code. Not one line of parser code, wrapped in conditional tests, with each line testing the success/failure of its predecessor.

There have been some suggestions in this thread:

https://devforums.apple.com/thread/227375?start=0&tstart=0

that involve optional types and comparisons to languages like Rust and Scala, but I did not see usable ideas from actual compiler writers. Suggestions or pointers/references welcome.

By andrewzboard at 2014-07-19 22:32 | LtU Forum | previous forum topic | next forum topic | other blogs | 3753 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Parser combinators

Look into parser combinators, such as Haskell's Parsec package or Text.ReadP. These could express your current program almost exactly.

By dmbarbour at Sun, 2014-07-20 00:33 | login or register to post comments

Backtracking

In order to express the rules separately (using combinators or whatever) backtracking is the critical mechanism. Without backtracking you have to accept symbol at a time and know which alternatives are available at each step. The data structure would look like a regular tree for this (branching at the choice points) rather than a table of separate rules.

By Keean Schupke at Sun, 2014-07-20 07:51 | login or register to post comments

Swift "has" exceptions

It just forces you to note them at the type level. The trivial case is Optional, which enforces handling of null pointer exceptions. There aren't traditional exception handling with try-blocks and what not, but pattern matching on an algebraic data type (enumerations in Swift) are equivalent. Another example would be NaNs and Infinities... these are exceptional values of floats, but they don't "raise" exceptions. Any function that takes in a float is expected to handle these values appropriately, along with all other values of floats. With algebraic data types, the compiler can actually enforce that each case is considered. Some IDEs attempt to warn you when you aren't handling exceptions raised in some exceptional languages, but I've not seen one that was correct all the time, nor do these languages have compile-time static analysis enforcing exception handling at all points. Perhaps there's something to be said along the lines of 'all languages with exceptions are dynamically typed', but I'm not willing to go that far.

Initially I was worried that Swift left out exceptions because Go has done alright without exceptions, but Go's syntax for error handling is rather obtuse. Upon realizing that Swift left out exceptions more because of Haskell's head [], I was much less disappointed in Swift.

By kms at Sun, 2014-07-20 15:04 | login or register to post comments

unwinding

Thanks kms, I did notice that there is a notion of exceptional behavior in Swift. What I am looking for is exception-style flow control, in particular the unwinding of deeply-nested, possibly recursive, activation record stacks. As Keean pointed out in the original Swift thread, this is very helpful in writing a parser where *every* line of code can (transitively) discover a syntax error, and must therefore somehow be prepared to alter flow control. Wrapping a method (and implicitly-transitively all its called methods) in a try block says "Every line of this block has an automatic test-and-break added to it."

I see that optional types and monads can achieve similar flow control and will try to wrap my imperative head around it.

By andrewzboard at Mon, 2014-07-21 02:49 | login or register to post comments