Rasheed Starlet (May 02 2024 at 16:31): Rasheed Starlet (May 02 2024 at 16:31):The Roc compiler has no scanner? Scanning and Parsing are done in the Parser?
Brendan Hansknecht (May 02 2024 at 21:02):scanner == lexer?
Brendan Hansknecht (May 02 2024 at 21:03):And yeah, roc uses parser combinators to go from source to first level ast.
Rasheed Starlet (May 02 2024 at 23:26):Yes sir. So that is like the Syntax-Directed Translation pattern?
Richard Feldman (May 02 2024 at 23:42):I'm not familiar with that term, but it's basically just that we have a function that goes directly from bytes in the file to an Abstract Syntax Tree
Richard Feldman (May 02 2024 at 23:43):there's no intermediate structure like a "token" or anything like that
Richard Feldman (May 02 2024 at 23:43):although @Joshua Warner and I have talked about wanting to rewrite the parser in a way which uses the more traditional approach, for various reasons :big_smile:
Richard Feldman (May 02 2024 at 23:45):the reason it works the way it does today is that when I started working on the compiler, parser combinators were the only technique I knew for parsing (from my experience using elm/parser) and Bodil Stokke wrote a post about how to do parser combinators in Rust, so I followed that to get started...and now several years later it's still how our parser is written :laughing:
Rasheed Starlet (May 02 2024 at 23:50):Hah! My first exposure to parser combinators was Bodil’s article.
Yesterday when I was reading the roc parser, I was going like wait, I know this, I know that and this :joy::joy:
Joshua Warner (May 03 2024 at 03:57):Huh, I've never heard of Syntax-Directed Translation before...
Joshua Warner (May 03 2024 at 03:59):If I'm reading the wikipedia page right, SDT is a fairly extreme compiler construction method, if taken literally.
Joshua Warner (May 03 2024 at 04:00):It's like the lex/yacc examples that show you how to do an expression evaluator in the yacc grammar. i.e. it doesn't build up an AST and evaluate it - it does the evaluation in the parser!
Rasheed Starlet (May 03 2024 at 04:00):New to these stuff. Just reading around.
Joshua Warner (May 03 2024 at 04:01):I could imagine stretching the definition a bit and just considering "doing extra steps in the parser" to be SDT
Joshua Warner (May 03 2024 at 04:02):e.g. in GCC I think for a long time there was a simple constant evaluator done very very early in the compiler, possibly directly in the parser (I'm like 95% speculating here, don't quote me)
Joshua Warner (May 03 2024 at 04:03):In Roc, one might imagine trying to do desugaring, canonicalization, name resolution, etc - all as part of the parser.
Joshua Warner (May 03 2024 at 04:05):One disadvantage then is that it's hard to have a parser that can accept fragments of code and parse them into something sensible - which can be useful for things like auto-formatting code that doesn't compile yet, or better syntax highlighting, etc.
Joshua Warner (May 03 2024 at 04:05):Or at least, you'd have to have two separate parsers - one for tooling and one for the production compiler.
Joshua Warner (May 03 2024 at 04:06)::thinking: I wonder if the compiler could be faster if you cram everything into as few stages as possible?
Definitely harder to maintain, but maybe that could be overcome with tooling or generics
Rasheed Starlet (May 03 2024 at 04:08):Looks like a shortcut that will come with a lotta gotcha’s down the line
Joshua Warner (May 03 2024 at 04:13):Definitely need to embark on that... carefully.
Joshua Warner (May 03 2024 at 04:13):I don't know that I would immediately reject it as "impossible to do well"
Joshua Warner (May 03 2024 at 04:14):But it's also not obvious how one would do it well.
Last updated: Jul 05 2025 at 12:14 UTC