Hacker News Reader

Comment by FeepingCreature | Hacker News Reader

I don't understand why people use FSMs or parser tools.

I wrote the parser for my script language, jerboa ( https://github.com/FeepingCreature/jerboa ) over a few days; it's (I thought) entirely standard recursive descent single-pass. This is how I've always written parsers. Where would you even use FSMs for parsers?

View on HN

> Where would you use FSMs for parsers?

For the lexing (lexical analysis) stage of the parser. I know that the alternative to using a lexer (for which the tokens are specified by regular languages, thus lexed by FSMs) is to use so-called scannerless parsing (this is possible since every regular-language is context-free, thus the tokens can also be specified by the original context-free grammar). But using this alternative is usually much more painful since you usually want the grammar to have a nice property that allows linear-time parsing and a unique parse tree. LR(k), LL(k) etc. are such properties. Such properties are much more difficult to ensure for scannerless parsing.

Except no, lexing is trivial; it is by far the easiest part of writing a compiler. You don't need anything fancy, you just type in the code.

If you want to write a lexer from scratch, this is IMHO not trivial. If you use a generator it is much easier, but so is also using a parser generator for the CFG parsing stage.

Hand-rolling a lexer seems pretty trivial to me. The code writes itself. A generator is a tool whose limitations you have to work around, be it for a lexer or a parser.

If you can't write a lexer by hand, just forget trying to write a compiler that does anything interesting, because the lexer is MUCH easier than any other part of the compiler.

There are a lot of reasons for this, but one of the basic ones is that the lexer does not need to interact in a complex way with the compiler's state. It is a relatively simple pipeline where characters go in one end and tokens come out the other.

When you add unicode, it can become more complicated (or rather, cumbersome)...

Well, you just need to call unicode_next_character all the time instead of saying s++, similarly for whitespace, similarly for asking whether a character can initiate or continue an identifier, etc. It does not change the basic nature of the task at all.

Sure, but if you are using a language without support for unicode, and you don't use a dedicated library (which would be already using a kind of lexer, wouldn't it?), you have also to parse these unicode characters yourself.

A unicode_next_character function is very simple to write regardless of unicode support in your language.

I usually write it as a small (256 byte) lookup table where each entry tells you how many characters to skip next. If you don't use a lookup table, its 4 single-line `if` statements (and if you do it's a one liner, plus however many lines the table takes).

There's free source code for basic Unicode operations all over the internet.

Here's a video of Rob Pike, developer of Go, talking about a lexer he built for the Go text/template package:

https://www.youtube.com/watch?v=HxaD_trXwRE

It supports unicode.

The only actual increase in difficulty from scannerless parsing is having to janitor whether a function will always slurp up whitespace before it finishes. Linear-time is easy, questions of unique parse tree are irrelevant because the only ambiguity is who owns a piece of whitespace that gets discarded anyway.

What wolfgke said. I (personally) use FSMs as my swiss-army chainsaw a lot. I realize that this isn't common practice, but I came from silicon, so what are ya gonna do?

Reply on news.ycombinator.com