MZ Parser combinator library
Preserved forum archive. This topic stores the original first post and locally mirrored RPG Maker Web attachments when available. It is posted by the BMMPlay archive account, not by the original creator.
Original Source
- Original title: MZ Parser combinator library
- Original author: Masked
- Original date: September 1, 2020
- Source thread: https://forums.rpgmakerweb.com/threads/parser-combinator-library.126545/
- Source forum path: Game Development Engines > RPG Maker Javascript Plugins > JS Plugins In Development
Summary
Hey there \o So, I've been working on a little "core" plugin for parsing, and thought of sharing it here to gather some feedback and ideas. Hope you enjoy What is a parser? On a general sense, a parser is a program that analyses strings. If you're a programmer, you're probably familiar with parsers, even if you don't realize it: every programming language has a parser as part of its compiler/interpreter/whatever. That goes to show a little about how powerful these things can be, but lets calm down a little,...
Archived First Post
Hey there \o
So, I've been working on a little "core" plugin for parsing, and thought of sharing it here to gather some feedback and ideas. Hope you enjoy
What is a parser?
On a general sense, a parser is a program that analyses strings. If you're a programmer, you're probably familiar with parsers, even if you don't realize it: every programming language has a parser as part of its compiler/interpreter/whatever. That goes to show a little about how powerful these things can be, but lets calm down a little, my intention is not to make a new programming language here (altough that would be fun, and totally possible).
A more grounded example would be a simple command line calculator, which takes an expression like "18 * 3 - 7" as input and outputs a numeric result (I know that's not very impressive but hold my orange juice). In this case, the parser would come in as a way to transform that string of digits and operators into something that could be processed somewhat reasonably by the computer, usually an Abstract Syntax Tree (or AST for short).
I'll borrow this picture from Ruslan Pivak's article on AST's (which makes for a great read if you have some time to spare, btw) to illustrate:
Point is: once we have an AST, we can use it to get to our goal quite easily with some recursion.
Now what is a parser combinator?
Ah! Glad you asked (or not). So, basically, combinators are endofunctors on the category of parsers! (Sorry, I don't know what these mean either)
Putting the category theory/functional programming stuff away for a second, a parser combinator is just a function that combines parsers, as the name suggests. "Combine" meaning all sorts of things, really: you could combine parsers with an "or" and have one parsed act as a fallback to another, or use a "many" to combine a parser with itself and have it match repeated expressions, or any sorts of other useful things.
To demonstrate how they're used, here's an example parser that parses a JSON number (as defined in https://www.json.org/, with the only exception that it also accepts a trailing '+' or trailing '0's), taken from the plugin repository:
At first, it seems weird with all those
And it's also declarative, which tends to be easier to understand than imperative code that does the same thing.
And what's the point?
Well, at this point you are probably wondering: and why the hell would I need that?
That's fair, but I'd argue that:
I also have the intention of shipping the plugin with some commonly used parsers, such as the arithmetic parser (which is already available /o/), a note tag parser and other stuff I can think of (I'm taking suggestions haha).
Ok, i get it, now where's the code?
The source code is available on Github: https://github.com/comuns-rpgmaker/schach-parsing
Documentation is available on Github Pages: https://comuns-rpgmaker.github.io/schach-parsing/index.html
Check out the releases if you're interested on testing it without having to compile. Everything is namespaced under
Can I use this as it is?
I wouldn't recommend that, no. At the time of writing, this project is more a proof of concept than anything, and drastic API changes could happen as it evolves into a stable version. There are also some serious performance issues that must be addressed before any application of this library.
When will it be available?
You can keep an eye on the Github projects for the plugin, as well as the issues I've created to keep track of development.
Will it be free for commercial use?
It's licensed under the Zlib license (so yes, it will).
Thank you for your attention \o
So, I've been working on a little "core" plugin for parsing, and thought of sharing it here to gather some feedback and ideas. Hope you enjoy
What is a parser?
On a general sense, a parser is a program that analyses strings. If you're a programmer, you're probably familiar with parsers, even if you don't realize it: every programming language has a parser as part of its compiler/interpreter/whatever. That goes to show a little about how powerful these things can be, but lets calm down a little, my intention is not to make a new programming language here (altough that would be fun, and totally possible).
A more grounded example would be a simple command line calculator, which takes an expression like "18 * 3 - 7" as input and outputs a numeric result (I know that's not very impressive but hold my orange juice). In this case, the parser would come in as a way to transform that string of digits and operators into something that could be processed somewhat reasonably by the computer, usually an Abstract Syntax Tree (or AST for short).
I'll borrow this picture from Ruslan Pivak's article on AST's (which makes for a great read if you have some time to spare, btw) to illustrate:
Now what is a parser combinator?
Ah! Glad you asked (or not). So, basically, combinators are endofunctors on the category of parsers! (Sorry, I don't know what these mean either)
Putting the category theory/functional programming stuff away for a second, a parser combinator is just a function that combines parsers, as the name suggests. "Combine" meaning all sorts of things, really: you could combine parsers with an "or" and have one parsed act as a fallback to another, or use a "many" to combine a parser with itself and have it match repeated expressions, or any sorts of other useful things.
To demonstrate how they're used, here's an example parser that parses a JSON number (as defined in https://www.json.org/, with the only exception that it also accepts a trailing '+' or trailing '0's), taken from the plugin repository:
JavaScript:
import { Parser, pure } from '../base';
import { many1 } from '../combinators';
import { char, digit, spaces } from '../text';
import type { NumberExpression } from './types';
/**
* @returns a parser that accepts a (possibly signed) string of digits and
* returns an int.
*/
export function integer(): Parser<string, number>
{
return many1(digit())
.map(digits => digits.reduce((acc, n) => acc * 10 + n));
}
const sign =
char('-').thenDrop(spaces).dropThen(pure(-1))
.or(char('+').dropThen(pure(1)))
.or(pure(1));
const floatingPoint =
char('.')
.dropThen(many1(digit()))
.map(digits => digits.reduceRight((acc, n) => n + acc / 10) / 10);
const exponent =
char('e')
.dropThen(sign.flatMap(bit => integer().map(n => bit * n)))
.map(e => Math.pow(10, e))
.or(pure(1));
/**
* @returns a parser that accepts a string of digits and/or a floating point
* expression and returns a number.
*/
export function number(): Parser<string, number>
{
return sign.flatMap(bit =>
integer()
.flatMap(n => floatingPoint.map(f => bit * (n + f)).or(pure(n)))
.or(floatingPoint)
.flatMap(n => exponent.map(e => n * e))
.error((_, context) => `expected number, got '${context}'`));
}At first, it seems weird with all those
thenDrop and flatMap functions, but once you get used to those, it's very powerful! In less than 70 lines, we got ourselves a fully featured number parser (with all those floating point and exponent shenanigans too!).And it's also declarative, which tends to be easier to understand than imperative code that does the same thing.
And what's the point?
Well, at this point you are probably wondering: and why the hell would I need that?
eval exists and I know RegEx!That's fair, but I'd argue that:
- A parser is MUCH more readable than a RegEx (it's hard not to be), and a lot more powerful and flexible too. As some of you might know, a regular expression is roughly equivalent to a finite state machine, which can only do so much (it's the weakest on the Chomsky hierarchy!). The output they generate is also quite limited, meaning they must always be used along with other code. They also hardly generate useful errors (either they match or they don't), which are almost trivial to generate using parser combinators.
- Eval can be more powerful than a parser, that's for granted. But it's also not even close to being as safe (I think I don't even have to defend this) or flexible. For one, it's limited to Javascript syntax and error handling, which is not always ideal.
I also have the intention of shipping the plugin with some commonly used parsers, such as the arithmetic parser (which is already available /o/), a note tag parser and other stuff I can think of (I'm taking suggestions haha).
Ok, i get it, now where's the code?
The source code is available on Github: https://github.com/comuns-rpgmaker/schach-parsing
Documentation is available on Github Pages: https://comuns-rpgmaker.github.io/schach-parsing/index.html
Check out the releases if you're interested on testing it without having to compile. Everything is namespaced under
Schach.Parsing, and a simple usage example is given in the README on the repository.Can I use this as it is?
I wouldn't recommend that, no. At the time of writing, this project is more a proof of concept than anything, and drastic API changes could happen as it evolves into a stable version. There are also some serious performance issues that must be addressed before any application of this library.
When will it be available?
You can keep an eye on the Github projects for the plugin, as well as the issues I've created to keep track of development.
Will it be free for commercial use?
It's licensed under the Zlib license (so yes, it will).
Thank you for your attention \o
Downloads / Referenced Files
Log in to download
Log in, then follow the RPG Maker Developers Group to see these download links.
Log in to downloadLicense / Terms Note
Will it be free for commercial use? It's licensed under the Zlib license (so yes, it will). Thank you for your attention \o
Referenced Images / Attachments
Creator Claims / Removal
If you are the original creator and want this listing reassigned, edited, or removed, join BMMPlay and contact the moderators with proof that matches the original RPG Maker Web profile, linked GitHub, itch.io page, or another public creator identity.
Replies (0)
No replies yet.
Topic Summary
Loading summary...