Comment by dgb23 | Hacker News Reader

Comment by dgb23 | Hacker News Reader

Here is my journey with this book so far:

I decided to follow the book but write in Clojure (at least the interpreter) instead of Java.

This went well, but then I decided I also wanted to write the lexer as a state machine in a data DSL (nested maps).

This went kind of well, but it seemed incredibly verbose, because a ton of states would have the same input messages, so I decided to write a macro that maps regular expressions to tokens one to one and produces a (data DSL) state machine that later drives the lexer.

Then I realized that I get a non-deterministic state machine that I needed to convert to a deterministic one.

Then I decided that the string representation of regular expressions suck, and that I want to write a DSL for those too...

Then left at the above, switched to a few other books in between and am trying to decide whether I should ditch the lexer entirely and just use s-expressions. I probably won't, because it's fun so far, but boy did I get sidetracked...

That's what I did. I made a Scheme instead of Lox because I'm not that interested in parsers; s-expression recursive descent parsers are almost trivial to implement. And I wanted to try implementing macros, which are so much simpler in a Lisp.

I loosely followed the second half of book - but I found that for a Scheme or Lisp, it made more sense to have separate parsing and compilation steps. Because implementing quotation is trivial if you parse first, but would have been kind of messy to do in a single pass.

(I also used Rust instead of C, which means I skipped a lot of the memory management code, at the cost of more indirection in some places.)

It can be simpler to not make a finite state machine. Instead, try the different alternatives one by one, the longest one first.

Instead of

    if (next == '>') {
        advance()
        if (next == '=') {
            advance()
            return GREATER_EQUAL
        } else {
            return GREATER
        }
    }

it can be simpler to do

    if (next is ">=")
        return GREATER_EQUAL
    if (next is ">")
        return GREATER

The price is a little bit of performance. It needs more than one character of "lookahead" and may have to re-scan some parts of the input.

In case you keep the S-expressions:

http://www.ccs.neu.edu/home/shivers/papers/sre.txt

https://docs.racket-lang.org/parser-tools/Lexers.html#%28for...

Just for clarification: I meant S-expressions for the language in the book (by changing the proposed syntax) so I can dramatically simplify the lexer.

But using s-expressions for regular expression DSL is a given, since I would do it in macros. The resources you linked seem fantastic, thank you!

Reply on news.ycombinator.com