File:  [gforth] / gforth / regexp.fs
Revision 1.31: download - view: text, annotated - select for diffs
Tue Dec 28 23:54:34 2010 UTC (8 years, 7 months ago) by pazsan
Branches: MAIN
CVS tags: HEAD
Added copyright date

    1: \ Regexp compiler
    2: 
    3: \ Copyright (C) 2005,2006,2007,2008,2010 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 [[ ELSE ." no done left!" cr THEN ;
  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: Variable greed-counts  9 cells allot \ no more than 9 nested greedy loops
  130: : greed' ( -- addr )  greed-counts dup @ + ;
  131: 
  132: \ start end
  133: 
  134: 0 Value end$
  135: 0 Value last$
  136: 0 Value start$
  137: : !end ( addr u -- addr )  over + to end$ dup to start$ ;
  138: : end-rex? ( addr -- addr flag ) dup end$ u< ;
  139: : start-rex? ( addr -- addr flag ) dup start$ u> ;
  140: : ?end ( addr -- addr ) ]] dup end$ u> ?LEAVE [[ ; immediate
  141: : rest$ ( addr -- addr addr u ) dup end$ over - ;
  142: : >last ( addr -- flag )  dup to last$ end$ u<= ;
  143: 
  144: \ start and end
  145: 
  146: : \^ ( addr -- addr ) \ regexp-pattern
  147:     \G check for string start
  148:     ]] start-rex? ?LEAVE [[ ; immediate
  149: : \$ ( addr -- addr ) \ regexp-pattern
  150:     \G check for string end
  151:     ]] end-rex? ?LEAVE [[ ; immediate
  152: 
  153: \ A word for string comparison
  154: 
  155: : (str=?) ( addr1 addr u -- addr2 )
  156:     dup >r 2>r rest$ r@ umin 2r> compare IF rdrop true ELSE r> + false THEN ;
  157: : str=? ( addr1 addr u -- addr2 ) ]] (str=?) ?LEAVE [[ ; immediate
  158: : ,=" ( addr u -- ) tuck dup ]] rest$ Literal umin SLiteral compare ?LEAVE Literal + [[ ;
  159: : =" ( <string>" -- ) \ regexp-pattern
  160:     \G check for string
  161:     '" parse ,=" ; immediate
  162: 
  163: \ regexp block
  164: 
  165: \ FORK/JOIN are like AHEAD THEN, but producing a call on AHEAD
  166: \ instead of a jump.
  167: 
  168: : (( ( addr u -- ) \ regexp-pattern
  169:     \G start regexp block
  170:     vars off varsmax off loops off greed-counts off
  171:     ]] FORK  AHEAD BUT JOIN !end [[ BEGIN, ; immediate
  172: : )) ( -- flag ) \ regexp-pattern
  173:     \G end regexp block
  174:     ]] >last  ;S [[
  175:     DONE, ]] drop false ;S THEN [[ ; immediate
  176: 
  177: \ greedy loops
  178: 
  179: \ Idea: scan as many characters as possible, try the rest of the pattern
  180: \ and then back off one pattern at a time
  181: 
  182: : drops ( n -- ) 1+ cells sp@ + sp! ;
  183: 
  184: : {** ( addr -- addr addr ) \ regexp-pattern
  185:     \G greedy zero-or-more pattern
  186:     ]] false >r BEGIN  dup  FORK  BUT  WHILE  last$ r> 1+ >r  REPEAT [[
  187:     ]] r>  AHEAD  BUT  JOIN [[
  188:     BEGIN, ; immediate
  189: ' {** Alias {++ ( addr -- addr addr ) \ regexp-pattern
  190:     \G greedy one-or-more pattern
  191:     immediate
  192: : **} ( sys -- ) \ regexp-pattern
  193:     \G end of greedy zero-or-more pattern
  194:     ]] >last  ;S [[ DONE, ]] drop false ;S  THEN [[
  195:     ]] 1+ false  U+DO  FORK BUT [[
  196:     ]] IF  I' I - 1- drops UNLOOP  true ;S  THEN  LOOP [[
  197:     ]] false ;S JOIN [[ ; immediate
  198: : ++} ( sys -- ) \ regexp-pattern
  199:     \G end of greedy zero-or-more pattern
  200:     ]] >last  ;S [[ DONE, ]] drop false ;S  THEN [[
  201:     ]] false  U+DO  FORK BUT [[
  202:     ]] IF  I' I - drops UNLOOP  true ;S  THEN  LOOP [[
  203:     ]] drop false ;S JOIN [[ ; immediate
  204: 
  205: \ non-greedy loops
  206: 
  207: \ Idea: Try to match rest of the regexp, and if that fails, try match
  208: \ first expr and then try again rest of regexp.
  209: 
  210: : {+ ( addr -- addr addr ) \ regexp-pattern
  211:     \G non-greedy one-or-more pattern
  212:     ]] BEGIN  [[ BEGIN, ; immediate
  213: : {* ( addr -- addr addr ) \ regexp-pattern
  214:     \G non-greedy zero-or-more pattern
  215:     ]] {+ dup FORK BUT  IF  drop true  ;S THEN [[ ; immediate
  216: : *} ( addr addr' -- addr' ) \ regexp-pattern
  217:     \G end of non-greedy zero-or-more pattern
  218:     ]] dup end$ u>  UNTIL [[
  219:     DONE, ]] drop false  ;S  JOIN [[ ; immediate
  220: : +} ( addr addr' -- addr' ) \ regexp-pattern
  221:     \G end of non-greedy one-or-more pattern
  222:     ]] dup FORK BUT  IF  drop true  ;S [[
  223:     DONE, ]] drop false  ;S [[ BEGIN, ]] THEN *} [[ ; immediate
  224: 
  225: : // ( -- ) \ regexp-pattern
  226:     \G search for string
  227:     ]] {* 1+ *} [[ ; immediate
  228: 
  229: \ alternatives
  230: 
  231: \ idea: try to match one alternative and then the rest of regexp.
  232: \ if that fails, jump back to second alternative
  233: 
  234: : THENs ( sys -- )  BEGIN  dup  WHILE  ]] THEN [[  REPEAT  drop ;
  235: 
  236: : {{ ( addr -- addr addr ) \ regexp-pattern
  237:     \G Start of alternatives
  238:     0 ]] dup FORK  IF  drop true ;S  BUT  JOIN [[ vars @ ; immediate
  239: : || ( addr addr -- addr addr ) \ regexp-pattern
  240:     \G separator between alternatives
  241:     vars @ varsmax @ max varsmax !  vars !
  242:     ]] AHEAD  BUT  THEN  [[
  243:     ]] dup FORK  IF  drop true ;S  BUT  JOIN [[ vars @ ; immediate
  244: : }} ( addr addr -- addr ) \ regexp-pattern
  245:     \G end of alternatives
  246:     vars @ varsmax @ max vars !  drop
  247:     ]] AHEAD  BUT  THEN  drop false ;S [[  THENs ; immediate
  248: 
  249: \ match variables
  250: 
  251: : \( ( addr -- addr ) \ regexp-pattern
  252:     \G start of matching variable; variables are referred as \\1--9
  253:     ]] dup [[
  254:     >var ]] ALiteral ! [[ ; immediate
  255: : \) ( addr -- addr ) \ regexp-pattern
  256:     \G end of matching variable
  257:     ]] dup [[
  258:     var> ]] ALiteral ! [[ ; immediate
  259: : \0 ( -- addr u ) \ regexp-pattern
  260:     \G the whole string
  261:     start$ end$ over - ;
  262: : \: ( i -- )
  263:     Create 2* 1+ cells vars + ,
  264:   DOES> ( -- addr u ) @ 2@ tuck - ;
  265: : \:s ( n -- ) 0 ?DO  I \:  LOOP ;
  266: 9 \:s \1 \2 \3 \4 \5 \6 \7 \8 \9
  267: 
  268: \ replacements, needs string.fs
  269: 
  270: require string.fs
  271: 
  272: 0 Value >>ptr
  273: 0 Value <<ptr
  274: Variable >>string
  275: : s>>  ( addr -- addr ) \ regexp-replace
  276:     \G Start replace pattern region
  277:     dup to >>ptr ;
  278: : << ( run-addr addr u -- run-addr ) \ regexp-replace
  279:     \G Replace string from start of replace pattern region with
  280:     \G @var{addr} @var{u}
  281:     <<ptr >>ptr over - >>string $+!
  282:     >>string $+! dup to <<ptr ;
  283: : <<" ( "string<">" -- ) \ regexp-replace
  284:     \G Replace string from start of replace pattern region with
  285:     \G @var{string}
  286:     '" parse postpone SLiteral postpone << ; immediate
  287: : >>string@ ( -- addr u )
  288:     >>string $@ ;
  289: : >>string0 ( addr u -- addr u )  s" " >>string $!
  290:     0 to >>ptr  over to <<ptr ;
  291: : >>next ( -- addr u ) <<ptr end$ over - ;
  292: : >>rest ( -- ) >>next >>string $+! ;
  293: : s// ( addr u -- ptr )
  294:     \G start search/replace loop
  295:     ]] >>string0 (( // s>> [[ ; immediate
  296: : >> ( addr -- addr )
  297:     ]] <<ptr >>ptr u> ?LEAVE ?end [[ ; immediate
  298: : //s ( ptr -- )
  299:     \G search end
  300:     ]] )) drop >>rest >>string@ [[ ; immediate
  301: : //o ( ptr addr u -- addr' u' )
  302:     \G end search/replace single loop
  303:     ]] << //s [[ ; immediate
  304: : //g ( ptr addr u -- addr' u' )
  305:     \G end search/replace all loop
  306:     ]] << LEAVE //s [[ ; immediate

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