Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.postscript > #3119
| Newsgroups | comp.lang.postscript |
|---|---|
| Date | 2017-06-13 23:28 -0700 |
| References | (9 earlier) <f27c0490-4a15-4a50-9d2b-40ab28664e5e@googlegroups.com> <20170613074059.02058fe1@samara.DOMA> <6d6a42eb-737a-4bf1-b1ad-3eb333221deb@googlegroups.com> <6776d1fc-7baa-4684-8bfe-d497fe8379ea@googlegroups.com> <e2371211-86ec-4644-bb05-cf79f483cde9@googlegroups.com> |
| Message-ID | <bd76de61-cb0b-4004-9702-ec94a5eae4d3@googlegroups.com> (permalink) |
| Subject | Re: Parser combinators |
| From | luser droog <luser.droog@gmail.com> |
On Tuesday, June 13, 2017 at 6:22:25 AM UTC-5, luser droog wrote:
> On Tuesday, June 13, 2017 at 5:48:56 AM UTC-5, luser droog wrote:
> > On Tuesday, June 13, 2017 at 3:53:48 AM UTC-5, luser droog wrote:
> > > On Tuesday, June 13, 2017 at 12:41:00 AM UTC-5, Carlos wrote:
> > > > According to https://qntm.org/combinators shouldn't "x+" return a set of
> > > > all matches?
> > > >
> > >
> > > Thanks. That's a nice, short reference. And multiple results seems
> > > like the right answer. I was going mad trying to come up with a
> > > backtracking algorithm. My first version returned [] or [n], but
> > > I didn't understand the purpose or how to use it correctly.
> > >
> >
> > Ok. A better nucleus. None of the fancy stuff. Half-abbreviated.
> > Return values are arrays of matched lengths. alt applies both
> > alternatives and then combines the results. seq applies the
> > right piece to any (each) results from the left piece.
> >
> > Hardest part is commenting these things. I tried giving running
> > stack pictures of the compile-time state and execution of that
> > fragment compiled so far.
> >
>
> Kleene star.
> sleepy.
>
Filled-out the rest of the baggage. And I think I came up with a better
way to document these dynamic procedures. By providing 3 times as much
commentary as the code itself. The regular main-line code has stack
comments leading up the dynamic procedure body in full.
Then, accompanying the function, the dynamic procedure is exploded
with its own running stack comments.
I'm not sure if I've mentioned this, but don't try to view the result
of the /many combinator. Its result is a procedure which recursively
contains itself. So the `==` operator will overflow the execution stack
if it attempts to print it.
Norah@laptop ~
$ cat pc5.ps
<<
/spill {{}forall}
/curry %{/exec cvx 3 |}
{[zxy spill]}
/combine %{2 | {/exec cvx} map}
{2 | {spill}map}
/map {[zxy forall]}
/reduce {y 0 get zxy zy 1 tail zy forall}
/head {0 zy getinterval}
/tail {y # y sub getinterval}
/is {y type eq}
/| {array astore}
/# {length}
/x {2 index}
/y {1 index}
/z {dup}
/xyz pop
/zy {exch}
/zxy {3 1 roll}
/yzx {3 2 roll}
/max {2 copy lt {exch} if pop}
/pass {# 1 | zy pop}
/fail {pop pop { } }
/failed {z # 0 eq}
/passed {failed not}
/next {y tail}
/sum-up {zy {add} curry cvx forall}
/test { y # y # lt { fail }{ % (input) (seek)
2 copy # head y eq { pass }{ fail } ifelse
} ifelse } % [] | [#]
/term { /test cvx 2 | cvx }
/alt {
% { % (input)
% z % (input) (input)
% p1 zy % [?1] (input)
% p2 % [?1] [?2]
% combine % [?1 ?2]
% }
{z} yzx combine % p2 [z p1]
{zy} combine zy combine % p2 [z p1 zy p2]
{combine} combine cvx } % {z p1 zy p2 combine}
/seq {
% { % (input)
% z % (input) (input)
% p1 zy % [?1] (input)
% {next p2 sum-up} curry cvx % [?1] {(input) next p2 sum-up}
% map % [#1+?2]
% }
% { % #1
% (input) next={y tail} % #1 (nput)
% p2 % #1 [?2]
% sum-up={
% zy {add} curry cvx % [?2] {#1 add}
% forall % #1+?2*
% }
% }
{z} yzx combine % p2 [z p1]
{zy} combine % p2 [z p1 zy]
{next} yzx combine % [z p1 zy] [next p2]
{sum-up} combine cvx % [z p1 zy] {next p2 sum-up}
{curry cvx map} curry combine cvx } % {z p1 zy{next p2 sum-up}curry cvx map}
/many { % x => y = << [ x y ] true >>
{{{}exec}exec} z 0 get zxy seq maybe
2 copy 0 zy put zy pop }
/some { z many seq }
/maybe { {()pass} alt }
/build-parser-action {
% {
% z parser passed {
% {max} reduce 2 copy head action tail
% }{
% /parser-fail = ps
% } ifelse
% }
zy build-parser {z} zy combine
{passed} combine
{{max} reduce 2 copy head} yzx combine
{tail} combine cvx
{{/parser-fail = ps}ifelse} curry combine cvx }
/build-parser {
/stringtype is { term }{
/arraytype is { build-seq }{
/dicttype is { build-alt }{
/booleantype is { build-bool }{ } ifelse } ifelse } ifelse } ifelse }
/build-seq { z xcheck { }{ {build-parser} map {seq} reduce } ifelse }
/build-alt { {} map {fix-up} map bubble {build-parser} map {alt} reduce }
/build-bool { {()pass} {()fail} ifelse }
/fix-up {
/nulltype is { pop }{
/nametype is { z # string cvs }{ } ifelse } ifelse }
/bubble { { z sorted {exit} if [ zy {2 copy comp {exch} if} reduce ] } loop }
/sorted { true zy {2 copy comp {pop pop pop false 0 exit} if exch pop} reduce pop }
/comp { switch? x type get y type get exec }
/switch? <<
/arraytype << /arraytype { arrcomp }
/stringtype { pop pop false }
/dicttype { pop pop false }
/booleantype { pop pop false } >>
/stringtype << /arraytype { pop pop true }
/stringtype { gt }
/dicttype { pop pop false }
/booleantype { pop pop false } >>
/dicttype << /arraytype { pop pop true }
/stringtype { pop pop true }
/dicttype { pop pop false }
/booleantype { pop pop false } >>
/booleantype << /arraytype { pop pop true }
/stringtype { pop pop true }
/dicttype { pop pop true }
/booleantype { pop pop false } >> >>
/arrcomp { y xcheck { dup xcheck { pop pop false }{ pop pop false } ifelse }{
dup xcheck { pop pop true }{ pop pop false } ifelse } ifelse }
/ps {pstack/ =} /pc {ps clear} /pq {ps quit}
>> begin
(>>) [ {counttomark 2 mod 1 eq {null} if} spill counttomark 1 add index load ] cvx def
%/forall { pstack/ = forall } bind def
%/getinterval { ps getinterval } bind def
(x) () term exec pc
(x) (x) term exec pc
(x) (x) term (y) term alt exec pc
(xy) (x) term (y) term seq exec pc
(xxxxy) (x) term many exec pc
(xxxxy) (x) term many (xy) term seq exec pc
<< (x) (y) >> build-parser pc
/xy << (x) (y) >> {
==
} build-parser-action ps def
(x) xy pc
(y) xy pc
pq
Norah@laptop ~
$ gsnd -q pc5.ps
[0]
[1]
[1]
[2]
[4 3 2 1 0]
[5]
{z (x) test zy (y) test combine}
{z z (x) test zy (y) test combine passed {{max} reduce 2 copy head == tail} {/parser-fail = ps} ifelse}
/xy
(x)
()
(y)
()
Norah@laptop ~
$
Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Parser combinators luser droog <luser.droog@gmail.com> - 2017-05-28 21:22 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-03 15:15 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-04 11:13 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-04 18:57 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-04 19:39 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-06 23:38 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-08 22:18 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-09 14:54 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-10 23:36 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-12 21:19 -0700
Re: Parser combinators Carlos <carlos@cvkm.cz> - 2017-06-13 07:40 +0200
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-13 01:53 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-13 03:48 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-13 04:22 -0700
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-13 23:28 -0700
Re: Parser combinators Carlos <carlos@cvkm.cz> - 2017-06-14 21:52 +0200
Re: Parser combinators luser droog <luser.droog@gmail.com> - 2017-06-15 13:36 -0700
csiph-web