Based on new knowledge, going to implement a new scanner and parser for toml.

General Steps to Scanning/Lexing

The job of a scanner is to go from characters to words. In our case, we aggregate characters into words related to TOML and decide if they are valid. What seperates words are punctuators or delimeters.

Each type of word, akin to “noun” or “verb” in english is called a Syntax category.

The way to go about creating a scanner is to think about the act of recognizing words as a finite state machine where states exist and the edges represent which is the next character that is scanned. All of this can be formalized using finite automata. These define states, transitions, an error state, and acceptance states. what’s cute is that when everything is mathematically formalized, it can be shown that it’s really just one function called on itself over and over again(akin to lisps).

In order to handle infinite things(like numbers), we allow cycles.

The set of words accepted by a finite automaton forms a language. We can describe a language using what we know as regular expressions. Regular expressions really rely on three simple rules(that get combined and composed over and over due to the set of regular expressions being closed on these operations)

The three operations are:

Alternation R | S = {x | x in R or x in S}
Concatenation { xy | x in R y in S}
Closure Union of concatenations 0 or more times

Every other regex syntax is really sugar over compositions of these three things.

So, to describe any language you first:

Generate finite automata for the smallest pieces of the alphabet in the language
Generate finite automata for concatenation of all of them(there are many states of this obviously, potentially infinite)
Generate finite automata for alternation
Generate finite automata for Closure

Use Thompson’s construction and pare that down using algorithms. Then impelment. Or, in the real world...

Identify your language and lexeme categories you want Generate regexes that map to those lexemes Use the regexes to generate finite automata graphs in the human readable form(or use automated programs but that’s gay) Implement those into code.

Step 1: Identifying Which Lexemes of TOML We Want

Table Headers(no array tables)
keys, both regular and dotted. Not quoted.
Strings
Arrays of strings
Boolean ie true or false keywords

The rest we can ignore. So what are the rules for these things based on TOML spec?

Table Header

with square brackets on a line by themselves Bare keys may only contain ASCII letters, ASCII digits, underscores, and dashes (A-Za-z0-9_-).

Keys

Bare keys may only contain ASCII letters, ASCII digits, underscores, and dashes (A-Za-z0-9_-). Dotted keys are a sequence of bare or quoted keys joined with a dot. This allows for grouping similar properties together: Defining a key multiple times is invalid. Same with tables.

Strings

Only support basic strings, with no escape characters. No new lines. Basic strings are surrounded by quotation marks ("). Any Unicode character may be used except those that must be escaped: quotation mark, backslash, and the control characters other than tab (U+0000 to U+0008, U+000A to U+001F, U+007F).

Arrays

Arrays are square brackets with values inside. Whitespace is ignored. Elements are separated by commas. Arrays can contain values of the same data types as allowed in key/value pairs. Values of different types may be mixed.

We only care about string values.

Boolean

true or false, only in the value portion

Step 2: Creating regexes for each thing

Table Header - [[a-zA-Z0-9-_]+(.?[a-zA-Z0-9-_]+)] Keys - Same as table header, but without the outter square brackets. Strings - "[^\n\]" <- this is too primitive, but it’s fine for now. Boolean - [true | false] Arrays - handle and build them up at compile step since we have no lookahead.

We also want to track individual punctuators:

array start, comma, array end, equals, newline, whitespace. Comments we skip.

This should cover everything.

Step 3: Creating DFA’s for Each Regex

Done in my notebook.