Source
Batman_AoD•

Because there is only one lifetime in both the input and output types, it can be inferred:

fn tokenize(code: &str) -> impl Iterator<Item=&str>

Trivial working example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=015cba05a28e361b61f1fce7ac518b92

63
TheIncorrigible1•

The term is lifetime elision

38
raugturi•

I think Mr. Mister has a song about that.

3
paulduncanidaho•

I think, in this case, including it in the post was smart because it made it very explicit that the two lifetimes are connected, which seems like the whole point of the second half of the post

11
cybergaiato•

Isn't that the default? Without the lifetime you know that's the case, otherwise there would be compiler errors.

3
shponglespore•

While the main points of the article still hold up, I don't think the actual signature is realistic for a tokenizer, because it provides no way to indicate whether the whole input was actually tokenized. Real tokenization functions I've seen do this by also returning the index of the last tokenized byte, which allows tokenizing functions to be composed easily. You can't return something like a pair or Result, because you don't know how much of the input has been consumed until the iterator has been consumed. There are a number of ways to deal with this:

  • Return a concrete iterator type with a method to get the number of bytes consumed.
  • Create a new trait with the necessary method.
  • Have the caller track the total length of the tokens returned.
  • Have the caller use pointer arithmetic to find where the last returned token lies in the input string.
  • Wrap the tokens in a struct that contains their offset in the input string.

I think the last option is probably best, because most real tokenizers will want to use a struct anyway, and it maintains the nice properties the article talks about. To make it fully realistic, the tokenizer function should take a start offset where it will start tokenizing. Just passing a str slice doesn't allow composition of tokenizing functions, because you want the token offsets to be in terms of the whole input, not just the slice passed to a sub-tokenizer.

There's also the issue of reporting errors to the user, which you'll usually want to be in terms of lines and columns. You probably want to do this by making a second pass over the input to convert offsets to lines and columns. The overhead of this extra pass doesn't matter, because it's only needed for invalid inputs.

Lastly, there's a hidden assumption here, which is that the whole input is available when tokenization starts. That won't be the case if, for example, you're trying to parse a stream incrementally. At that point, you probably need to abandon using off-the-shelf types and traits, and build something more specialized to deal with issues like buffering enough of the input to backtrack as much as necessary.

EDIT: Ok, one more thing. If you want to be excruciatingly stingy with memory, the returned token structs shouldn't contain slices of original string, because it's redundant. You're already saving the start offset, so you just need to save the length or end offset as well. You're still using references (of a sort) to the original string, just not tracked by the compiler. To make the compiler enforce lifetime constraints for you, give the token struct a lifetime parameter referring to the original string, and include a PhantomData member that uses the lifetime, because without it the compiler will complain that the lifetime parameter isn't used.

41
gendulf•

Real tokenization functions I've seen do this by also returning the index of the last tokenized byte, which allows tokenizing functions to be composed easily. You can't return something like a pair or Result, because you don't know how much of the input has been consumed until the iterator has been consumed.

I think this misses the point. The article is demonstrating that the "complete" tokenization of the can be interweaved with the parser because the Iterator is lazy. Inside this tokenize function you can certainly do partial tokenization in stages (including details like last byte, etc). However, if you want to know the "remainder" of the input, then you have to tokenize until you're done (or reach an error), forcing completion of anything lazy.

I agree it's not composable, but I think in this case, this article is written from the high level where the parser is interacting with a tokenizer (and this would be the interface). I don't think the parser would need to know this information, but maybe that's me missing your point. :)

12
shponglespore•

I wasn't trying to critique the article, just expand on it. I happen to have been tinkering with a tokenizer in Rust very recently so it was on my mind.

6
[deleted]•

+1 for linking a concrete example to PhantomData which makes its use case clearer in my mind. Thanks!

5
[deleted]•

it provides no way to indicate whether the whole input was actually tokenized.

Wouldn't that just safely be assumed if the iterator returns None? If so, the problem would be that the tokenizer has no way to indicate failure.

2
shponglespore•

No, because the iterator will always return None at some point. If it returns None the first time you call next, you know there's a problem at the start of the input, but if it produces any tokens, you need some way to know if there are more characters after the last valid token.

1
[deleted]•

[deleted]

1
thunderseethe•

For the edit what's the advantage of storing offsets vs a slice memory wise? It sounds like either way you're storing two words.

1
shponglespore•

A &str is two words but it doesn't tell you where the token starts relative to the original string. I guess it's really just a matter of what you want to make convenient. There are two important things you need to be able to find for each token: its content (a &str, two words), and its offset in the input (a usize). But you only need to actually store two words per token if you assume the original input string will always be available from the stack or another data structure when you need it, so there are two cases depending on what you want to store in the token itself:

  1. If you store just the &str, you need the original input only when you need to compete the token's start offset, and computing the offset requires a little bit of pointer arithmetic.

  2. If you store start and end offsets, you need the original input only when you need to find token's content, and computing the content requires taking a slice of the original input.

Of the two options, I prefer the second because I think pointer arithmetic is ugly compared to slicing. The second option also lets you store the length in less than a full word if you really want to, since you could restrict the maximum length of a single token to fit in a u8 or u16 and probably nobody would ever notice. Even the start offset could be a u16 or u32 for any realistic input, so you could conceivably store everything you need in a single word with room left over for something like a category tag, which is another thing most real tokenizers need to report for each token.

1
giorgiga•

TL;DR fn tokenize<'a>(code: &'a str) -> impl Iterator<Item=&'a str> because of Iterator being lazy and lifetime.

36
gendulf•

Specifically that it splits a normally two pass operation (inefficient but clean code) or one pass operation (efficient, but messy code) into getting the best of both worlds plus safety (first pass is written in a clean way and done lazily, and it's efficient due to optimizations that can be made).

16
giorgiga•

That's a 100% moot point: it may indicate that the article's author has never written a "clean code" 1-pass parser, but it doesn't mean that it can't be written without an Iterator.

It must be also said that Iterator alone does not support look-ahead and that, depending on what language one is parsing, that functionality may very well be needed in a parser.

2†
po8•

If you only need one token of lookahead, which is typical, you can use std::iter::Peekable instead of Iterator. If you need arbitrary lookahead, you can drop a std::collections::VecDeque in there somewhere — in the unusual case that you need to inspect the queue state make_contiguous() is on nightly right now.

11
sheepshapesoap•

Why VecDeque instead of Vec?

1
[deleted]•

[removed]

-25
gendulf•

The author may be lacking experience or understanding (I'm not judging here). I just felt that I understood your TL;DR, but it left out too much context, and wanted to provide that here.

4
TomorrowPlusX•

I just finished a Rust port (this morning!) of the Lox interpreter from Bob Nystrom's Crafting Interpreters. I'm pretty happy with it, because as a Rust newbie it's the first non-trivial thing I've written in it.

https://github.com/ShamylZakariya/CraftingInterpreters/tree/master/rlox

One of my notes for improvement is exactly this - my scanner/tokenizer returns a list of tokens which have copies from the input string, and I've planned to fix it by passing tokens with string references in them.

This is a fun read, but I've got a LONG way to go before I'm writing properly idiomatic Rust.

10
cat_in_the_wall•

Same. Im a rust noob, and i started by writing a tokenizer and parser for a toy language and was so stuck on proper lifetimes i never got anything done. eventually i gave up and just copied everything, made progress, then unsurprisingly i actually learned, and was able to go back and clean up a bunch of those copies (maybe 80%?).

I'm a perfectionist so this has been a hard pill for me to swallow: do it the easy way first, then learn, refine, repeat. probably not going to get it 100% on your first go.

6
addmoreice•

Personally, I think of programming the same way I think about writing. Get something down, get it roughly going where you want, find out of the big overarching stuff work together, then go back and edit.

Starting from a blank page is hard, the same way starting with an empty main is hard. But get the core bit working and flesh it out, structure it correctly, and where things need work/can be expanded is obvious.

3
edujtm•

I'm kinda of a beginner in Rust and I've been thinking about doing the same thing. Do you think the book is appropriate for someone who has no compiler background?

I've read the rust book and I'm currently reading programming rust. I've also studied automatas before, so I do have a bit of a background. I'm not sure if I should read a compiler theory book before the Bob Nystrom's one.

2
TomorrowPlusX•

I don't have any compiler background at all - I did the book in its default Java and C implementations a year or so ago as an intro to interpreters, compilers, etc. So when approaching it in Rust, I was already familiar with the design of the interpreter.

That being said, I only started learning Rust a few months ago (via the standard Rust book, like everybody does), and was able to get this working in maybe 5 or 6 weeks of occasional evening "homework".

I'm going to give a stab at implementing a simple platformer (going to "remake" Gargoyle's Quest from Gameboy) in Amethyst next, as an opportunity to learn a different kind of Rust programming. Maybe after that I'll give a stab at something embedded.

Anyway Rust has sold me now for my personal projects, even if I have to write c++ all day for work :)

5
Plazmotech•

God I love this language

1