Hacker News Reader

Comment by aidenn0 | Hacker News Reader

The more I work with languages, parsing, etc. the more I think that the lexer/parser setup is a bad idea. Many non-trivial languages are actually harder to implement clearly in the traditional lexer/parser setup due to required coupling between the lexer and parser.

View on HN

Really? Why would they be coupled? I mean, maybe a little bit. For instance, maybe the parser could tell the lexer what kind of token it expects to see next, so that the lexer doesn't parse an int as a float by mistake, but that doesn't sound that bad to me. (I should point out that my experience here is a single class in college.)

The traditional theories about parsing and their implementations in tools like yacc, lex, antlr, etc. are not that important in practice. I also used them in some university courses, but after I encountered parsing problems in practice it seemed easier to just implement a recursive descent parser in the host language.

First, you have to learn the DSL's of these tools (which are non-trivial in detail). Second you have to integrate them into your toolchain. Third - and that is my biggest complaint - you have to connect the Parser combinator's AST to your domain AST. The last thing is pretty amusing as I consider it the main purpose of a parser.

In practice (hopefully after evaluating the need for a custom data format as it might be possible to hijack existing languages and standards) I either use a combinator-parser (if FP available) or an ad-hoc recursive descent parser. Maybe I consider a lexer but the representation of tokens is also a non-trivial decision.

Most languages will have some sort of way of letting you extend them; inasmuch as this will require a new way of lexing, this will add some coupling.

One example: shell aliases. The shell syntax in POSIX is defined in the standard lexer/parser divide (which is already a bit of a pain, as a significant of the parsing logic is needed to correctly tokenize command expansions). When you encounter an alias expansion (which since it has to happen in the command position, doesn't happen until parse time) you expand the alias, and then need to re-lex the results.

In practice, many mature compilers and interpreters use a recursive-descent parser rather than any of the LL/LR/LALR things I learned in school.

Common Lisp actually defines its syntax in terms of a recursive-descent algorithm, and that's a language that largely came out of academia.

Reply on news.ycombinator.com