[<<][compsci][>>][..]
Wed Jul 5 22:25:34 EDT 2017

Manual parser

So I ended up writing a manual recursive parser.  I had to resort to a
hack to be able to solve the equal infix operator, which is patched at
two places: close and atom.

%% I: input
%% Q: current queue
%% S: stack of queues
p([open    |I], Q,          S)               -> p(I, [],             [Q|S]);
p([close   |I], Q1,         [[{eq,K}|Q2]|S]) -> p(I, [{K,r(Q1)}|Q2], S);
p([close   |I], Q1,         [Q2|S])          -> p(I, [r(Q1)|Q2],     S);
p([{atom,V}|I], [{eq,K}|Q], S)               -> p(I, [{K,V}|Q],      S);
p([{atom,A}|I], Q,          S)               -> p(I, [A|Q],          S);
p([equal   |I], [K|Q],      S)               -> p(I, [{eq,K}|Q],     S);
p([comma   |I], Q,          S)               -> p(I, Q,              S);  %% (1)
p([],           Q,          [])              -> r(Q);


So equal quite literally changes the meaning of the last object parsed.

It also changes the continuation: we're no longer putting the result
in the queue, but in the second slot of the pair.

{Q,S} is a represetnation of the continuation.

S is always a stack of Qs, but there are two kinds of Qs:
- list     the hole at the end of a list
- {eq,K}   the hole in the second slot of the pair

The rules likely become simpler if the continuations are made
abstract.  Let's give that a try.

{Q,S} -> {[],[Q,S]}

I find CPS hard.  Maybe it's just lack of training, but making that
translation really doesn't come naturally.

Initial Q=[], S=[]


This is a push to a list, which as an ordinary function is:
fun(V) -> [A|V] end

What I miss is muscle memory..


Functions in CPS form look like this (e.g. the Haskell do block):

(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

(define (pyth& x y k)
 (*& x x (lambda (x2)
 (*& y y (lambda (y2)
 (+& x2 y2 (lambda (x2py2)
 (sqrt& x2py2 k))))))))


Note that the only reason to use CPS is to be able to also pass the
input as part of the state using just tail recursion.

So here's a systematic approach:
- write a recursive parser in direct style
- convert it to CPS mechanically
- add the extra input argument

So in erlang it is actually not necessary to write it in CPS, because
the input can be abstracted away into a read() call by using another
process.

But it's nice to keep things pure of course..


EDIT: actually, this needs some form of back-patching for "=" unless
that is changed to do it directly.




[Reply][About]
[<<][compsci][>>][..]