Hacker News Reader

Comment by gavinhoward | Hacker News Reader

I usually love Laurence's posts. However, one thing he said in this one is wrong in my experience.

> Since some parsing approaches such as recursive descent parsing unify these phases, why do lex and yacc split them apart?

I have written two recursive descent parsers for one small, but production quality compiler. I am in the middle of writing another two, which will also be production quality and much bigger. And I have written various small parsers.

I always use recursive descent, and I always split the lexing and parsing phases.

Now, I fully acknowledge that my experience could be an outlier, but I believe the benefits of lexing are so big that most recursive descent parsers have separate lexers.

View on HN

I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand.

They're still separate modules. You just don't have to run lexing to completion ahead of time (and as a consequence, it's natural to let lexing be context-sensitive where needed).

> I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand.

You even get this for free in a lazy language like Haskell, where your parser can accept a list of tokens `[Token]` whilst the list itself is only computed on-demand whenever the parser tries to get the next one.

Well, except for the context-sensitive option:

> (and as a consequence, it's natural to let lexing be context-sensitive where needed).

This is how I am setup in the little language I am writing in C++. I put the lexer into an iterator.

> I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand.

This is how I implemented it in my language. Evaluator asks parser for a value, parser asks lexer for one or more tokens, lexer asks the I/O layer for characters. It's nice.

A Javascript parser have to do something like this. The text /a/ tokenize differently depending on where in the grammar, eg a/b/c is division (/a/) is a regex.

That's not unusual though and can just be normal lexing (or parsing - IMO it can be a pretty arbitrarily drawn line) e.g. in many languages = 'tokenises differently depending on where it is in the grammar': a = b is assignment; a == b is an equality test.

No, = or == is purely a lexer decision easily decided by greedy _character_ matching and easily resolved.

In JavaScript the following give wildly differently shaped ASTs since the / character initiates RegEx parsing when in a _value position_ that has different lexing than the division operator that _only_ appears as a potential binary operator, consider the following:

a = b + /c.y/+d

a = b /c.y/+d

(Given b=1 , c={y:2} and d=3 )

The first assigns a as add b to the RegExp matching c.y added to +d giving us the string "1/c.y/3" (JS converts most types to string on addition and strings are dominant during addition as concatenations), this is correct since the + operator before the / character forces the parser to look for a value.

The second reads as assign a to b divided by property y of c then divided by d (ie the numeric computation (1/2)/3 = 0.166666.... ), this is because the parser is looking for binary operators after the b identifier and when the / character appears it becomes an operator.

So, without knowing the parsing context (operator or value position) the lexer decision is ambigious.

This is somewhat how A<B<C>> is ambigious when parsing C++/Java/C# templates/generics VS the <, > and >> operators but that case is usually easier since the parser could include a hack in the generic parsing code that mutates the token stream if it encounters >> when closing a generic. (The JS ambiguity is worse though since RegEx lexing rules are totally different from regular JS)

True; but the division vs regex example that I replied to was also 'easily decided bg greedy character matching and easily resolved.

I don't know how JS (implementations) actually does it, but this is what I meant by the line being a bit arbitrary, in my limited experience - you can just lex 'forward slash token' or whatever and keep your lexer/parser separation even with this ambiguity.

With horrible hacks in the reference - search for InputElementDiv and InputElementRegExp if you want to read more about it.

It's not so bad in practice, since you only need to look at the previous token to decide whether a / should be parsed as a division or regular expression, once you've excluded the possibility for // and /* comments.

Comments are also why the empty regular expression in JavaScript must be written as /(?:)/

How about this:

    ( x ) / b / a

It could be part of:

    var x = (x) / b / a;

    if (x) /b/a.test(z)

X could be an arbitrary complex expression. Looking at one preceding token is not enough to disambiguate the slash.

I suspect the only real solution is to intertwine lexing and parsing, so the parser asks for the next token with a flag indicating context. But this constrains what parsing algorithm can be used.

Consider this text: /a+ ”/ How would you tokenize this if you don’t know the grammar context? If it is a regex, the space is significant - it is part of the pattern. If it is a divsion, the quote will start a string.

Most lexers just match the longest legal token, so there is no ambiguity between = and == and the grammar does not influence tokenization.

The issue with JavaScript is that say /a+”/ tokenize differently based on the position in the grammar, so you can’t tokenize in a seperate pass before parsing.

My experience is that splitting lexing and parsing is by far the norm, even in recursive descent.

Oh, thank you! I was wondering if I was an outlier.

Nah, I’ve been toying with writing a compiler and that’s where I’ve gotten to too, it seems to my inexperienced self at least, if what you’re implementing is a specified language, combining the phases makes sense since you only have one thing per language, but while making a language and experimenting, having them be separate helps reduce a lot of complexity in the parser for things like tokens that go across multiple lines.

I have no idea if the above observations are generally true, but that’s been my experience with the handful of parsers I’ve thrown away because they get too unwieldy for what I want.

Funny; my experience is the opposite.

My first production-quality parser was for the `bc` language, which is specified in a standard.

But your experience is just as valid as mine.

I know right?

I had a friend in college who nearly always solved problems 'backwards' to everyone else cause it's just how her brain worked, like we'd do a standard for(int i = 0; i < length; i++) and she'd have for(int i = length; i >=0; i--) kinda backwards.

I don't question it at this point anymore and just marvel at the mathematical validity of it all.

It's buggy though

It definitely can be, and it was mostly an illustrative example for the ‘mathematical validity’ part of my comment. When you’re just starting out, working valid code is better than nothing!

I think you're right that most modern recursive decent parsers have separate lexers, but I think what you'll find in many older recursive descent parsers is that when it's clear which token type may come next, the parsers will often call a specialised function that will return or throw an error if it's not that specific type.

E.g. you might be calling a "getIdentifier()" function instead of a generic "getToken()".

In practical terms you sort-of have a lexer separation anyway - you will have a set of functions that each lexes one type of token. You just call them directly instead of letting a generic function discriminate between the token types.

But a generic separation works also for grammars where a scannerless approach is awkward. It's always possible; worst case you add support for backtracking and/or add helpers for more generic parses, but if you need to jump through hoops like that it quickly gets silly. And if you're first used to the separation there's little reason to write parsers in two different ways depending on the grammar.

Ultimately I think that's the reason why scannerless parsers are relatively rare.

That's how most of my recursive descent parsers have worked. I think the first ones I wrote did have a lexer/parser split and then I realized it was easier to use the specific calls for each expected token class.

Most of mine too. When you're hand-writing the whole thing anyway, and the grammar makes it obvious the next token can only be an identifier it feels wasteful to call a generic function, and so I rarely add a generic function unless I get to somewhere in the grammar where there's no easy way to determine a single or small set of token types to parse. But at the same time, if you're reaching for automation the lexer side is easier to automate "cleanly" and most of the automation tools tend to provide a single entry-point.

In my first C compiler, I combined the lexer and preprocessor. That was a mistake. The (much) later one I wrote, Warp, tokenized and then preprocessed. It was much easier to work with.

It is also about performance.

I've watched a video recently from a guy who compiled entire Linux kernel in under 1 second I believe, he used TinyC and also noticed that something like 90% of compilation is tokenization of headers that are included many times, like there are headers that are included thousands of times in almost every C file, so he ended up caching tokens. So a big reason to have a separate tokenizer is that tokenization is a simpler task and can be optimized with all low level approaches, like perfect hashes, crafted nested switch/if tries, branchless algs, compiler intrinsics etc.

The good tokenizer is about as fast as a speed of writing the output array of records into memory. Which means it is important to choose right memory layout for your tokenized data so that when parser reads tokens it has as little cache misses and indirect memory access as possible. Tokenization can be thought of as a sort of in memory compression.

Excellent summary. A couple other reasons for a separate tokenizer:

1. Sometimes all you need is a tokenizer - such as for highlighting in a code editor

2. D has a construct called a token string - where a string literal consists of tokens

3. A separate tokenizer means the lexer and parser can run in separate threads

I won't say this is the explicit reason recursive descent parsers have separate lexers, but there is a major downside to folding the lexer into a recursive descent parser, which would occur when/if you make the leap to packrat parsing. If the parsed language develops far enough you'll often run into edge cases where backtracking can become pathological. One benefit to recursive descent is that you can often just fix this by memoizing the parser functions (called a packrat parser).

However, you really don't want to memoize calls to lexer-y parser functions because it's almost always faster and less memory-intensive to simply re-lex the source string. This gets more complicated if you're parsing a stream (but if your language is being parsed from a stream you should definitely be giving strong preference to language constructs which don't require backtracking).

Incremental re-Lexing works great in IDEs where you want to preserve tokens and the state associated with them. It also helps to isolate errors by attributing them to a token that contains the change rather than somewhere far off. Incremental parsing is the same: it costs more in terms of memory and even overall time, but provides better feedback for the IDE.

Batch compilation is a different beast, but I haven’t written one of those for a pint time.

I have similar compiler history and employ similar practice.

Keep things where they logically belong - the parser is for mapping tokens onto syntax, for that it needs tokens! It doesn't matter if lexing is done in a separate pass, or "interleaved" in time. What matters is that the each "pass" is logically distinct.

Most languages are designed so that it's easy to produce tokens from text, without knowing where you are in the syntax tree - that makes it easy to read code fragments.

(There are languages where the same string can have very distinct structure & meaning depending on context. They tend to cause much swearing and confusion.)

You're quite right, I over-simplified -- mea culpa! That should have said "often unify these phases". FWIW, I've written recursive descent parsers with and without separate lexers, though my sense is that the majority opinion is that "recursive descent" implies "no separate lexer".

For what it's worth, in my little corner of the world, all of the recursive descent parsers I've seen and worked with have separate lexers. I can't recall seeing a single recursive descent parser in industry that didn't separate lexing.

However, I do often see a little fudging the two together for funny corners of the language. Often that just means handling ">>" as right-shift in some contexts and nested generics in others.

That's not my impression of the majority opinion, fwiw. (I wrote my first recursive-descent parser in the 80s and I learned from pretty standard sources like one of Wirth's textbooks.)

As another data point in addition to the sibling comments, all IntelliJ language parsers use recursive descent with a separate lexer.

I don’t think it’s an outlier, I do my lex phase before the parsing phase, it’s not concurrent. However, I find reporting bad tokens and parse errors to work well even if the phases are sequential.

I’ve only written lexing and parsing together in recursive descent parsers. What am I missing out on?

I believe the point being made is that while it is possible to merge lexing and parsing with recursive descent parser, it is not essential to this style, and separating lexing and parsing while doing recursive descent parser is also a legitimate approach.

Lexing separately is cleaner in that the lexer's only job is to produce tokens and then the parser's only job is to consume tokens and produce e.g. an AST. It also means that you can use that token stream for other things that don't require a full parse (e.g. for syntax highlighting). The disadvantage is that you're often doubling the allocations and increasing the memory footprint. I alternate between separate lexer, combined recursive descent parser and generated PEG parsers depending on what is more important: speed + maintainability, speed of execution or speed of development

If you don't think you're missing out, you're not. I think it could be preference.

I just prefer for a lexer to be responsible for handling characters, and a parser be responsible for handling tokens. So Single Responsibility Principle.

If you find the code wants factoring out (if you don't, just leave it be, parsers are wonderful things to have written but IME writing them is generally a labour of love) then that split tends to be very natural and works well in the vast majority of cases.

It's also worth having a poke around at some of the Racket community's Language Oriented Programming efforts, they usually have a split they call 'reader' versus 'expander' that I found helped me get my head around how the dividing line can be drawn and why you'd want to.

(Racket's approach isn't quite lexer vs. parser AFAICT but while I at least -think- I've understood it well enough to use ideas, I'm not going to pretend I understand it well enough to provide a correct explanation, let alone a well written one)

Can you expand on why you prefer that approach?

It's much easier to have a grammar that is LL(1) - which also makes recursive descent that much more convenient to write - if you separate.

Reply on news.ycombinator.com