CODEWITHSUNDEEP
parsingexceptionocamlrecursive-descent
destrius
destrius

Reputation: 33

Using option types instead of exceptions for a recursive descent parser?

I'm writing a simple recursive descent parser in OCaml. Typically (as far as I can tell from the tutorials online and in books), exceptions are used to indicate parse failures, for example:

match tok with
   TokPlus -> ...
 | _ -> raise SyntaxError

However, I'm thinking of using the option type instead, i.e.:

match tok with
   TokPlus -> Some(...)
 | _ -> None

The main reason I want to do this is that using option types allows me to optimize some of my combinators to be tail-recursive.

Are there any shortcomings with using options instead of exceptions? Will this decision bite me in the foot as I start parsing more complex structures?

Upvotes: 3

Views: 399

Answers (3)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

The great thing about recursive descent parsing is that you can write the code any way you like (within reason). I don't see a problem writing tail recursively with or without exceptions, unless you would imagine catching exceptions in all your intermediate functions. More likely you'd have one (or a few) exception handlers near the top of your grammar, in which case all the code below could easily be tail recursive.

So, I agree with ygrek that the exception style is quite natural for parsing, and I don't think using exceptions necessarily precludes tail recursive style.

Upvotes: 1

ygrek
ygrek

Reputation: 6697

I believe exceptions optimize the common case - the code path for successful parse is simpler. Usually when parsing it is all or nothing - either everything parses ok and you return the final result or something breaks - and you don't care where it breaks because you are not going to handle it anyway, except to print meaningful message, but one can skip that step too :) So looks like a perfect match for exceptions.

Upvotes: 2

Ira Baxter
Ira Baxter

Reputation: 95402

No, but you'll likely have to add (a lot of) dummy rules to propagate the error back to the root production of the grammar.

The point of exceptions is you don't have to add exception handlers to each routine; you get implicit propagation.

Is there a specific reason you want optimized tail recursion? Most parsers don't actually produce very deep call stacks (a few hundred levels for really complex stuff). And I doubt the time savings is significant compared to all the other work being done by the non-parser part.

Upvotes: 3

Related Questions