[Chapter Sixteen][Previous] [Next] [Art of Assembly][Randall Hyde]

Art of Assembly: Chapter Sixteen


16.4 - Designing Your Own Pattern Matching Routines
16.5 - Extracting Substrings from Matched Patterns

16.4 Designing Your Own Pattern Matching Routines


Although the UCR Standard Library provides a wide variety of matching functions, there is no way to anticipate the needs of all applications. Therefore, you will probably discover that the library does not support some particular pattern matching function you need. Fortunately, it is very easy for you to create your own pattern matching functions to augment those available in the UCR Standard Library. When you specify a matching function name in the pattern data structure, the match routine calls the specified address using a far call and passing the following parameters:

es:di- Points at the next character in the input string. You should not look at any characters before this address. Furthermore, you should never look beyond the end of the string (see cx below).

ds:si- Contains the four byte parameter found in the matchparm field.

cx- Contains the last position, plus one, in the input string you're allowed to look at. Note that your pattern matching routine should not look beyond location es:cx or the zero terminating byte; whichever comes first in the input string.

On return from the function, ax must contain the offset into the string (di's value) of the last character matched plus one, if your matching function is successful. It must also set the carry flag to denote success. After your pattern matches, the match routine might call another matching function (the one specified by the next pattern field) and that function begins matching at location es:ax.

If the pattern match fails, then you must return the original di value in the ax register and return with the carry flag clear. Note that your matching function must preserve all other registers.

There is one very important detail you must never forget with writing your own pattern matching routines - ds does not point at your data segment, it contains the H.O. word of the matchparm parameter. Therefore, if you are going to access global variables in your data segment you will need to push ds, load it with the address of dseg, and pop ds before leaving. Several examples throughout this chapter demonstrate how to do this.

There are some obvious omissions from (the current version of) the UCR Standard Library's repertoire. For example, there should probably be matchtoistr, matchichar, and matchtoichar pattern functions. The following example code demonstrates how to add a matchtoistr (match up to a string, doing a case insensitive comparison) routine.




                .xlist

                include         stdlib.a
                includelib      stdlib.lib
                matchfuncs
                .list

dseg            segment para public 'data'

TestString      byte    "This is the string 'xyz' in it",cr,lf,0

TestPat         pattern {matchtoistr,xyz}
xyz             byte    "XYZ",0

dseg            ends


cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg

; MatchToiStr-  Matches all characters in a string up to, and including, the
;               specified parameter string. The parameter string must be
;               all upper case characters. This guy matches string using
;               a case insensitive comparison.
;
; inputs:
;               es:di-  Source string
;               ds:si-  String to match
;               cx-     Maximum match position
;
; outputs:
;               ax-     Points at first character beyond the end of the
;                       matched string if success, contains the initial DI
;                       value if failure occurs.
;               carry-  0 if failure, 1 if success.

MatchToiStr     proc    far
                pushf
                push    di
                push    si
                cld

; Check to see if we're already past the point were we're allowed
; to scan in the input string.

                cmp     di, cx
                jae     MTiSFailure

; If the pattern string is the empty string, always match.

                cmp     byte ptr ds:[si], 0
                je      MTSsuccess

; The following loop scans through the input string looking for
; the first character in the pattern string.

ScanLoop:       push    si
                lodsb                   ;Get first char of string

                dec     di
FindFirst:      inc     di              ;Move on to next (or 1st) char.
                cmp     di, cx          ;If at cx, then we've got to
                jae CantFind1st ; fail.

                mov     ah, es:[di]     ;Get input character.
                cmp     ah, 'a'         ;Convert input character to
                jb      DoCmp           ; upper case if it's a lower
                cmp     ah, 'z'         ; case character.
                ja      DoCmp
                and     ah, 5fh
DoCmp:          cmp     al, ah          ;Compare input character against
                jne     FindFirst       ; pattern string.


; At this point, we've located the first character in the input string
; that matches the first character of the pattern string. See if the
; strings are equal.

                push    di              ;Save restart point.

CmpLoop:        cmp     di, cx          ;See if we've gone beyond the
                jae     StrNotThere     ; last position allowable.
                lodsb                   ;Get next input character.
                cmp     al, 0           ;At the end of the parameter
                je      MTSsuccess2     ; string? If so, succeed.

                inc     di
                mov     ah, es:[di]     ;Get the next input character.
                cmp     ah, 'a'         ;Convert input character to
                jb      DoCmp2          ; upper case if it's a lower
                cmp     ah, 'z'         ; case character.
                ja      DoCmp2
                and     ah, 5fh
DoCmp2:         cmp     al, ah          ;Compare input character against
                je      CmpLoop
                pop     di
                pop     si
                jmp     ScanLoop

StrNotThere:    add     sp, 2           ;Remove di from stack.
CantFind1st:    add     sp, 2           ;Remove si from stack.
MTiSFailure:    pop     si
                pop     di
                mov     ax, di          ;Return failure position in AX.
                popf
                clc                     ;Return failure.
                ret

MTSSuccess2:    add     sp, 2           ;Remove DI value from stack.
MTSSuccess:     add     sp, 2           ;Remove SI value from stack.
                mov     ax, di          ;Return next position in AX.
                pop     si
                pop     di
                popf
                stc                     ;Return success.
                ret
MatchToiStr     endp

Main            proc
                mov     ax, dseg
                mov     ds, ax
                mov     es, ax
                meminit

                lesi    TestString
                ldxi    TestPat
                xor     cx, cx
                match
                jnc     NoMatch
                print
                byte    "Matched",cr,lf,0
                jmp     Quit

NoMatch:        print
                byte    "Did not match",cr,lf,0

Quit:           ExitPgm
Main            endp

cseg            ends

sseg            segment para stack 'stack'
stk             db      1024 dup ("stack ")
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
                end     Main


16.5 Extracting Substrings from Matched Patterns


Often, simply determining that a string matches a given pattern is insufficient. You may want to perform various operations that depend upon the actual information in that string. However, the pattern matching facilities described thus far do not provide a mechanism for testing individual components of the input string. In this section, you will see how to extract portions of a pattern for further processing.

Perhaps an example may help clarify the need to extract portions of a string. Suppose you are writing a stock buy/sell program and you want it to process commands described by the following regular expression:




(buy | sell) [0-9]+ shares of (ibm | apple | hp | dec)

While it is easy to devise a Standard Library pattern that recognizes strings of this form, calling the match routine would only tell you that you have a legal buy or sell command. It does not tell you if you are to buy or sell, who to buy or sell, or how many shares to buy or sell. Of course, you could take the cross product of (buy | sell) with (ibm | apple | hp | dec) and generate eight different regular expressions that uniquely determine whether you're buying or selling and whose stock you're trading, but you can't process the integer values this way (unless you willing to have millions of regular expressions). A better solution would be to extract substrings from the legal pattern and process these substrings after you verify that you have a legal buy or sell command. For example, you could extract buy or sell into one string, the digits into another, and the company name into a third. After verifying the syntax of the command, you could process the individual strings you've extracted. The UCR Standard Library patgrab routine provides this capability for you.

You normally call patgrab after calling match and verifying that it matches the input string. Patgrab expects a single parameter - a pointer to a pattern recently processed by match. Patgrab creates a string on the heap consisting of the characters matched by the given pattern and returns a pointer to this string in es:di. Note that patgrab only returns a string associated with a single pattern data structure, not a chain of pattern data structures. Consider the following pattern:





PatToGrab       pattern {matchstr, str1, 0, Pat2}
Pat2            pattern {matchstr, str2}
str1            byte    "Hello",0
str2            byte    " there",0

Calling match on PatToGrab will match the string "Hello there". However, if after calling match you call patgrab and pass it the address of PatToGrab, patgrab will return a pointer to the string "Hello".

Of course, you might want to collect a string that is the concatenation of several strings matched within your pattern (i.e., a portion of the pattern list). This is where calling the sl_match2 pattern matching function comes in handy. Consider the following pattern:





Numbers         pattern {sl_match2, FirstNumber}
FirstNumber     pattern {anycset, digits, 0, OtherDigs}
OtherDigs       pattern {spancset, digits}

This pattern matches the same strings as





Numbers         pattern {anycset, digits, 0, OtherDigs}
OtherDigs       pattern {spancset, digits}

So why bother with the extra pattern that calls sl_match2? Well, as it turns out the sl_match2 matching function lets you create parenthetical patterns. A parenthetical pattern is a pattern list that the pattern matching routines (especially patgrab) treat as a single pattern. Although the match routine will match the same strings regardless of which version of Numbers you use, patgrab will produce two entirely different strings depending upon your choice of the above patterns. If you use the latter version, patgrab will only return the first digit of the number. If you use the former version (with the call to sl_match2), then patgrab returns the entire string matched by sl_match2, and that turns out to be the entire string of digits.

The following sample program demonstrates how to use parenthetical patterns to extract the pertinent information from the stock command presented earlier. It uses parenthetical patterns for the buy/sell command, the number of shares, and the company name.





                .xlist
                include                 stdlib.a
                includelib              stdlib.lib
                matchfuncs
                .list

dseg            segment para public 'data'

; Variables used to hold the number of shares bought/sold, a pointer to
; a string containing the buy/sell command, and a pointer to a string
; containing the company name.

Count           word    0
CmdPtr          dword   ?
CompPtr         dword   ?

; Some test strings to try out:

Cmd1            byte    "Buy 25 shares of apple stock",0
Cmd2            byte    "Sell 50 shares of hp stock",0
Cmd3            byte    "Buy 123 shares of dec stock",0
Cmd4            byte    "Sell 15 shares of ibm stock",0
BadCmd0         byte    "This is not a buy/sell command",0

; Patterns for the stock buy/sell command:
;
; StkCmd matches buy or sell and creates a parenthetical pattern
; that contains the string "buy" or "sell".

StkCmd          pattern {sl_match2, buyPat, 0, skipspcs1}

buyPat          pattern {matchistr,buystr,sellpat}
buystr          byte    "BUY",0

sellpat         pattern {matchistr,sellstr}
sellstr         byte    "SELL",0

; Skip zero or more white space characters after the buy command.

skipspcs1       pattern {spancset, whitespace, 0, CountPat}

; CountPat is a parenthetical pattern that matches one or more
; digits.

CountPat        pattern {sl_match2, Numbers, 0, skipspcs2}
Numbers         pattern {anycset, digits, 0, RestOfNum}
RestOfNum       pattern {spancset, digits}

; The following patterns match " shares of " allowing any amount
; of white space between the words.

skipspcs2       pattern {spancset, whitespace, 0, sharesPat}

sharesPat       pattern {matchistr, sharesStr, 0, skipspcs3}
sharesStr       byte    "SHARES",0

skipspcs3       pattern {spancset, whitespace, 0, ofPat}

ofPat           pattern {matchistr, ofStr, 0, skipspcs4}
ofStr           byte    "OF",0

skipspcs4       pattern {spancset, whitespace, 0, CompanyPat}

; The following parenthetical pattern matches a company name.
; The patgrab-available string will contain the corporate name.

CompanyPat      pattern {sl_match2, ibmpat}

ibmpat          pattern {matchistr, ibm, applePat}
ibm             byte    "IBM",0

applePat        pattern {matchistr, apple, hpPat}
apple           byte    "APPLE",0

hpPat           pattern {matchistr, hp, decPat}
hp              byte    "HP",0

decPat          pattern {matchistr, decstr}
decstr          byte    "DEC",0

                include stdsets.a
dseg            ends

cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg

; DoBuySell-    This routine processes a stock buy/sell command.
;               After matching the command, it grabs the components
;               of the command and outputs them as appropriate.
;               This routine demonstrates how to use patgrab to
;               extract substrings from a pattern string.
;
;               On entry, es:di must point at the buy/sell command
;               you want to process.

DoBuySell       proc    near
                ldxi StkCmd
                xor     cx, cx
                match
                jnc     NoMatch

                lesi    StkCmd
                patgrab
                mov     word ptr CmdPtr, di
                mov     word ptr CmdPtr+2, es

                lesi    CountPat
                patgrab
                atoi                    ;Convert digits to integer
                mov     Count, ax
                free                    ;Return storage to heap.

                lesi    CompanyPat
                patgrab
                mov     word ptr CompPtr, di
                mov     word ptr CompPtr+2, es

                printf
                byte    "Stock command: %^s\n"
                byte    "Number of shares: %d\n"
                byte    "Company to trade: %^s\n\n",0
                dword   CmdPtr, Count, CompPtr

                les     di, CmdPtr
                free
                les     di, CompPtr
                free
                ret

NoMatch:                print
                byte    "Illegal buy/sell command",cr,lf,0
                ret
DoBuySell       endp


Main            proc
                mov     ax, dseg
                mov     ds, ax
                mov     es, ax

                meminit

                lesi    Cmd1
                call    DoBuySell
                lesi    Cmd2
                call    DoBuySell
                lesi    Cmd3
                call    DoBuySell
                lesi    Cmd4
                call    DoBuySell
                lesi    BadCmd0
                call    DoBuySell

Quit:           ExitPgm
Main            endp

cseg            ends

sseg            segment para stack 'stack'
stk             db      1024 dup ("stack ")
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
                end     Main


Sample program output:
Stock command: Buy
Number of shares: 25
Company to trade: apple

Stock command: Sell
Number of shares: 50
Company to trade: hp

Stock command: Buy
Number of shares: 123
Company to trade: dec

Stock command: Sell
Number of shares: 15
Company to trade: ibm

Illegal buy/sell command
16.4 - Designing Your Own Pattern Matching Routines
16.5 - Extracting Substrings from Matched Patterns


Art of Assembly: Chapter Sixteen - 29 SEP 1996

[Chapter Sixteen][Previous] [Next] [Art of Assembly][Randall Hyde]



Number of Web Site Hits since Jan 1, 2000: