11 ms·
Rust for tokenising and parsing
- tptacek 2y agoSo, just to kick this off: I wrote an eBPF disassembler and (half-hearted) emulator in Rust and I also found it a pleasant language to do parsing-type stuff in. But: I think the author cuts against their argument when they manage to necessitate a macro less than 1/6th of the way into their case study. A macro isn't quite code-gen, but it also doesn't quite feel like working idiomatically within the language, either. Again: not throwing shade. I think this is a place where Rust is genuinely quite strong.
- deleted 2y ago[deleted]
- jamra 2y agoLink us your eBPF disassembler if you can. Sounds cool.
- tptacek 2y agoIt's not. If you wrote one, it'd be more interesting than mine.
- thesz 2y agoHow can one define an infinite grammar in Rust? E.g., a context-free rule S ::= abc|aabbcc|aaabbbccc|... can effectively parse a^Nb^Nc^N which is an example of context-sensitive grammar. This is a simple example, but something like that can be seen in practice. One example is when language allows definition of operators. So, how does Rust handle that?
- ryandv 2y agoIn Haskell I think it's something like: {-# LANGUAGE OverloadedStrings #-} import Data.Attoparsec.Text import qualified Data.Text as T type ParseError = String csgParse :: T.Text -> Either ParseError Int csgParse = eitherResult . parse parser where parser = do as <- many' $ char 'a' let n = length as count n $ char 'b' count n $ char 'c' char '\n' return n ghci> csgParse "aaabbbccc\n" Right 3
- thesz 2y agoThe question comes from Haskell, yes: https://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ https://byorgey.wordpress.com/2012/01/05/parsing-context-sen... You used monadic parser, monadic parsers are known to be able to parse context-sensitive grammars. But, they hide the fact that they are combiinators, implemented with closures beneath them. For example, that "count n $ char 'b'" can be as complex as parsing a set of statements containing expressions with an operator specified (symbol, fixity, precedence) earlier in code. In Haskell, it is easy - parameterize your expression grammar with operators, apply them, parse text. This will work even with Applicative parsers, even unextended. But in Rust? I haven't seen how it can be done.
- ryandv 2y agoI tried winnow as suggested elsewhere in this thread, this is what it may look like: use winnow::combinator::{ repeat }; use winnow::token::take_while; use winnow::prelude::*; pub fn csg_parse(input: &mut &str) -> PResult<usize> { let a: &str = take_while(0.., 'a').parse_next(input)?; let n: usize = a.len(); repeat(n, "b").parse_next(input)?; repeat(n, "c").parse_next(input)?; '\n'.parse_next(input)?; return Ok(n); } #[cfg(test)] mod test { use super::*; #[test] fn parses_examples() { assert_eq!(Ok(0), csg_parse(&mut "\n")); assert_eq!(Ok(3), csg_parse(&mut "aaabbbccc\n")); assert!(csg_parse(&mut "abcc\n").is_err()); assert!(csg_parse(&mut "abbcc\n").is_err()); assert!(csg_parse(&mut "aabc\n").is_err()); assert!(csg_parse(&mut "aabbc\n").is_err()); assert!(csg_parse(&mut "def\n").is_err()); } }
- thesz 2y agoSo you are directly express context-sensitivity instead of approximating it with infinite context-free grammar. Okay, good enough.
- jeroenhd 2y agoUsing parser combinator library "nom", this should probably do what you'd want: fn parse_abc(input: &str, n: usize) -> IResult<&str, (Vec<char>, Vec<char>, Vec<char>)> { let (input, result) = tuple(( many_m_n(n, n, char('a')), many_m_n(n, n, char('b')), many_m_n(n, n, char('c')) ))(input)?; Ok((input, result)) } It parses (the beginning of) the input, ensuring `n` repetitions of 'a', 'b', and 'c'. Parse errors are reported through the return type, and the remaining characters are returned for the application to deal with as it sees fit. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c641c407591e1eb7ce451f5865250f56 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- oguz-ismail 2y ago> this should probably do what you'd want If you have to specify N, no, it doesn't
- hu3 2y agoRelated, I love Rob Pike's talk about lexical Scanning in Go (2011). Educational and elegant approach. https://www.youtube.com/watch?v=HxaD_trXwRE https://www.youtube.com/watch?v=HxaD_trXwRE
- emmanueloga_ 2y agoThat talk is great, but I remember some discussion later about Go actually NOT using this technique because of goroutine scheduling overhead and/or inefficient memory allocation patterns? The best discussion I could find is [1]. Another great talk about making efficient lexers and parsers is Andrew Kelley's "Practical Data Oriented Design" [2]. Summary: "it explains various strategies one can use to reduce memory footprint of programs while also making the program cache friendly which increase throughput". -- 1: https://news.ycombinator.com/item?id=31649617 https://news.ycombinator.com/item?id=31649617 2: https://www.youtube.com/watch?v=IroPQ150F6c https://www.youtube.com/watch?v=IroPQ150F6c
- chubot 2y agoYeah I actually remember that too, this article mentions it: Coroutines for Go - https://research.swtch.com/coro https://research.swtch.com/coro The parallelism provided by the goroutines caused races and eventually led to abandoning the design in favor of the lexer storing state in an object, which was a more faithful simulation of a coroutine. Proper coroutines would have avoided the races and been more efficient than goroutines.
- tptacek 2y agoI feel like that talk has more to do with expressing concurrency, in problems where concurrency is a natural thing to think about, than it does with lexing.
- jamra 2y agoDoes anyone have a good EBNF notation for Sqlite? I tried to make a tree-sitter grammar, which produces C code and great Rust bindings for it. But they use some lemon parser. Not sure how to read the grammar from that.
- deleted 2y ago[deleted]
- andrewflnr 2y agoIt looks pretty much like BNF. Not too far off, anyway. https://sqlite.org/src/doc/trunk/doc/lemon.html#syntax https://sqlite.org/src/doc/trunk/doc/lemon.html#syntax
- rstuart4133 2y agoNot EBNF or anything standard, but possibly readable enough. It is an LR(1) grammar that has tested on all the test cases in Sqlite's test suite at the time: https://lrparsing.sourceforge.net/doc/examples/lrparsing-sqlite.py https://lrparsing.sourceforge.net/doc/examples/lrparsing-sql... The grammer contains things you won't have seen before, like Prio(). Think of them as macros. It all gets translated to LR(1) productions which you can ask it to print out. LR(1) productions are simpler than EBNF. They look like: symbol1 := symbol2 symbol3 symbol1 := symbol4 symbol3 symbol3 := token1 symbol2 token2 ... Documentation on what the macros do, and how to get it to spit out the LR1(1) productions is here: https://lrparsing.sourceforge.net/doc/html/ https://lrparsing.sourceforge.net/doc/html/ It was used to do a similar task the OP is attempting.
- jamra 2y agoThis is great. Do you have any pointers to where those tests are? It’s hard to test the grammar without those. Edit: Never mind. I see it right there under the parser. Thanks!
- emmanueloga_ 2y agoPerhaps this ANTLR v4 sqlite grammar? [1] -- 1: https://github.com/antlr/grammars-v4/tree/master/sql/sqlite https://github.com/antlr/grammars-v4/tree/master/sql/sqlite
- sksxihve 2y agoI've found that the logos crate is really nice for writing lexers in rust https://docs.rs/logos/0.14.2/logos/ https://docs.rs/logos/0.14.2/logos/
- WiSaGaN 2y agoI think except macros, most of these features are ML family language features as well. Rust stands out because it can implement this in an efficient, zero overhead abstraction way.
- kldx 2y agoI like MegaParsec in haskell quite expressive, based on my limited experience using nom in Rust
- ketzo 2y agoSo how do you debug code written with macros like this, or come into it as a new user of the codebase? I’m imagining seeing the node! macro used, and seeing the macro definition, but still having a tough time knowing exactly what code is produced. Do I just use the Example and see what type hints I get from it? Can I hover over it in my IDE and see an expanded version? Do I need to reference the compiled code to be sure? (I do all my work in JS/TS so I don’t touch any macros; just curious about the workflow here!)
- schneems 2y agoRun: $ cargo expand And you’ll see the resulting code. Rust is really several languages, ”vanilla” rust, declarative macros and proc macros. Each have a slightly different capability set and different dialect. You get used to working with each in turn over time. Also unit tests is generally a good playground area to understand the impacts of modifying a macro.
- guitarbill 2y agorust-analyzer, the Rust LSP used in e.g. VSCode, can expand declarative and proc macros recursively. it isn't too bad, although the fewer proc macros in a code base, the better. declarative macros are slightly easier to grok, but much easier to maintain and test. (i feel the same way about opaque codegen in other languages.)
- ryandv 2y agoI don't know. Having written a small parser [0] for Forsyth-Edwards chess notation [1] Haskell takes the cake here in terms of simplicity and legibility; it reads almost as clearly as BNF, and there is very little technical ceremony involved, letting you focus on the actual grammar of whatever it is you are trying to parse. [0] https://github.com/ryandv/chesskell/blob/master/src/Chess/FastFenParser.hs https://github.com/ryandv/chesskell/blob/master/src/Chess/Fa... [1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...
- nine_k 2y agoBut this is not unaided Haskell, it's a parser combinator library, isn't it? Do you see an obvious reason why a similar approach won't work in Rust? E.g. winnow [1] seems to offer declarative enough style, and there are several more parser combinator libraries in Rust. [1]: https://docs.rs/winnow/latest/winnow/ https://docs.rs/winnow/latest/winnow/
- codebje 2y agodata Color = Color { r :: Word8 , b :: Word8 , c :: Word8 } deriving Show hex_primary :: Parser Word8 hex_primary = toWord8 <$> sat isHexDigit <*> sat isHexDigit where toWord8 a b = read ['0', 'x', a, b] hex_color :: Parser Color hex_color = do _ <- char '#' Color <$> hex_primary <*> hex_primary <*> hex_primary Sure, it works in Rust, but it's a pretty far cry from being as simple or legible - there's a lot of extra boilerplate in the Rust.
- jeroenhd 2y agoI think it's a stretch to call parser combinator code in Haskell simple or legible. Most Haskell code is simple and legible if you know enough Haskell to read it, but Haskell isn't exactly a simple or legible language. Haskell demonstrates the use of parser combinators very well, but I'd still use parser combinators in another language. Parser combinators are implemented in plenty of languages, including Rust, and actually doing anything with the parsed output becomes a lot easier once you leave the Haskell domain.
- brundolf 2y agoSomething that was hard when I wrote a full AST parser in Rust was representing a hierarchy of concrete AST types, with upcasting and downcasting. I was able to figure out a way, but it required some really weird type shenanigans (eg PhantomData) and some macros. Looks like they had to do crazy macros here too Curious what the rest of the prior art looks like
- elcritch 2y agoHmmm, yeah Rust’s ADTs and matching syntax would be great. Until you got to the up/down casting. I’m inexperienced enough in Rust to know if there’s good ways to handle it. Dynamic traits maybe?
- ainiriand 2y agoSorry to bother you, but would that be open-source by any chance? Is there any public repo available? Thank you.
- yu3zhou4 2y agoMaybe it can work as a quick glimpse into how parser and lexer can work in Rust https://github.com/jmaczan/0x6b73746b https://github.com/jmaczan/0x6b73746b I wrote it long time ago and it’s not fully implemented tho
- norman784 2y agoI wrote my fairly share of parsers the last year, and the one I liked a lot is from Salsa examples, you can find it here[0]. [0] https://github.com/salsa-rs/salsa/blob/e4d36daf2dc4a096009753b6e326cf44e6c6e18a/examples/calc/parser.rs https://github.com/salsa-rs/salsa/blob/e4d36daf2dc4a09600975...
- brundolf 2y agoYup! You can find it here: https://github.com/brundonsmith/bagel-rs/blob/master/src/model/ast.rs https://github.com/brundonsmith/bagel-rs/blob/master/src/mod... [trying to remind myself how this works because it's been a while] So it's got macros for defining "union types", which combine a bunch of individual structs into an enum with same-name variants, and implement From and TryFrom to box/unbox the structs in their group's enum ASTInner is a struct that holds the Any (all possible AST nodes) enum in its `details` field, alongside some other info we want all AST nodes to have And then AST<TKind> is a struct that holds (1) an RC<ASTInner>, and (2) a PhantomData<TKind>, where TKind is the (hierarchical) type of AST struct that it's known to contain AST<TKind> can then be: 1. Downcast to a TKind (basically just unboxing it) 2. Upcast to an AST<Any> 3. Recast to a different AST<TKind> (changing the box's PhantomData type but not actually transforming the value). This uses trait implementations (implemented by the macros) to automatically know which parent types it can be "upwardly casted to", and which more-specific types it can try and be casted to The above three methods also have try_ versions What this means then is you can write functions against, eg, AST<Expression>. You will have to pass an AST<Expression>, but eg. an AST<BooleanLiteral> can be infallibly recast to an AST<Expression>, but an AST<Any> can only try_recast to AST<Expression> (returning an Option<AST<Expression>>) Another cool property of this is that there are no dynamic traits, and the only heap pointers are the Rc's between AST nodes (and at the root node). Everything else is enums and concrete structs; the re-casting happens solely with that PhantomType, at the type level, without actually changing any data or even cloning the Rc unless you unbox the details (in downcast()) I worked in this codebase for a while and the dev experience was actually quite nice once I got all this set up. But figuring it out in the first place was a nightmare I'm wondering now if it would be possible/worthwhile to extract it into a crate
- omani 2y agothis is the third day in a row this article is being posted here. this time it got traction. funny how HN works. https://news.ycombinator.com/item?id=42055954 https://news.ycombinator.com/item?id=42055954 https://news.ycombinator.com/item?id=42058920 https://news.ycombinator.com/item?id=42058920
- noelwelsh 2y agoThis is, to me, an odd way to approach parsing. I get the impression the author is relatively inexperienced with Rust and the PL ideas it builds on. A few notes: * The AST would, I believe, be much simpler defined as an algebraic data types. It's not like the sqlite grammar is going to randomly grow new nodes that requires the extensibility their convoluted encoding requires. The encoding they uses looks like what someone familiar with OO, but not algebraic data types, would come up with. * "Macros work different in most languages. However they are used for mostly the same reasons: code deduplication and less repetition." That could be said for any abstraction mechanism. E.g. functions. The defining features of macros is they run at compile-time. * The work on parser combinators would be a good place to start to see how to structure parsing in a clean way.
- huijzer 2y ago> I get the impression the author is relatively inexperienced The author never claimed to be an experienced programmer. The title of the blog is "Why I love ...". Your notes look fair to me, but calling out inexperience is unnecessary IMO. I love it if someone loves programming. I think that's great. Experience will come.
- guappa 2y agoIf someone didn't study the state of the art of tokenising and parsing and still wants to write about it, it's absolutely ok to call it out as being written by someone who has only a vague idea of what they're talking about.
- palata 2y ago> calling out inexperience is unnecessary IMO I don't know the author, so it's useful for me to see in the comments that some people think they are not so experienced. Doesn't mean I won't respect the author at all, it's great that they write about what they do!
- robertlagrant 2y ago"calling out" is too fuzzy a term to be useful. It covers "mentioning" and "accusing". I wouldn't use it, for that reason. "unnecessary" is the same. Who defines what's necessary? Is Hacker News necessary?
- jurschreuder 2y agoI cannot agree less, C++ is the best and always will be. You youngsters made up this new dialect that can also compile with the C++ compiler. This is like people putting VS Code in dark mode thinking they're now also working in the Terminal like the Gods of Binary.
- arlort 2y agoRust being a dialect of c++ is certainly a novel take
- tialaramex 2y agoI expect they are thinking of the "Safe C++" proposal P3390. This proposes to provide the syntax and other features needed to grant (a subset of the future) C++ the same safety properties as safe Rust via an equivalent mechanism (a borrow checker for C++ and the lifetime annotations to drive it, the destructive move, the nominative typing and so on). Much as you might anticipate (although perhaps its designer Sean Baxter did not) this was not kindly looked upon by many C++ programmers and members of WG21 (the C++ committee) The larger thing that "Safe C++" and the reaction to it misses is that Rust's boon is its Culture. The "Safe C++" proposal gives C++ a potential safety technology but does not and cannot gift it the accompanying Safety Culture. Government programmes to demand safety will be most effective - just as with other types of safety - if they deliver an improved culture not just technological change.
- whytevuhuni 2y agoThat sounds significantly more like C++ trying to be a dialect of Rust, rather than the other way around. I don't think that was the GGP's main gripe. But more importantly, Safe C++ is just not a thing yet. People seem to discount the herculean effort that was required to properly implement the borrow checker, the thousands of little problems that needed to be solved for it to be sound, not to mention a few really, really hard problems, like variance, lifetimes in higher-kinded trait bounds, generic associated types, and how lifetimes interact with a Hindley-Milner type system in general. Not trying to discount Safe C++'s efforts of course. I really hope they, too, succeed. I also hope they manage to find a syntax that's less... what it is now.
- gritzko 2y agoI have the experience of writing parsers (lexers) in Ragel, using Go, Java C++, and C. I must say, once you have some boilerplate generator in place, raw C is as good as the Rust code the author describes. Maybe even better because simplicity. For example, this is the most of code necessary to have a JSON parser: https://github.com/gritzko/librdx/blob/master/JSON.lex https://github.com/gritzko/librdx/blob/master/JSON.lex In fact, that eBNF only produces the lexer. The parser part is not that impressive either, 120 LoC and quite repetitive https://github.com/gritzko/librdx/blob/master/JSON.c https://github.com/gritzko/librdx/blob/master/JSON.c So, I believe, a parser infrastructure evolves till it only needs eBNF to make a parser. That is the saturation point.
- dvdkon 2y agoThat repetitivness can be seen as a downside, not a virtue. And I feel that Rust's ADTs make working with the resulting syntax tree much easier. Though I agree that a little code generation and/or macro magic can make C significantly more workable.
- djoldman 2y agoI love love love ragel. Won't the code here: https://github.com/gritzko/librdx/blob/master/JSON.lex https://github.com/gritzko/librdx/blob/master/JSON.lex accept "[" as valid json? delimiter = OpenObject | CloseObject | OpenArray | CloseArray | Comma | Colon; primitive = Number | String | Literal; JSON = ws* ( primitive? ( ws* delimiter ws* primitive? )* ) ws*; Root = JSON; (pick zero of everything in JSON except one delimiter...) I usually begin with the RFCs: https://datatracker.ietf.org/doc/html/rfc4627#autoid-3 https://datatracker.ietf.org/doc/html/rfc4627#autoid-3 I'm not sure one can implement JSON with ragel... I believe ragel can only handle regular languages and JSON is context free.
- gritzko 2y agoThat is a lexer, so yes, it accepts almost any sequence of valid tokens. Pure Ragel only parses regular languages, but there are ways.
- pornel 2y ago
- ForHackernews 2y agoI'll throw in a plug for https://pest.rs/ https://pest.rs/ a PEG-based parser-generator library in Rust. Delightful to work with and removes so much of the boilerplate involved in a parser.
- tda 2y agoI have been using this tool. The best feature imho is that you can quickly iterate on the grammar in the browser using the online editor in the homepage. I was struggling though with the lack of strong typing in the returned parse tree, though I think some improvements have beenade there which I did not have a chance to look into yet
- ForHackernews 2y agoThat feature is on the roadmap for Pest 3: https://github.com/pest-parser/pest/issues/882 https://github.com/pest-parser/pest/issues/882
- miningape 2y agoAbout 2 months ago I would have said the same as the author, but I kept running against the hard edges of Rust: the borrow checker. I realised that while I really liked using algebraic data types (e.g. Enums) and pattern matching, the borrow checker and the low level memory concerns meant I spent a lot of time fighting the borrow checker instead of fighting the PL issues at the heart of my project. So while tokenising/parsing was nice, interpreting and typechecking became the bane of my existence With that realisation I started looking for another more suitable language - I knew the FP aspects of Rust are what I was looking for so at first I considered something like F# but I didn't like that it's tied to microsoft/.NET. Looking a bit further I could have gone with something like Zig/C but then I lose the FP niceness I'm looking for. I also spent a fair amount of time looking at Go, but eventually decided that 1. I wanted a fair amount of syntax sugar, and 2. golang is a server side language, a lot of its features and library are geared towards this use case. Finally I found OCaml, what really convinced me was seeing the syntax was like a friendly version of Haskell, or like Rust without lifetimes. In fact the first Rust compiler was written in OCaml, and OCaml is well known in the programming language space. I'm still learning OCaml so I'm not sure I can give a fair review yet, but so far it's exactly what I was looking for.
- ralegh 2y agoI wouldn't call Go a 'server side' language. The Go compiler is written in Go, for example! Cross compilation and (relatively) small binaries make it super easy for distribution. Syntax sugar is a fair point though, it doesn't lend itself to functional-y pattern matching.
- miningape 2y agoWell now I've got to go check out the go compiler! That sounds really interesting. I was mainly referring to go having a lot more developed concurrency features, which while they're great I didn't really want to use them for my toy language, it seemed like I was throwing away a lot of what makes golang great just because of the nature of my project. The rest of the golang ecosystem I found really nice actually, and imo it had a really great set of tools for reading/writing to files - and also I like that everything is apart of the go binary, it certainly is easier than juggling between opam and dune (used for OCaml for example).
- nhatcher 2y agoWell good luck parsing sqlite syntax! I had to write a (fairly small) subset sqlite parser for work a couple of years ago. I really like sqlite, it's always a source of inspiration. The railroad diagrams are tremendously useful: https://www.sqlite.org/syntaxdiagrams.html https://www.sqlite.org/syntaxdiagrams.html I don't think the lemon parser generator gets enough credit: https://sqlite.org/src/doc/trunk/doc/lemon.html https://sqlite.org/src/doc/trunk/doc/lemon.html With respect of the choice of the language, any language with Algebraic Data Types would work great. Even Typescript would be great for this. FWIW I wrote a small introduction to writing parsers by hand in Rust a while ago: https://www.nhatcher.com/post/a-rustic-invitation-to-parsing/ https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...
- James_K 2y agoMentioning macros as a reason to love Rust goes against my experience with them.
- tonyhart7 2y agoI love using macros, writing it however
- sshine 2y agoOne mind-blowing experience for me: I can take my parser combinator library that I use for high-level compiler parsers, and use that same library in a no-std setting and compile it to a micro-controller, and deploy that as a high-performance protocol parser in an embedded environment. Exact same library! Just with fewer String and more &'static str. So toying around with compilers translates my skill-set rather well into doing embedded protocol parsers.
- djfobbz 2y agoSorry my OCD is kicking in but "Asterisk" is spelled wrong as "Asteriks" in your entire sample code.
- nicoco 2y agoEvery rust article: "Look how great this rust feature is and how clean and concise the resulting code is!" Me: "How can a programming language be so damn complex? Am I just dumb?"
- biorach 2y agoThere's plenty of complex programming languages out there. Some are worth putting the time into. If you can program well in some other language you can get your head around Rust - give it some time - it's worth it.
- pornel 2y agoIf you don't know the language, and it's different from what you know, it may look incomprehensible to you whether it's complex or not. For example, the Korean alphabet is pretty simple, and the spelling is simpler than English, but to English speakers it can look intimidating, like hundreds of blocks of unrecognizable squiggles. The article (over)uses macros, which make the code look more convoluted than it really is. The macro-by-example syntax is conceptually simple, but it has a punctuation-heavy syntax that may look alien if you don't know what you're looking at. BTW, this macro system has been originally designed for JavaScript, which is why even in Rust it looks odd by Rust's standards.
- samsartor 2y agoImperative rust is really good for parsing, but you can also get a long way with regexes. Especially if you are just prototyping or doing Advent of Code. I do still like declarative parsing over imperative, so I wrote https://docs.rs/inpt https://docs.rs/inpt on top of the regex crate. But Andrew Gallant gets all the credit, the regex crate is overpowered.