3 ms·
I've recently played with making simple JS-based parsers without reading anything about the theory. My conclusion was that making a parser by itself is a relati
by gambler 6y ago
I've recently played with making simple JS-based parsers without reading anything about the theory. My conclusion was that making a parser by itself is a relatively easy task. The hard part is making grammars easy to read and write, as well as handling various errors.
My best stab at representing something like EBNF in JS looked like this:
class ArrayGrammar { //e.g: [1, 2, 3, [4, 5,],]
array =()=> ['[', this.entries, ']'];
entries =()=> many(this.entry);
entry =()=> [either(this.array, this.number, ''), /\s*,\s*/];
number =()=> /\d+/;
}
This is a grammar for "arrays" of positive integers. I tested it out and concluded that this is too awful to be of any practical use. Now I'm seeing something with significantly more involved representation making it to the front page of HN. Hm.
---
Edit: Not much to look at, but here is the source code of the toy implementation if anyone is interested:
https://jsfiddle.net/306jrnt9/1/ https://jsfiddle.net/306jrnt9/1/
The only "cool" part about it is that the parser implementation is close to 100 lines of code.
- rmasters 6y agoTree-sitter uses JS for grammars and I'm sure there are others: https://tree-sitter.github.io/tree-sitter/creating-parsers#the-first-few-rules https://tree-sitter.github.io/tree-sitter/creating-parsers#t...
- gambler 6y agoI was aiming for sub-100 lines of code implementation. IMO, a full-fledged library would be much better off if they just supported EBNF or McKeeman Form.
- hardmath123 6y agoParsers in nearley.js [1] are written in a very readable EBNF-like DSL; then they get desugared down to a JS file that's a lot like your snippet. [1] https://github.com/kach/nearley https://github.com/kach/nearley
- matheusmoreira 6y agoI love Earley's algorithm! I wonder why it's so rare. Nearley is the only implementation I know. Why? It handles every possible grammar and yet it is a relatively simple algorithm. Would make an excellent choice for a standard library parse(grammar, input) function. Is it because the papers are hard to understand? All those symbols make no sense to the uninitiated. I definitely struggled to gain an understanding of how it works.