3 ms·

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 th

by dgb23 5y ago

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...

soegaard 5y ago
In case you keep the S-expressions: http://www.ccs.neu.edu/home/shivers/papers/sre.txt http://www.ccs.neu.edu/home/shivers/papers/sre.txt https://docs.racket-lang.org/parser-tools/Lexers.html#%28form._%28%28lib._parser-tools%2Flex..rkt%29._lexer%29%29 https://docs.racket-lang.org/parser-tools/Lexers.html#%28for...
- dgb23 5y ago
  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!
greenshackle2 5y ago
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.)
ufo 5y ago
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.

by dgb23 5y ago

soegaard 5y ago

In case you keep the S-expressions: http://www.ccs.neu.edu/home/shivers/papers/sre.txt http://www.ccs.neu.edu/home/shivers/papers/sre.txt https://docs.racket-lang.org/parser-tools/Lexers.html#%28form._%28%28lib._parser-tools%2Flex..rkt%29._lexer%29%29 https://docs.racket-lang.org/parser-tools/Lexers.html#%28for...

dgb23 5y ago
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!

greenshackle2 5y ago

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.)

ufo 5y ago

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.