File:  [gforth] / gforth / regexp.fs
Revision 1.18: download - view: text, annotated - select for diffs
Sun Sep 5 22:18:54 2010 UTC (13 years, 6 months ago) by pazsan
Branches: MAIN
CVS tags: HEAD
alternatives with backtracking

    1: \ Regexp compile
    2: 
    3: \ Copyright (C) 2005,2006,2007,2008 Free Software Foundation, Inc.
    4: 
    5: \ This file is part of Gforth.
    6: 
    7: \ Gforth is free software; you can redistribute it and/or
    8: \ modify it under the terms of the GNU General Public License
    9: \ as published by the Free Software Foundation, either version 3
   10: \ of the License, or (at your option) any later version.
   11: 
   12: \ This program is distributed in the hope that it will be useful,
   13: \ but WITHOUT ANY WARRANTY; without even the implied warranty of
   14: \ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15: \ GNU General Public License for more details.
   16: 
   17: \ You should have received a copy of the GNU General Public License
   18: \ along with this program. If not, see http://www.gnu.org/licenses/.
   19: 
   20: \ The idea of the parser is the following:
   21: \ As long as there's a match, continue
   22: \ On a mismatch, LEAVE.
   23: \ Insert appropriate control structures on alternative branches
   24: \ Keep the old pointer (backtracking) on the stack
   25: \ I try to keep the syntax as close to a real regexp system as possible
   26: \ All regexp stuff is compiled into one function as forward branching
   27: \ state machine
   28: 
   29: \ special control structure
   30: 
   31: : FORK ( compilation -- orig ; run-time f -- ) \ gforth
   32:     \G AHEAD-like control structure: calls the code after JOIN.
   33:     POSTPONE call >mark ; immediate restrict
   34: : JOIN ( orig -- ) \ gforth
   35:     \G THEN-like control structure for FORK
   36:     postpone THEN ; immediate restrict
   37: 
   38: \ Charclasses
   39: 
   40: : +bit ( addr n -- )  + 1 swap c! ;
   41: : -bit ( addr n -- )  + 0 swap c! ;
   42: : @+ ( addr -- n addr' )  dup @ swap cell+ ;
   43: 
   44: 0 Value cur-class
   45: : charclass ( -- ) \ regexp-cg
   46:     \G Create a charclass
   47:     Create here dup to cur-class $100 dup allot erase ;
   48: : +char ( char -- ) \ regexp-cg
   49:     \G add a char to the current charclass
   50:     cur-class swap +bit ;
   51: : -char ( char -- ) \ regexp-cg
   52:     \G remove a char from the current charclass
   53:     cur-class swap -bit ;
   54: : ..char ( start end -- ) \ regexp-cg
   55:     \G add a range of chars to the current charclass
   56:     1+ swap ?DO  I +char  LOOP ;
   57: : or! ( n addr -- )  dup @ rot or swap ! ;
   58: : and! ( n addr -- )  dup @ rot and swap ! ;
   59: : +class ( class -- ) \ regexp-cg
   60:     \G union of charclass @var{class} and the current charclass
   61:     $100 0 ?DO  @+ swap
   62:     cur-class I + or!  cell +LOOP  drop ;
   63: : -class ( class -- ) \ regexp-cg
   64:     \G subtract the charclass @var{class} from the current charclass
   65:     $100 0 ?DO  @+ swap invert
   66:     cur-class I + and!  cell +LOOP  drop ;
   67: 
   68: : char? ( addr class -- addr' flag )
   69:     >r count r> + c@ ;
   70: 
   71: \ Charclass tests
   72: 
   73: : c? ( addr class -- ) \ regexp-pattern
   74:     \G check @var{addr} for membership in charclass @var{class}
   75:     ]] char? 0= ?LEAVE [[ ; immediate
   76: : -c? ( addr class -- ) \ regexp-pattern
   77:     \G check @var{addr} for not membership in charclass @var{class}
   78:     ]] char?    ?LEAVE [[ ; immediate
   79: 
   80: charclass digit  '0 '9 ..char
   81: charclass blanks 0 bl ..char
   82: \ bl +char #tab +char #cr +char #lf +char ctrl L +char
   83: charclass letter 'a 'z ..char 'A 'Z ..char
   84: charclass any    0 $FF ..char #lf -char
   85: 
   86: : \d ( addr -- addr' ) \ regexp-pattern
   87:     \G check for digit
   88:     ]] digit c?        [[ ; immediate
   89: : \s ( addr -- addr' ) \ regexp-pattern
   90:     \G check for blanks
   91:     ]] blanks c?       [[ ; immediate
   92: : .? ( addr -- addr' ) \ regexp-pattern
   93:     \G check for any single charachter
   94:     ]] any c?          [[ ; immediate
   95: : -\d ( addr -- addr' ) \ regexp-pattern
   96:     \G check for not digit
   97:     ]] digit -c?       [[ ; immediate
   98: : -\s ( addr -- addr' ) \ regexp-pattern
   99:     \G check for not blank
  100:     ]] blanks -c?      [[ ; immediate
  101: : ` ( "char" -- ) \ regexp-pattern
  102:     \G check for particular char
  103:     ]] count [[  char ]] Literal <> ?LEAVE [[ ;  immediate
  104: : -` ( "char" -- ) \ regexp-pattern
  105:     \G check for particular char
  106:     ]] count [[  char ]] Literal = ?LEAVE [[ ;  immediate
  107: 
  108: \ loop stack
  109: 
  110: Variable loops  $40 3 * cells allot
  111: : 3@ ( addr -- a b c )  dup >r 2 cells + @ r> 2@ ;
  112: : 3! ( a b c addr -- )  dup >r 2! r> 2 cells + ! ;
  113: : loops> ( -- addr ) -3 loops +!  loops @+ swap cells + 3@ ;
  114: : >loops ( addr -- ) loops @+ swap cells + 3! 3 loops +! ;
  115: : BEGIN, ( -- )  ]] BEGIN [[ >loops ;
  116: : DONE, ( -- )  loops @ IF  loops> ]] DONE [[ THEN ]] noop [[ ;
  117: 
  118: \ variables
  119: 
  120: Variable vars   &18 cells allot
  121: Variable varstack 9 cells allot
  122: Variable varsmax
  123: : >var ( -- addr ) vars @+ swap 2* cells +
  124:     vars @ varstack @+ swap cells + !
  125:     1 vars +! 1 varstack +! ;
  126: : var> ( -- addr ) -1 varstack +!
  127:     varstack @+ swap cells + @
  128:     1+ 2* cells vars + ;
  129: 
  130: \ start end
  131: 
  132: 0 Value end$
  133: 0 Value start$
  134: : !end ( addr u -- addr )  over + to end$ dup to start$ ;
  135: : end-rex? ( addr -- addr flag ) dup end$ u< ;
  136: : start-rex? ( addr -- addr flag ) dup start$ u> ;
  137: : ?end ( addr -- addr ) ]] dup end$ u> ?LEAVE [[ ; immediate
  138: 
  139: \ start and end
  140: 
  141: : \^ ( addr -- addr ) \ regexp-pattern
  142:     \G check for string start
  143:     ]] start-rex? ?LEAVE [[ ; immediate
  144: : \$ ( addr -- addr ) \ regexp-pattern
  145:     \G check for string end
  146:     ]] end-rex? ?LEAVE [[ ; immediate
  147: 
  148: \ A word for string comparison
  149: 
  150: : ,=" ( addr u -- ) tuck ]] dup SLiteral tuck compare ?LEAVE Literal + noop [[ ;
  151: : =" ( <string>" -- ) \ regexp-pattern
  152:     \G check for string
  153:     '" parse ,=" ; immediate
  154: 
  155: \ regexp block
  156: 
  157: \ FORK/JOIN are like AHEAD THEN, but producing a call on AHEAD
  158: \ instead of a jump.
  159: 
  160: : (( ( addr u -- ) \ regexp-pattern
  161:     \G start regexp block
  162:     vars off varsmax off loops off
  163:     ]] FORK  AHEAD BUT JOIN !end [[ BEGIN, ; immediate
  164: : )) ( -- addr f ) \ regexp-pattern
  165:     \G end regexp block
  166:     ]] ?end drop true EXIT [[
  167:     DONE, ]] drop false EXIT THEN [[ ; immediate
  168: 
  169: \ greedy loops
  170: 
  171: \ Idea: scan as many characters as possible, try the rest of the pattern
  172: \ and then back off one pattern at a time
  173: 
  174: : drops ( n -- ) 1+ cells sp@ + sp! ;
  175: 
  176: : {** ( addr -- addr addr ) \ regexp-pattern
  177:     \G greedy zero-or-more pattern
  178:     0 ]] Literal >r BEGIN dup [[ BEGIN, ; immediate
  179: ' {** Alias {++ ( addr -- addr addr ) \ regexp-pattern
  180:     \G greedy one-or-more pattern
  181:     immediate
  182: : n*} ( sys n -- ) \ regexp-pattern
  183:     \G At least @var{n} pattern
  184:     >r ]] r> 1+ >r end-rex? 0= UNTIL dup [[ DONE, ]] drop [[
  185:     r@ IF r@ ]] r@ Literal u< IF  r> 1+ drops false  EXIT  THEN [[ THEN
  186:     r@ ]] r> 1+ Literal U+DO FORK BUT [[
  187:     ]] IF  I' I - [[ r@ 1- ]] Literal + drops true UNLOOP EXIT  THEN  LOOP [[
  188:     r@ IF  r@ ]] Literal drops [[ THEN
  189:     rdrop ]] false  EXIT  JOIN [[ ; immediate
  190: : **} ( sys -- ) \ regexp-pattern
  191:     \G end of greedy zero-or-more pattern
  192:     0 postpone n*} ; immediate
  193: : ++} ( sys -- ) \ regexp-pattern
  194:     \G end of greedy zero-or-more pattern
  195:     1 postpone n*} ; immediate
  196: 
  197: \ non-greedy loops
  198: 
  199: \ Idea: Try to match rest of the regexp, and if that fails, try match
  200: \ first expr and then try again rest of regexp.
  201: 
  202: : {+ ( addr -- addr addr ) \ regexp-pattern
  203:     \G non-greedy one-or-more pattern
  204:     ]] BEGIN  [[ BEGIN, ; immediate
  205: : {* ( addr -- addr addr ) \ regexp-pattern
  206:     \G non-greedy zero-or-more pattern
  207:     ]] {+ dup FORK BUT  IF  drop true  EXIT THEN [[ ; immediate
  208: : *} ( addr addr' -- addr' ) \ regexp-pattern
  209:     \G end of non-greedy zero-or-more pattern
  210:     ]] dup end$ u>  UNTIL [[
  211:     DONE, ]] drop false  EXIT  JOIN [[ ; immediate
  212: : +} ( addr addr' -- addr' ) \ regexp-pattern
  213:     \G end of non-greedy one-or-more pattern
  214:     ]] dup FORK BUT  IF  drop true  EXIT [[
  215:     DONE, ]] drop false  EXIT  THEN *} [[ ; immediate
  216: 
  217: : // ( -- ) \ regexp-pattern
  218:     \G search for string
  219:     ]] {* 1+ *} [[ ; immediate
  220: 
  221: \ alternatives
  222: 
  223: \ idea: try to match one alternative and then the rest of regexp.
  224: \ if that fails, jump back to second alternative
  225: 
  226: : JOINs ( sys -- )  BEGIN  dup  WHILE  ]] JOIN [[  REPEAT  drop ;
  227: 
  228: : {{ ( addr -- addr addr ) \ regexp-pattern
  229:     \G Start of alternatives
  230:     0 ]] dup BEGIN [[  vars @ ; immediate
  231: : || ( addr addr -- addr addr ) \ regexp-pattern
  232:     \G separator between alternatives
  233:     vars @ varsmax @ max varsmax !
  234:     ]] dup FORK  IF  2drop true  EXIT THEN  drop dup [[ >r >r >r vars !
  235:     ]] DONE drop dup [[ r> r> r> ]] BEGIN [[ vars @ ; immediate
  236: : }} ( addr addr -- addr addr ) \ regexp-pattern
  237:     \G end of alternatives
  238:     vars @ varsmax @ max vars !
  239:     ]] dup FORK  IF  2drop true  EXIT THEN  drop dup [[ >r >r >r drop
  240:     ]] DONE drop LEAVE [[ r> r> r> JOINs ; immediate
  241: 
  242: \ match variables
  243: 
  244: : \( ( addr -- addr ) \ regexp-pattern
  245:     \G start of matching variable; variables are referred as \\1--9
  246:     ]] dup [[
  247:     >var ]] ALiteral ! [[ ; immediate
  248: : \) ( addr -- addr ) \ regexp-pattern
  249:     \G end of matching variable
  250:     ]] dup [[
  251:     var> ]] ALiteral ! [[ ; immediate
  252: : \0 ( -- addr u ) \ regexp-pattern
  253:     \G the whole string
  254:     start$ end$ over - ;
  255: : \: ( i -- )
  256:     Create 2* 1+ cells vars + ,
  257:   DOES> ( -- addr u ) @ 2@ tuck - ;
  258: : \:s ( n -- ) 0 ?DO  I \:  LOOP ;
  259: 9 \:s \1 \2 \3 \4 \5 \6 \7 \8 \9
  260: 
  261: \ replacements, needs string.fs
  262: 
  263: require string.fs
  264: 
  265: 0 Value >>ptr
  266: 0 Value <<ptr
  267: Variable >>string
  268: : s>>  ( addr -- addr ) \ regexp-replace
  269:     \G Start replace pattern region
  270:     dup to >>ptr ;
  271: : << ( run-addr addr u -- run-addr ) \ regexp-replace
  272:     \G Replace string from start of replace pattern region with
  273:     \G @var{addr} @var{u}
  274:     <<ptr >>ptr over - >>string $+!
  275:     >>string $+! dup to <<ptr ;
  276: : <<" ( "string<">" -- ) \ regexp-replace
  277:     \G Replace string from start of replace pattern region with
  278:     \G @var{string}
  279:     '" parse postpone SLiteral postpone << ; immediate
  280: : >>string@ ( -- addr u )
  281:     >>string $@ ;
  282: : >>string0 ( addr u -- addr u )  s" " >>string $!
  283:     0 to >>ptr  over to <<ptr ;
  284: : >>next ( -- addr u ) <<ptr end$ over - ;
  285: : >>rest ( -- ) >>next >>string $+! ;
  286: : s// ( addr u -- ptr )
  287:     \G start search/replace loop
  288:     ]] >>string0 (( // s>> [[ ; immediate
  289: : >> ( addr -- addr )
  290:     ]] <<ptr >>ptr u> ?LEAVE ?end [[ ; immediate
  291: : //s ( ptr -- )
  292:     \G search end
  293:     ]] )) drop >>rest >>string@ [[ ; immediate
  294: : //o ( ptr addr u -- addr' u' )
  295:     \G end search/replace single loop
  296:     ]] << //s [[ ; immediate
  297: : //g ( ptr addr u -- addr' u' )
  298:     \G end search/replace all loop
  299:     ]] << LEAVE //s [[ ; immediate

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>