dmaevsky/rd-parse

Simple example using Y combinator?

rapodaca opened this issue · 4 comments

rapodaca commented

I'd like to implement a grammar that I think requires recursion.

The input "a(b(c)d)e" should produce:

 [
  [
    "a"
  ],
  [
    "(",
    [
      [
        "b"
      ],
      [
        "(",
        [
          [
            "c"
          ]
        ],
        ")"
      ],
      [
        "d"
      ]
    ],
    ")"
  ],
  [
    "e"
  ]
]

My grammar so far is:

const grammar = function (token, all, any, plus, optional, node) {
  let open = token(/(\()/g, 'open');
  let close = token(/(\))/g, 'close');
  let letter = token(/([a-z])/g, 'letter');
  
  let run = Y(function (thisRun) {
    return node(any(plus(letter), all(open, thisRun, close)), reduceRun);
  });
  let line = node(plus(run), reduceLine)

  return line;
};

const Y = function (gen) {
  return (function(f) {return f(f)})( function(f) {
    return gen(function() {return f(f).apply(null, arguments)});
  });
};

const reduceRun = (run) => {
  return run.map((u) => {
    return u;
  });
};

const reduceLine = (line) => {
  return line;
};

module.exports = grammar;

I use the grammar like this:

const Parser = require('rd-parse');
const grammar = require('./grammar');

let input = 'a(b(c)d)e';
let p = new Parser(grammar);
let ast = p.parse(input);

console.log(JSON.stringify(ast, null, 2));

Instead of the output I'm after, this code fails with the error: "Error: Parsing failed"

How can I fix this problem? Alternatively, are there any examples illustrating how (and why) to use the Y combinator?

The documentation refers to the examples, but I'm not able to see why my code fails from them.

rapodaca commented

I noticed this modified grammar does the job:

const grammar = function (token, all, any, plus, optional, node) {
  let open = token(/(\()/g, 'open');
  let close = token(/(\))/g, 'close');
  let letter = token(/([a-z])/g, 'letter');
  
  return Y(function (thisGrammar) {
    let run = node(any(plus(letter), all(open, thisGrammar, close)), reduceRun);
    let line = node(plus(run), reduceLine);

    return line;
  });
};

const Y = function (gen) {
  return (function(f) {return f(f)})( function(f) {
    return gen(function() {return f(f).apply(null, arguments)});
  });
};

const reduceRun = (run) => {
  return run.map((u) => {
    return u;
  });
};

const reduceLine = (line) => {
  return line;
};

module.exports = grammar;

However, it appears to require recursion over the entire grammar. Is it possible to define recursion over a more limited set of grammar rules as I originally tried?

dmaevsky commented
rapodaca commented

Thanks for taking a look. You're right, and I have a much better handle on how to use rd-parse now. The y combinator part also makes sense, and I ended up going with something similar to my second example.

dmaevsky commented

Glad to hear that it works for you!