Exceptional Parsing, or using JavaScript exceptions as a substitute for algebraic expressions

Articles

Parsing is one of those intermediate-level algorithms, which, like state machines, you may not use on a day-to-day basis as a developer but their understanding helps with your mental model of programming.

In its simplest form, parsing is a method of turning a stream of tokens (such as the sequence of individual characters in a string) into a higher level data structure based on the content and sequence of those tokens. It is used for converting JSON text into JavaScript objects, for example, and by the JavaScript interpreter itself to turn source code into something which can be executed.

The quality of a parser comes down to performance, but also down to ease of use - because you, the developer, have to write the rules for parsing your input stream and generating your output data structure. You also have to specify all the error conditions and give them suitable error messages.

The Shape Of Parsing

Parsing follows the shape of "Structured Progamming" in the sense that it needs the same three basic constructs:

  • Sequencing - the ability to match one rule after another in the inpout stream
  • Switching - the ability to match any one of a set of rules in the input stream
  • Recursion/iteration - the ability to match one or more instances of a rule

Developer experience

Sometimes a good way to approach a problem is asking what interface would be most conventient and easy to use for end-user developers.

If I wanted to parse some text, I would like to write something like this in JavaScript:

// This turns a string like "[ 123.234, 456.11 ]" into an object like {x:123.234, y:456.11} const vector2 = Parse.Text( myTextString, parseVector2Rule )

And to define a rule I want to specify in sequence the values which should be parsed from the string, and what final value they are turned into. For example:

// This is a rule which parses three numbers in an array in this format, // allowing for optional whitespace: // [ 123.234, 456.11 ]

parseVector2Rule = () => {

//  This consumes exactly the character '[' or throws a NoMatch exception
Parse.Match.Text.Exact( '[' )

//  This consumes zero or more whitespace characters
//  This returns the whitespace characters in case they are needed
Parse.Match.Text.OptionalWhitespace()

//  Grab the first number
const x = Parse.Match.Text.Number()

//  Grab a comma with optional whitespace around it
Parse.Match.Text.OptionalWhitespace()
Parse.Match.Text.Exact( ',' )
Parse.Match.Text.OptionalWhitespace()

//  Grab the second number
const y = Parse.Match.Text.Number()

//  Grab the final closing square bracket
Parse.Match.Text.OptionalWhitespace()
Parse.Match.Text.Exact( ']' )

//  Return the parsed data structure
return {x, y}

}

Note that unlike many parsing libraries, I want the rule to return the final parsed value, not an intermediate format that the parser provides which then needs further processing.

For switching, I want to be able to specify a set of rules which will be checked in order, and the first one which does not throw a NoMatch is the match.

This parse rule matches any kind of vector (two, three or four dimensional), returning the object returned by the matching rule:

parseAnyVector = () => {

return Parse.Match.Any( () => {
  Parse.Match.Option( parseVector2Rule )
  Parse.Match.Option( parseVector3Rule )
  Parse.Match.Option( parseVector4Rule )
})

}

Parse.Match.Any works by calling the provided callback containing the options. The value returned from this function is the value returned by the matching rule.

The final axiom is iteration, so lets go ahead and look at how that could be achieved:

// Define a separator rule which we will use when matching a list of items below // The spearator is a comma character with optional whitespace around it const separatorRule = () => {

Parse.Match.Text.OptionalWhitespace()
Parse.Match.Text.Exact( ',' )
Parse.Match.Text.OptionalWhitespace()

}

// This parses any array of numbers, returning a JavaScript Array object const parseAnyArray = () => {

//  Open square bracket
Parse.Match.Text.Exact( '[' )
Parse.Match.Text.OptionalWhitespace()

//  Match a list of numbers, using the separator
//  This returns an array of the results of the matching Parse.Match.Text.Number rules
const numbers = Parse.Match.List( separatorRule, Parse.Match.Text.Number )

//  Close square bracket
Parse.Match.Text.OptionalWhitespace()
Parse.Match.Text.Exact( ']' )

//  Return the array of numbers
return numbers

}