Maybe this will bring the idea of “TypeScript tooling should run the typechecker before doing anything else” (like linting, running tests, etc.). It feels very backwards that you can make a bundle with vite or whatever without the code being in a compilable state.
I mean, most bundlers or compilers don’t automatically run a linter or force all the tests to pass before compiling the code. It’s surprisingly convenient being able to separate type checking from whether the code runs or not. It makes it very easy to make a change locally and test it out, without having to update the entire codebase based on the change you’ve made. In most cases, you need to do compilation to get your code to run in the first place, but Typescript is lucky that type checking can be decoupled in this way.
Obviously everything needs to type check before ending up in production, but this is the same as tests, linting, and so on.
This hits me right in the feels. I picked my college because they had a mainframe. Some amber terminals, some green, but I never saw a blue one. Very nice :) Can this be rendered fast enough to make a terminal experience out of it? Or is it more for making screenshots?
I haven’t optimized for speed at all, the div rendering would probably be quite slow in practice. I had a brief attempt at converting this to a C + SDL2/3 program but had some issues with rectangles / pixels showing up blurred (probably Retina / HiDPI issues) and I abandoned that.
I think to use this in a game or a website you’d likely want to bake the calculations into a bitmap atlas and string those full character “PNGs” together. I kept the calculations runtime in the above demo to allow for fast experimentation.
As a heavy Go user and former ReasonML kinda-fanboi, Gleam really piques my interest. Still looking for the right project to give it a try with, but watching from afar I’m really impressed with what I see.
How do you fight the sinking feeling that writing all the tooling around the language that’s needed for it to be even considered modern (LSP, auto-formatter, package manager, …) is going to take you another few years in addition to the compiler itself? At this point I’m glad when I get a few weeks of focused time on Cara a year.
I don’t use any of those things for my main work language, so I certainly don’t need them for my little toy language either. And since I’m making it for me, once it works for me, it’s done!
Well, I’m obviously skeptical of such gains, but my real point is just to not worry about if other people consider your language modern or not and just do what works for you.
The most well-known presentations (Vaughan Pratt’s in Lisp and Douglas Crockford’s in JavaScript) use dynamic languages, but it works nicely in static languages too. I’ve written expression parsers in pushdown automaton style and Pratt style and I prefer the Pratt style because more kinds of operators fit into the pattern and it has a fairly smooth transition to recursive descent.
I was involved in the Elm community (it’s a small pond though so it’s easy to get noticed), helping out beginners on the Slack, speaking at conferences, writing libraries and so on. That was while I was still a way underpaid junior in a JavaScript+Java+Kotlin shop.
One day I wrote to our #cz-sk channel on the Elm Slack how an interview at a Prague React shop turned out to be a dud (in the job posting they promised remote, but that turned out to be a lie), and a friend from the channel asked if I wanted to work with them. Better money, better language (read: Elm), full remote and people I know already. Got there and lived the dream for about 3 years (really, a dream job) until the management changed, made some dubious decisions and we all ran away to different companies.
Since then I worked in remote Elm companies. The layoff situation in the sweng world is a bit rough right now but I am very grateful for the journey so far. All that started, IMHO, with my involvement in the language community.
I fully expected one of the drawbacks of the vector format (compared to bitmap) to be that the 16x16 icons are less legible (at least the example in this post, the casette player, is). There is something about hinting for small sizes. Must be why I love 9px Verdana :)
Would be interesting to try to come up with some kind of hinting for HVIF ’cause that example image shows a few fairly clear places where it matters most: darker outline, darker shadow, maybe higher contrast in general…
Hey there, no, it’s just ligatures for -> and |>. If you copypaste the code snippets into your editor, it should show that.
I can try making it hide the ligatures on hover with font-variant-ligatures: none; but I’m not sold on removing them altogether.
I just discovered Pratt parsers two(?) weeks ago, and this is the clearest intro I’ve read yet — I wish I’d been able to read it first! There’s good stuff in the original paper and Crockford’s lengthy JS article/example, but they were each tougher to puzzle out. That TL;DR flowchart at the top of this article would have lit my Aha! lightbulb.
I’m glad you got into prefix and postfix operators at the end.
The one big idea IMHO that isn’t expressed here is that the recursive parse calls can be delegated to the operators — each operator can have one or two attached functions (one for prefix, one infix/postfix) and the main parser calls the appropriate function. Those functions then make the recursive calls. (I’m trying to stick with functional terminology; in my mind, the operators are classes.)
This makes the parser much easier to extend: you can use it for the entire language, not just algebraic expressions. For example, an “if” operator whose parsePrefix() function first parses an expression that becomes the condition, then matches “then”, then parses the ‘then’ clause, then looks for “else” and if it finds it parses the ‘else’ clause.
This was the insight I got from Crockford’s article; it’s in Pratt’s paper too, but harder to figure out.
The one big idea IMHO that isn’t expressed here is that the recursive parse calls can be delegated to the operators
Oh yeah. That’s a good point. I touch on it a little bit when discussing postfix operators: the recursive calling of pratt is moved out of pratt itself and given to the operator-specific parser. But I might try to amend the article a little bit to spell this out more clearly.
I’ve just started using Pratt parser techniques, which are also great. I wonder if they can be combined with parser combinators, for even more goodness…
This is why in Roc we don’t have a “length” function for strings: if the strings are Unicode, it’s easy to have an inaccurate mental model of what a function named “length” is telling you about the string.
Have you/the Roc team done some research into whether counting graphemes is on average more useful than counting the clusters? I’m considering this question for Cara - so far I plan to make the String API work on clusters instead.
Btw your documentation says “Counts the number of extended grapheme clusters in the string.”, which seems to be wrong to me if it gives 4 for “👩👩👦👦”
Elm strives to be a pure language - with no unmanaged side effects, and no runtime errors. In order to achieve that, native modules were restricted so that there couldn’t be code that would either have buggy JS or do secret side effect stuff. Previously there was a whitelist of packages with native modules allowed on the official package host, to cut down on the possible native modules. But as the community and needs grew, there were cases of people handrolling their own packaging solution to bypass the whitelist. Eventually, this whitelist was replaced by a hardcoded restriction within the compiler itself. The idea was to keep Elm pure and safe for all users, and to encourage solutions written directly in Elm rather than in some wrappers around JS.
This was seen as problematic as it prevented some libraries doing things with stuff like the DOM API. But I think the goal was to keep Elm as consistent as possible.
Overall with hindsight it turned out WebComponents are a great way to keep Elm pure and still have some of that JS whenever you need it, and if all else fails there are still ports (for async Elm<->JS communication) and Proxies (kind of a dirty hack you can smuggle on init via Flags if you really really need sync Elm<->JS, sacrificing purity/referential transparency).
I reckon if native modules were more widespread, the community would take much longer to arrive at WebComponents.
ATO is a online code sandbox, with an emphasis on niche languages. If you ever wanted to try APL or Chapel but didn’t feel like downloading the whole language, here ya go.
it’s from pxeger, who is also a user on code golf stack exchange. Since TIO will likely be stagnant for the near future, ATO allows contributions and has more chances for new languages to be added.
I wish the puzzles were more.. Abridged? I find hard them hard to understand because you have to first make sense what the puzzle is from a wall of text.
But this is just the conceit of the first year of any engineering degree, no? Some sort of arbitrarily complicated prosey description of a vat of a chemical discharging into a pipe, or a long description of a bell in a church tower loosing 100ms a day because of air buoyancy, or an oscilloscope input not reacting to higher speed signals because of the thickness and permitivity of the fibreglass substrate… your job is to realise that all of these are just dressed-up instances of a simple differential equation, and the skill of engineering is to identify the underlying equation or algorithm and know an efficient way to solve it.
I dont have engineering degree, so i wouldnt know.
I just dont find reading these kind of huge walls of texts fun to decipher for many reasons. My friend simplified the first task well for me like this:
given a list of numbers, where each group of number is separated by an empty line:
--
10
10
20
20
30
--
find the largest sum
This is all i want basically. English not being my native language makes the big blocks slightly difficult to read at first, then my low attention span ruins the rest of it. So, not fun.
Basically i want to have fun too but it’s not very accessible to me.
Ah well, such is life.
Now if i would get paid to decipher the text, things would be different. :)
It’s a lot of fun. If you do competitive programming a lot you’ll start reading through the lines, as most problems have playful descriptions. I guess AoC is a fair bit heavier on that front, but people still manage to read it all and do it very quickly, and to be honest, that’s most of the fun for me, because if I just wanted some puzzles to solve, there’s plenty of other sites that can offer that.
The problem I found with parser combinator libraries is that left recursion seems to be essentially impossible to tackle, thus rendering them useless for simple things as arithmetic expressions. I’ve also heard that Packrat fails to intelligently parse A ::= a A a | \epsilon: presumably, only strings of length a power of two are accepted.
All in all, after hearing about PEG being the one true way to solve real life parsing, I’ve been pretty disappointed… Open to refutation though!
I think that you can do good engineering work with PEG parsers, even if they don’t handle certain difficult cases. Your job as a programmer is to understand the limitations of the tools available and e.g. rewrite a grammar with a A a in it to something the parser system can handle. I don’t think the problem of taking a completely arbitrary CFG and generating an efficient parser for it has been solved. https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html
One of the positives about PEG parsers for parsing things like programming languages is the left biasing is useful to express common PL syntax idioms, where a more theoretically pure description could have ambiguity in it. (relevant terms: ordered choice/soft cut)
If I was using rust I would want to take advantage of nom for the zero copy properties.
If you are not too much worried about the performance impact, you can limit the recursion to num(nonterminals) * (1 + |input_length|), which lets you escape the infinite recursion. (e.g)
See “Richard A. Frost, Rahmatullah Hafiz, and Paul C. Callaghan. Modular and efficient top-down parsing for ambiguous left recursive grammars. IWPT 2007”
I still think that expressing infix operators with the precedence climbing / Pratt parser algorithm is both more natural to write and more performant than via left recursion, though.
I looked at your library before deciding on Pest for my attempt at Make A Lisp. It looks quite robust but I had trouble with the pseudo-Rust syntax in the parser macro. What made you decide to go that route instead of a more traditional PEG syntax?
(Not to say Pest is “traditional”, it is fairly different than the PEG grammar described in the original paper, but it’s at least close enough to make translation easy.)
Using a procedural macro makes it integrate better into the Rust ecosystem. Many of the tokens are passed through to the generated Rust code with span information intact, so error messages point to the code you wrote rather than a generated file. Even works live in an editor with rust-analyzer! It does mean the syntax has to be compatible with the Rust lexer, though.
The biggest departure in syntax is the use of Rust’s patterns (['a'..='z']) for matching a character vs the regex-like syntax in most other PEG libraries ([a-z]). It’s more verbose, but this is to enable operation over data types other than strings – for example you can use an external lexer and match tokens like [Identifier(n)].
Other than that, it’s heavily inspired by PEG.js and some of the operators like $ come from there.
As far as I can tell, most every left recursive expression can be reformed into a non-left recursive form: term <- term "+" num / num can be rewritten as term <- num ("+" num)*, in the simplest example. This isn’t an ideal solution as the resulting parse tree is not as “natural” as the left recursive parse tree would be, but it is possible.
For your “only even forms” objection, Pest has added specific operators for “range” matching: A = @{ "a" ~ ("a"{2})* } matches 1 “a” plus any number of pairs of “a”. (This could be accomplished more easily with @{ "a" ~ "aa"* } but that’s less fun. ;) )
There are methods for handling left recursion directly (Python’s new PEG parser implements one such method, and the Pegged library for D implements another), but they’re more complicated than the base case.
Maybe this will bring the idea of “TypeScript tooling should run the typechecker before doing anything else” (like linting, running tests, etc.). It feels very backwards that you can make a bundle with vite or whatever without the code being in a compilable state.
I mean, most bundlers or compilers don’t automatically run a linter or force all the tests to pass before compiling the code. It’s surprisingly convenient being able to separate type checking from whether the code runs or not. It makes it very easy to make a change locally and test it out, without having to update the entire codebase based on the change you’ve made. In most cases, you need to do compilation to get your code to run in the first place, but Typescript is lucky that type checking can be decoupled in this way.
Obviously everything needs to type check before ending up in production, but this is the same as tests, linting, and so on.
It doesn’t have quite the same flicker as you got with original CRTs
Yeah and the background + the debug controls don’t have scanlines at all, completely unplayable :)
This hits me right in the feels. I picked my college because they had a mainframe. Some amber terminals, some green, but I never saw a blue one. Very nice :) Can this be rendered fast enough to make a terminal experience out of it? Or is it more for making screenshots?
Take a look at cool-retro-term.
I haven’t optimized for speed at all, the div rendering would probably be quite slow in practice. I had a brief attempt at converting this to a C + SDL2/3 program but had some issues with rectangles / pixels showing up blurred (probably Retina / HiDPI issues) and I abandoned that.
I think to use this in a game or a website you’d likely want to bake the calculations into a bitmap atlas and string those full character “PNGs” together. I kept the calculations runtime in the above demo to allow for fast experimentation.
Did blue ones even exist? I’ve seen monochrome displays in amber, green and white, but not sure I’ve ever even heard of one in blue.
see for example this list: https://en.wikipedia.org/wiki/Phosphor#Standard_phosphor_types
I have seen blue on some oscilloscopes, however P1 (green) and P3 (amber) are more common.
Ooooh, cool. Thanks!
As a heavy Go user and former ReasonML kinda-fanboi, Gleam really piques my interest. Still looking for the right project to give it a try with, but watching from afar I’m really impressed with what I see.
Some of the codecrafters.io courses (“write a Redis from scratch in Gleam”) are free until end of November! Quite a nice exercise to go through.
How do you fight the sinking feeling that writing all the tooling around the language that’s needed for it to be even considered modern (LSP, auto-formatter, package manager, …) is going to take you another few years in addition to the compiler itself? At this point I’m glad when I get a few weeks of focused time on Cara a year.
I don’t use any of those things for my main work language, so I certainly don’t need them for my little toy language either. And since I’m making it for me, once it works for me, it’s done!
This argument feels fallacious. Imagine your productivity if you were using those tools effectively.
Well, I’m obviously skeptical of such gains, but my real point is just to not worry about if other people consider your language modern or not and just do what works for you.
Let me plug the Top Down Operator Precedence parsing algorithm, which I only learned about last year. Link is to Douglas Crockford’s article about it.
Yeah, see also my collection of Pratt parser links which includes a link to ~andyc’s collection.
The most well-known presentations (Vaughan Pratt’s in Lisp and Douglas Crockford’s in JavaScript) use dynamic languages, but it works nicely in static languages too. I’ve written expression parsers in pushdown automaton style and Pratt style and I prefer the Pratt style because more kinds of operators fit into the pattern and it has a fairly smooth transition to recursive descent.
In the Elm community we sometimes discuss whether the app model should be a product
which doesn’t lose an old page’s state when you navigate to a new one, or a sum:
which only holds the current one. This article feels very close to that topic.
I was involved in the Elm community (it’s a small pond though so it’s easy to get noticed), helping out beginners on the Slack, speaking at conferences, writing libraries and so on. That was while I was still a way underpaid junior in a JavaScript+Java+Kotlin shop.
One day I wrote to our #cz-sk channel on the Elm Slack how an interview at a Prague React shop turned out to be a dud (in the job posting they promised remote, but that turned out to be a lie), and a friend from the channel asked if I wanted to work with them. Better money, better language (read: Elm), full remote and people I know already. Got there and lived the dream for about 3 years (really, a dream job) until the management changed, made some dubious decisions and we all ran away to different companies.
Since then I worked in remote Elm companies. The layoff situation in the sweng world is a bit rough right now but I am very grateful for the journey so far. All that started, IMHO, with my involvement in the language community.
I fully expected one of the drawbacks of the vector format (compared to bitmap) to be that the 16x16 icons are less legible (at least the example in this post, the casette player, is). There is something about hinting for small sizes. Must be why I love 9px Verdana :)
Would be interesting to try to come up with some kind of hinting for HVIF ’cause that example image shows a few fairly clear places where it matters most: darker outline, darker shadow, maybe higher contrast in general…
The article didn’t mention that HVIF also includes level of detail to optimise for rendering at smaller sizes
oooooooh, neat!
There’s some information about the LoD feature with examples in the Icon-O-Matic documentation.
The code blocks appear to suggest that writing Elm requires entering exotic symbols, arrows and triangles. Is that right?
Hey there, no, it’s just ligatures for -> and |>. If you copypaste the code snippets into your editor, it should show that. I can try making it hide the ligatures on hover with
font-variant-ligatures: none;but I’m not sold on removing them altogether.I just discovered Pratt parsers two(?) weeks ago, and this is the clearest intro I’ve read yet — I wish I’d been able to read it first! There’s good stuff in the original paper and Crockford’s lengthy JS article/example, but they were each tougher to puzzle out. That TL;DR flowchart at the top of this article would have lit my Aha! lightbulb.
I’m glad you got into prefix and postfix operators at the end.
The one big idea IMHO that isn’t expressed here is that the recursive parse calls can be delegated to the operators — each operator can have one or two attached functions (one for prefix, one infix/postfix) and the main parser calls the appropriate function. Those functions then make the recursive calls. (I’m trying to stick with functional terminology; in my mind, the operators are classes.)
This makes the parser much easier to extend: you can use it for the entire language, not just algebraic expressions. For example, an “if” operator whose parsePrefix() function first parses an expression that becomes the condition, then matches “then”, then parses the ‘then’ clause, then looks for “else” and if it finds it parses the ‘else’ clause.
This was the insight I got from Crockford’s article; it’s in Pratt’s paper too, but harder to figure out.
Thank you for the feedback!
Oh yeah. That’s a good point. I touch on it a little bit when discussing postfix operators: the recursive calling of
prattis moved out ofprattitself and given to the operator-specific parser. But I might try to amend the article a little bit to spell this out more clearly.I’ve just started using Pratt parser techniques, which are also great. I wonder if they can be combined with parser combinators, for even more goodness…
They can! For example, Elm has a parser combinator library (elm/parser) and there’s a library adding Pratt parsing combinators: https://package.elm-lang.org/packages/dmy/elm-pratt-parser/latest/
This is why in Roc we don’t have a “length” function for strings: if the strings are Unicode, it’s easy to have an inaccurate mental model of what a function named “length” is telling you about the string.
Instead we have countGraphemes:
https://www.roc-lang.org/builtins/Str#countGraphemes
Have you/the Roc team done some research into whether counting graphemes is on average more useful than counting the clusters? I’m considering this question for Cara - so far I plan to make the String API work on clusters instead.
Btw your documentation says “Counts the number of extended grapheme clusters in the string.”, which seems to be wrong to me if it gives 4 for “👩👩👦👦”
(Swift counts clusters and gives 1 for “👩👩👦👦”)
I guess I just don’t understand why Elm restricted native modules to begin with. What was the stated reasoning?
Elm strives to be a pure language - with no unmanaged side effects, and no runtime errors. In order to achieve that, native modules were restricted so that there couldn’t be code that would either have buggy JS or do secret side effect stuff. Previously there was a whitelist of packages with native modules allowed on the official package host, to cut down on the possible native modules. But as the community and needs grew, there were cases of people handrolling their own packaging solution to bypass the whitelist. Eventually, this whitelist was replaced by a hardcoded restriction within the compiler itself. The idea was to keep Elm pure and safe for all users, and to encourage solutions written directly in Elm rather than in some wrappers around JS.
This was seen as problematic as it prevented some libraries doing things with stuff like the DOM API. But I think the goal was to keep Elm as consistent as possible.
Overall with hindsight it turned out WebComponents are a great way to keep Elm pure and still have some of that JS whenever you need it, and if all else fails there are still ports (for async Elm<->JS communication) and Proxies (kind of a dirty hack you can smuggle on init via Flags if you really really need sync Elm<->JS, sacrificing purity/referential transparency).
I reckon if native modules were more widespread, the community would take much longer to arrive at WebComponents.
ATO is a online code sandbox, with an emphasis on niche languages. If you ever wanted to try APL or Chapel but didn’t feel like downloading the whole language, here ya go.
A nicer-looking TIO! Thanks :)
it’s from pxeger, who is also a user on code golf stack exchange. Since TIO will likely be stagnant for the near future, ATO allows contributions and has more chances for new languages to be added.
I wish the puzzles were more.. Abridged? I find hard them hard to understand because you have to first make sense what the puzzle is from a wall of text.
Once the difficulty starts to ramp up you begin to appreciate the verbiage.
Once you strip away the contrived backstory, the text is quite clear.
Ofc there were the dark days of 2018D15, but I believe that was a team effort and Wastl wasn’t as involved as he was before and since.
Here’s a puzzle I still haven’t cracked, compare and contrast: 2019D18
Unfortunately this is clearly not for me. :(
I hate that when you mentioned 2018D15, I knew what puzzle it was. Still unsolved for me.
So many moving parts! And boring as well.
I just checked and that was the last day I completely gave up trying to complete a puzzle. They were very difficult.
But this is just the conceit of the first year of any engineering degree, no? Some sort of arbitrarily complicated prosey description of a vat of a chemical discharging into a pipe, or a long description of a bell in a church tower loosing 100ms a day because of air buoyancy, or an oscilloscope input not reacting to higher speed signals because of the thickness and permitivity of the fibreglass substrate… your job is to realise that all of these are just dressed-up instances of a simple differential equation, and the skill of engineering is to identify the underlying equation or algorithm and know an efficient way to solve it.
I dont have engineering degree, so i wouldnt know.
I just dont find reading these kind of huge walls of texts fun to decipher for many reasons. My friend simplified the first task well for me like this:
This is all i want basically. English not being my native language makes the big blocks slightly difficult to read at first, then my low attention span ruins the rest of it. So, not fun.
Basically i want to have fun too but it’s not very accessible to me.
Ah well, such is life.
Now if i would get paid to decipher the text, things would be different. :)
It’s a lot of fun. If you do competitive programming a lot you’ll start reading through the lines, as most problems have playful descriptions. I guess AoC is a fair bit heavier on that front, but people still manage to read it all and do it very quickly, and to be honest, that’s most of the fun for me, because if I just wanted some puzzles to solve, there’s plenty of other sites that can offer that.
Elm in this context is a “delightful” functional language for reliable web applications. https://elm-lang.org/
Good to see the email client crowd! 👋 /crosses out his Bingo/
A data point: in Elm semver is enforced, and there are some packages with major version numbers in tens.
The problem I found with parser combinator libraries is that left recursion seems to be essentially impossible to tackle, thus rendering them useless for simple things as arithmetic expressions. I’ve also heard that Packrat fails to intelligently parse
A ::= a A a | \epsilon: presumably, only strings of length a power of two are accepted. All in all, after hearing about PEG being the one true way to solve real life parsing, I’ve been pretty disappointed… Open to refutation though!I think that you can do good engineering work with PEG parsers, even if they don’t handle certain difficult cases. Your job as a programmer is to understand the limitations of the tools available and e.g. rewrite a grammar with
a A ain it to something the parser system can handle. I don’t think the problem of taking a completely arbitrary CFG and generating an efficient parser for it has been solved. https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.htmlOne of the positives about PEG parsers for parsing things like programming languages is the left biasing is useful to express common PL syntax idioms, where a more theoretically pure description could have ambiguity in it. (relevant terms: ordered choice/soft cut)
If I was using rust I would want to take advantage of
nomfor the zero copy properties.Interesting link, thanks! The author refers to “boolean grammars”; I wonder if these got any traction, either in research or applications.
If you are not too much worried about the performance impact, you can limit the recursion to
num(nonterminals) * (1 + |input_length|), which lets you escape the infinite recursion. (e.g)See “Richard A. Frost, Rahmatullah Hafiz, and Paul C. Callaghan. Modular and efficient top-down parsing for ambiguous left recursive grammars. IWPT 2007”
There’s a clever way that PEG / packrat parsers can use the memoization cache to support left recursion quite simply: https://medium.com/@gvanrossum_83706/left-recursive-peg-grammars-65dab3c580e1
I still think that expressing infix operators with the precedence climbing / Pratt parser algorithm is both more natural to write and more performant than via left recursion, though.
(I maintain another PEG library in Rust that implements both of these.)
I looked at your library before deciding on Pest for my attempt at Make A Lisp. It looks quite robust but I had trouble with the pseudo-Rust syntax in the parser macro. What made you decide to go that route instead of a more traditional PEG syntax?
(Not to say Pest is “traditional”, it is fairly different than the PEG grammar described in the original paper, but it’s at least close enough to make translation easy.)
Using a procedural macro makes it integrate better into the Rust ecosystem. Many of the tokens are passed through to the generated Rust code with span information intact, so error messages point to the code you wrote rather than a generated file. Even works live in an editor with rust-analyzer! It does mean the syntax has to be compatible with the Rust lexer, though.
The biggest departure in syntax is the use of Rust’s patterns (
['a'..='z']) for matching a character vs the regex-like syntax in most other PEG libraries ([a-z]). It’s more verbose, but this is to enable operation over data types other than strings – for example you can use an external lexer and match tokens like[Identifier(n)].Other than that, it’s heavily inspired by PEG.js and some of the operators like
$come from there.As far as I can tell, most every left recursive expression can be reformed into a non-left recursive form:
term <- term "+" num / numcan be rewritten asterm <- num ("+" num)*, in the simplest example. This isn’t an ideal solution as the resulting parse tree is not as “natural” as the left recursive parse tree would be, but it is possible.For your “only even forms” objection, Pest has added specific operators for “range” matching:
A = @{ "a" ~ ("a"{2})* }matches 1 “a” plus any number of pairs of “a”. (This could be accomplished more easily with@{ "a" ~ "aa"* }but that’s less fun. ;) )There are methods for handling left recursion directly (Python’s new PEG parser implements one such method, and the Pegged library for D implements another), but they’re more complicated than the base case.
Re left recursion: see here - https://www.youtube.com/watch?v=b2AUW6psVcE Solves left recursion for BNF/EBNF/… https://github.com/Engelberg/instaparse