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

Groups > comp.lang.forth > #40172 > unrolled thread

Recognizers; review

Back to article view | Back to comp.lang.forth

Contents

  Recognizers; review "Alex McDonald" <blog@rivadpm.com> - 2015-06-30 22:43 +0100
    Re: Recognizers; review Matthias Trute <matthias.trute@gmail.com> - 2015-07-01 12:28 -0700
      Re: Recognizers; review "Alex McDonald" <blog@rivadpm.com> - 2015-07-05 07:41 +0100

#40172 — Recognizers; review

on 26/06/2015 18:06:28, "Alex McDonald" wrote:
> on 24/06/2015 15:08:47, Bernd Paysan wrote:
>> Bernd Paysan wrote:
>>>> Any volunteers to contribute one for VFX ? One could use the
>>>> CUNDEFINED hook that is not documented ...
>>
>> Ok, here's a recognizer implementation for VFX, using the typical
>> internals of VFX for the standard interpreter. Postpone mode is almost
>> for free. Line Gforth, you can now use >R and R> (matched within a
>> line) in the text interpreter, something that doesn't work in VFX with
>> the normal text interpreter.
>>

I've implemented a rough & ready version of this in my Forth. 

>> Recognizers for other things like real string literals and TO
>> replacement will follow.
>>
>> ----------------------recognizer.fth----------------------
>> \ recognizer for VFX
>>
>> \ postpone mode
>>
>>: ]] -2 state ! ; immediate
>>: [[ ; immediate comp: drop -1 state ! discard-sinline ;
>>
>> \ word recognizer
>>
>>: recognizer: ( xtint xtcomp xtpost "name" -- )
>> Create rot , swap , , ;
>>
>> ' undefined dup dup recognizer: r:fail
>>
>>: post, ( xt -- ) clit, postpone compile, ;
>>
>> ' execute ' compile, ' post, recognizer: r:word
>> ' execute ' execute ' compile, recognizer: r:immediate
>>
>>: rec:word ( addr u -- xt r:word | r:fail )
>> \ Searches a word in the wordlist stack
>> here place here find dup 0= IF  2drop r:fail
>> ELSE  0< IF  r:word  ELSE  r:immediate  THEN THEN ;
>>
>> \ num recognizer
>>
>>: xlit, ( x1 .. xn n -- ) dup 0< IF  c#fliteral  ELSE  c#literal  THEN ;
>>
>> ' drop ' xlit, :noname dup >r xlit, r> clit, postpone xlit, ;
>> recognizer: r:num
>>
>>: rec:num ( addr u -- n 1 r:num | d 2 r:num | r: -2 r:num | r:fail )
>> pad place pad donumber? dup IF  r:num  ELSE  drop r:fail  THEN ;
>>
>> \ generic stack get/set
>>
>> $10 Constant max-stack#
>>
>>: get-stack ( rec-addr -- xt1 .. xtn n )
>> dup @ 0= IF  @  EXIT  THEN
>> dup swap @ dup >r cells bounds 1 cells - swap DO
>> I @
>> cell negate +LOOP  r> ;
>>
>>: set-stack ( xt1 .. xtn n rec-addr -- )
>> over max-stack# u>= abort" Too many items"
>> 2dup ! cell+ swap cells bounds ?DO
>> I !
>> cell +LOOP ;
>>
>> \ recognizer stack
>>
>> max-stack# 1+ cells buffer: forth-recognizer
>>
>>: get-recognizers ( -- xt1 .. xtn n )
>> \ push the content on the recognizer stack
>> forth-recognizer get-stack ;
>>: set-recognizers ( xt1 .. xtn n )
>> \ set the recognizer stack from content on the stack
>> forth-recognizer set-stack ;
>>
>> ' rec:num ' rec:word 2 set-recognizers

The recognizer stack -- or rather, the use of a stack -- need some work &
understanding of how it can be extended. This is unlike wordlist
behaviour, since what is pushed on the stack gets searched last, not
first; it's more like an ordered list held as an array than a stack.

>>
>> \ recognizer loop
>>
>>: map-recognizer ( addr u rec-addr -- tokens table )
>> \ apply a recognizer stack to a string, delivering a token
>> dup cell+ swap @ cells bounds ?DO
>> 2dup I -rot 2>r
>> @ execute dup r:fail <>  IF
>> 2r> 2drop UNLOOP  EXIT
>> THEN  drop 2r>
>> cell +LOOP
>> 2drop r:fail ;

We could put 

: REC:FAIL R:FAIL ; 

on the "bottom" of the stack, and use 0 (FALSE) rather than R:FAIL to
indicate failure from REC:xxx routines.

>>
>>: do-recognizer ( addr u -- tokens xt )
>> \ process the string @var{addr u} in the recognizer stack
>> forth-recognizer map-recognizer ;
>>
>> \ toplevel
>>
>>: parser ( addr u -- .. xt )
>> do-recognizer state @ negate cells + @ ;
>>
>>: (interpret)
>> BEGIN  ?stack parse-name dup
>> WHILE  parser execute
>> REPEAT 2drop ;
>>
>> ' (interpret) is interpret
>> ----------------------recognizer.fth----------------------
>>
> 
> For smart-compile and avoiding FIND and immediacy we can have with
> FIND-NAME (ala gforth);
> 
>:noname name>interpret execute ;
>:noname name>compile   execute ;
>:noname name>compile   swap postpone literal compile, ;
> recognizer: r:word
> 
>: rec:word ( addr u -- xt r:word | r:fail )
> find-name ?dup if r:word else r:fail then ;
> 
> This removes R:IMMEDIATE. I've now got this working for parts of my
> compiler. It really is quite simple and effective; I'm going to extend
> it to the whole compiler this weekend. My only concern is the
> unbalanced stack returns; <n items> R:something vs R:FAIL. qv
> REC:WORD.
> 

Based on the above use of NAME>xxx, [[ and ]] don't work since [[ doesn't
get out of POSTPONE mode. It needs to be "super-IMMEDIATE" since it needs
to execute, and

:noname name>compile   swap postpone literal compile, ;

doesn't allow it to execute. Special casing it might involve having ]]
add REC:[[ which removes itself.

[toc] | [next] | [standalone]

#40210

A few notes from my side

> >> ' rec:num ' rec:word 2 set-recognizers
> 
> The recognizer stack -- or rather, the use of a stack -- need some work &
> understanding of how it can be extended. 

That's specified in the RFD

"SET-RECOGNIZERS ( rec-n .. rec-1 n -- ) RECOGNIZER
Set the recognizer stack to the recognizers identified by the execution tokens of their parsing words rec-n .. rec-1. rec-1 will be the parsing word of the recognizer that is called first, rec-n will be the last one."

Thus the top-level entry is used first. If the code you cited does something
else, well, that would be a bug.

> This is unlike wordlist
> behaviour,

A wordlist can only be changed by appending to it (ignoring MARKER for simplicity). It would be really cruel to insert an entry somewhere 
in the middle of it as well. So I think that a wordlist is not the
right model to follow. An array (or list) in general would be
un-forthy, an implementer can use them internally much like I did in
the RFD reference implementation.

> We could put 
> 
> : REC:FAIL R:FAIL ; 
> 
> on the "bottom" of the stack, and use 0 (FALSE) rather than R:FAIL to
> indicate failure from REC:xxx routines.

I have had such a terminating entry in the first recognizer version. It
turned out,  that this needs more code and generates some more possibilities
for errors with no benefit. Re-using the r:fail as a binary flag is disputable,
but I think that the dual use of flag *and* action table makes the do-recognizer
shorter while still easy to understand.

> 
> Based on the above use of NAME>xxx, [[ and ]] don't work since [[ doesn't
> get out of POSTPONE mode. It needs to be "super-IMMEDIATE" since it needs
> to execute, and
> 
> :noname name>compile   swap postpone literal compile, ;
> 
> doesn't allow it to execute. Special casing it might involve having ]]
> add REC:[[ which removes itself.

[[ and ]] are not part of the forth standard, making it difficult to 
handle them in an RFD. Using recognizers to get them is cool indeed.

[toc] | [prev] | [next] | [standalone]

#40295

on 01/07/2015 20:28:19, Matthias Trute wrote:

Thanks for your comments. I'll reply later this week when I have
experimented a bit more.

> A few notes from my side
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web