How to implement a meta-circular evaluator to parse `[1..10]` in JavaScript?

267 views Asked by At

I want to implement a meta-circular evaluator in JS with support to functional programming.

How can I parse this?

[1..10]

I want to receive 1 and 10

3

There are 3 answers

0
customcommander On

I've been longing to try out nearley.js for so long. This may or may not be what you wanted!


Please do note that I have assumed that what you want to get out of [1..10] is all the numbers from 1 to 10 (included), e.g. [1,2,3,4,5,6,7,8,9,10].


Let's define the grammar for this mini language

grammar.ne

# Given the string "[1..10]", AST is ['[', 1, '..', 10, ']']
# We define a postprocessor that immediately interprets the expression
range -> "[" number ".." number "]" {%
  function range(ast) {
    const [,a,,b,] = ast; // extracts the number from the ast
    const len = Math.abs(a - b) + 1;
    const inc = a < b ? (_, i) => a + i : (_, i) => a - i;
    return Array.from(Array(len), inc);
  }
%}

# Given the string "1", AST is [['1']]
# Given the string "10", AST is [['1','0']]
# We define a postprocessor that joins the characters together and coerce them into a number.
number -> [0-9]:+ {% ([chars]) => Number(chars.join('')) %}

What I like about nearley.js is that it allows you to embed post processors for your rules right into the grammar. It may looks ugly but I find it pretty neat actually!

Another cool thing, is that nearley.js comes with a suite of useful tools. One of them generates a diagram for your grammar:

yarn run -s nearley-railroad grammar.ne > grammar.html

Here's the output:

As you can see a range is a sequence of:

  1. Starts with "["
  2. Followed by a number
  3. Followed by ".."
  4. Followed by a number
  5. Ends with "]"

enter image description here

Now we need to compile that grammar

yarn run -s nearleyc grammar.ne > grammar.js

This code needs to be loaded into a parser. I'm just showing the compiled grammar for illustration purpose:

grammar.js

// Generated automatically by nearley, version 2.19.3
// http://github.com/Hardmath123/nearley
(function () {
function id(x) { return x[0]; }
var grammar = {
    Lexer: undefined,
    ParserRules: [
    {"name": "range$string$1", "symbols": [{"literal":"."}, {"literal":"."}], "postprocess": function joiner(d) {return d.join('');}},
    {"name": "range", "symbols": [{"literal":"["}, "number", "range$string$1", "number", {"literal":"]"}], "postprocess": 
        function range(ast) {
          const [,a,,b,] = ast; // extracts the number from the ast
          const len = Math.abs(a - b) + 1;
          const inc = a < b ? (_, i) => a + i : (_, i) => a - i;
          return Array.from(Array(len), inc);
        }
        },
    {"name": "number$ebnf$1", "symbols": [/[0-9]/]},
    {"name": "number$ebnf$1", "symbols": ["number$ebnf$1", /[0-9]/], "postprocess": function arrpush(d) {return d[0].concat([d[1]]);}},
    {"name": "number", "symbols": ["number$ebnf$1"], "postprocess": ([chars]) => Number(chars.join(''))}
]
  , ParserStart: "range"
}
if (typeof module !== 'undefined'&& typeof module.exports !== 'undefined') {
   module.exports = grammar;
} else {
   window.grammar = grammar;
}
})();

Now let's build a parser and use it!

index.js

const nearley = require("nearley");
const grammar = require("./grammar"); // loads the compiled grammar!

const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar));

parser.feed("[1..10]");

console.log(parser.results[0]);
//=> [1,2,3,4,5,6,7,8,9,10]
2
user120242 On

This is a basic implementation of generating a range.
The goal you are talking about is going to be too complex for regex (firmly tongue in cheek).

Using tagged template literal syntax.
Regex finds two digit sequences, converts to numbers. Fills an array.

range = (str,...args) =>
(([,min,max])=>
  Array(Math.abs(max-min)+1).fill(+min).map((_,i)=>_+i*(min>max?-1:1)))
    ((Array.isArray(str) ? str.map((s,i)=>s+args[i]).join('') : str)
      .match(/\[\s*(-?\d+)\s*\.\.\s*(-?\d+)\s*\]/))

x=-3, y=0
console.log(
range`[5..1]`,
range`[1..10]`,
range("[ 5 .. -2 ]"),
range`[${x}.. ${y}]`
)

0
selbie On

Regex: \[([0-9]+)\.\.([0-9]+)\]

I confirmed the regex via regex101.com and let it generate the sample code.

const regex = /\[([0-9]+)\.\.([0-9]+)\]/gm;
const str = `[1..10]`;
let m;

while ((m = regex.exec(str)) !== null) {
    // This is necessary to avoid infinite loops with zero-width matches
    if (m.index === regex.lastIndex) {
        regex.lastIndex++;
    }
    
    // The result can be accessed through the `m`-variable.
    m.forEach((match, groupIndex) => {
        console.log(`Found match, group ${groupIndex}: ${match}`);
    });
}

Result:

Found match, group 0: 1..10
Found match, group 1: 1
Found match, group 2: 10