Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3117

Re: Parser combinators

Show all headers | View raw

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:
> > [luser droog <luser.droog@gmail.com>, 2017-06-12 21:19]
> > > On Sunday, June 11, 2017 at 1:36:15 AM UTC-5, luser droog wrote:
> > > > I've got a better one now. The idea is it's a sequence. In my
> > > > builder notation,
> > > > 
> > > >   [ x ]
> > > > 
> > > > where x is whatever, the input parser to this combinator. 
> > > > This is the zero-or-more quantifier, so there may be matching
> > > > input but if not, the matcher still succeeds.
> > > > 
> > > >   << [ x ] true >>
> > > > 
> > > > Then we stitch this into a loop by inserting the whole matcher
> > > > into the inner sequence.
> > > > 
> > > >   y = <<[ x y ] true>>
> > > > 
> > > > And it works!
> > > >   
> > > 
> > > It came up in the comp.lang.c thread that this is not the usual
> > > behavior of BNF quantifiers. There's no backtracking so a greedy
> > > quantifier with this program is also "possessive". So with 
> > > something like
> > > 
> > >     (x) term some
> > >     (xy) term alt
> > > 
> > > which corresponds to the regex
> > > 
> > >     x+xy
> > > 
> > > the 'x+' consumes all 'x's that may be present, and the 'xy' part
> > > will never match.
> > > 
> > > I may not be able to fix this quickly or easily. Need to rethink
> > > the whole deal.
> > 
> > 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.

Norah@laptop ~
$ cat pc5.ps
<<
    /spill   {{}forall}
    /curry   {[zxy spill]}
    /combine {2 | {spill}map}
    /map     {[zxy  forall]}
    /reduce  {y 0 get zxy 1 tail zy forall}
    /head {0 zy getinterval}
    /tail {y # y sub getinterval}
    /is  {y type eq}
    /|   {array astore}
    /#   {length}
    /y   {1 index}
    /xyz pop
    /zxy {3 1 roll}
    /yzx {3 2 roll}
     /zy {exch}

    /pass   {# 1 | zy pop}
    /fail   {pop pop { } }
    /failed {dup # 0 gt}
    /passed {failed not}

    /test { y #  y #  lt         {  fail  }{    % (input) (seek)
            2 copy # head  y  eq {  pass  }{  fail  } ifelse
            } ifelse }  % [] | [#]

    /term { /test cvx 2 | cvx }
    /alt {
        {dup} yzx combine               % p2 {dup p1}                   % (input) [?1]
        {exch} combine zy combine       % p2 {dup p1 exch p2}           % [?1] [?2]
        {combine} combine cvx }         % {dup p1 exch p2 combine}      % [?12]
    /seq {
        {dup} yzx combine                       % p2 {dup p1}                   % (input) [?1]
        {zy} combine                            % p2 {dup p1 zy}                % [?1] (input)
        { zy tail } yzx combine cvx             % {dup p1 zy} {zy tail p2}      % [?1] (input) {zy tail p2}
        {curry cvx map{spill}map} curry combine cvx } %{dup p1 zy{zy tail p2}curry map{spill}map}   % [?2]
    /ps {pstack / =} /pc {ps clear}
>> begin
%/forall { pstack/ = forall } bind def

(x) (x) term exec pc
(x) (x) term (y) term alt exec pc
(xy) (x) term (y) term seq exec pc

quit

Norah@laptop ~
$ gsnd -q pc5.ps
[1]

[1]

[1]


Norah@laptop ~
$ 

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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