Hacker News Reader

Comment by ci5er | Hacker News Reader

It's a pain and not something you really keep touching again and again once you've got it baked.

I've done it a number of times and I've had to relearn ANTLR each time (or fall back to flex/yacc or perl if I'm feeling grungy or go commando with a hand-crafted FSM if I'm on an odd machine architecture)

Is this something that you'd expect people who code even daily to be able to whip out without looking at a man page?

View on HN

Sure,

All of the parser-generator tools are really opaque and not something that can be easily used for simple things. On the other hand, recursive descent parsers are something that can be whipped easily if you have a little project. And the problem is that a lot programmers both can't produce a recursive descent parser AND don't know when their problem domain is moving into a place where such a thing is needed.

Fair enough. They're not rocket science conceptually - but I have to relearn the tools each time. Not a huge deal - a couple of hours - but I was thinking that you were claiming I needed to have it down as cold as when I got out of CS 202 (or whatever that thing was).

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?

> 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