4 ms·

The Unicode input alphabet is up to 4096 symbols. The Lexer's output alphabet (a set of tokens) which is an input for a Parser is up to a few tens of symbols a

The Unicode input alphabet is up to 4096 symbols. The Lexer's output alphabet (a set of tokens) which is an input for a Parser is up to a few tens of symbols at worst. The smaller alphabet the easier it is to make efficient recursive decent parser. Regular expressions are Finite-State Machines under the hood. There exist one single minimal deterministic FSM per any Regex. And that model is the best in performance. In contrast, for context-free grammars we don't have such unique computation model that would be best in performance. Because of this it is reasonable to separate a Regex-based part of the grammar (the Lexing part) and treat it independently. Also, when parsing, perhaps it would be easier to recover from input syntax errors from the Token-based input rather than Unicode-based input. Finally, my personal opinion is that if you write a recursive-descend parser manually, it would be really easier to reason about just the limited number of token classes rather than the entire Unicode alphabet.

arcticbull 3y ago
I used to feel similarly until I spent a bunch of time with nom [1]. There's not really any difference between tokens and grammar rules, in my experience. They're just terminal and non-terminal symbols yeah? Doing these things in one place doesn't get in the way of writing a nice LL recursive-descent parser. I'm sure it will depend on what you're doing but for me at least splitting into lex and parse has a much higher bar now. I've done it both ways many times and at least for my applications adding a separate lexer has historically been the wrong abstraction in retrospect. [1] https://blog.logrocket.com/parsing-in-rust-with-nom/ https://blog.logrocket.com/parsing-in-rust-with-nom/
- Eliah_Lakhin 3y ago
  Well, my personal experience was in the opposite direction actually. I used to use combinators-based approach without Lex/Syn separation (aka PEGs) for a long time. But then I came up to understanding that the separation approach is actually better in performance. And also that working and debugging of the Token sequences while writing parser manually is just more handy (at least for me). But this is my personal experience of course. I do believe too that it all depends on the goal, and parsers micro-optimizations is not that much critical in many cases, and that combinators approach actually works quite well too. As of Nom, I can say that it works quite well. But I think that the it's performance gains stem from the fact that Rust is a systems-based PL, and it optimizes function combinations just better than, let say, JavaScript or Python. In my incremental parsers library Lady Deirdre I utilize Lex/Syn separation, and the LL(1) recursive-descend parsing, and it shows much better performance than in Tree-Sitter at least on relatively big files [1]. [1] https://github.com/Eliah-Lakhin/lady-deirdre/tree/master/work/crates/examples#results https://github.com/Eliah-Lakhin/lady-deirdre/tree/master/wor...
vlovich123 3y ago
> easier to recover from input syntax errors from the Token-based input rather than Unicode-based input Rust has pretty exact mapping from syntax errors to lexical placement. Couldn't a similar approach be used if you have a potential recovery path?
- Eliah_Lakhin 3y ago
  I think it depends on how the recovery path is made. During the lexical scanning stage you can persist the token's source code sites, and later reuse them to indicate syntax or similar errors. For example, in Rust when you parse the syntax from the TokenStream of a procedural macro input, you can bind custom errors to any spans of input tokens, and it works just fine.
jwilk 3y ago
> The Unicode input alphabet is up to 4096 symbols. Huh? How did you come up with this number?
- Eliah_Lakhin 3y ago
  ah, I apologize for misdirection. In general it could be much bigger of course. Wikipedia[1] says Utf-8 can encode up to 1,112,064. Anyway, it is quite big "alphabet" than the usual set of Lexis Tokens :) [1] https://en.wikipedia.org/wiki/UTF-8 https://en.wikipedia.org/wiki/UTF-8

arcticbull 3y ago

I used to feel similarly until I spent a bunch of time with nom [1]. There's not really any difference between tokens and grammar rules, in my experience. They're just terminal and non-terminal symbols yeah? Doing these things in one place doesn't get in the way of writing a nice LL recursive-descent parser. I'm sure it will depend on what you're doing but for me at least splitting into lex and parse has a much higher bar now. I've done it both ways many times and at least for my applications adding a separate lexer has historically been the wrong abstraction in retrospect. [1] https://blog.logrocket.com/parsing-in-rust-with-nom/ https://blog.logrocket.com/parsing-in-rust-with-nom/

Eliah_Lakhin 3y ago
Well, my personal experience was in the opposite direction actually. I used to use combinators-based approach without Lex/Syn separation (aka PEGs) for a long time. But then I came up to understanding that the separation approach is actually better in performance. And also that working and debugging of the Token sequences while writing parser manually is just more handy (at least for me). But this is my personal experience of course. I do believe too that it all depends on the goal, and parsers micro-optimizations is not that much critical in many cases, and that combinators approach actually works quite well too. As of Nom, I can say that it works quite well. But I think that the it's performance gains stem from the fact that Rust is a systems-based PL, and it optimizes function combinations just better than, let say, JavaScript or Python. In my incremental parsers library Lady Deirdre I utilize Lex/Syn separation, and the LL(1) recursive-descend parsing, and it shows much better performance than in Tree-Sitter at least on relatively big files [1]. [1] https://github.com/Eliah-Lakhin/lady-deirdre/tree/master/work/crates/examples#results https://github.com/Eliah-Lakhin/lady-deirdre/tree/master/wor...

vlovich123 3y ago

> easier to recover from input syntax errors from the Token-based input rather than Unicode-based input Rust has pretty exact mapping from syntax errors to lexical placement. Couldn't a similar approach be used if you have a potential recovery path?

Eliah_Lakhin 3y ago
I think it depends on how the recovery path is made. During the lexical scanning stage you can persist the token's source code sites, and later reuse them to indicate syntax or similar errors. For example, in Rust when you parse the syntax from the TokenStream of a procedural macro input, you can bind custom errors to any spans of input tokens, and it works just fine.

jwilk 3y ago

> The Unicode input alphabet is up to 4096 symbols. Huh? How did you come up with this number?

Eliah_Lakhin 3y ago
ah, I apologize for misdirection. In general it could be much bigger of course. Wikipedia[1] says Utf-8 can encode up to 1,112,064. Anyway, it is quite big "alphabet" than the usual set of Lexis Tokens :) [1] https://en.wikipedia.org/wiki/UTF-8 https://en.wikipedia.org/wiki/UTF-8