Automata theory is mainly concerned with whether or not a string matches a given pattern. Like many theoretical sciences, practitioners of automata theory are only concerned if something is possible, the practical applications are not as important. For real programs, however, we would like to perform certain operations if we match a string or perform one from a set of operations depending on how we match the string.

A semantic rule or semantic action is an operation you perform based upon the type of pattern you match. This is, it is the piece of code you execute when you are satisfied with some pattern matching behavior. For example, the call to patgrab in the previous section is an example of a semantic action.

Normally, you execute the code associated with a semantic rule after returning from the call to match. Certainly when processing regular expressions, there is no need to process a semantic action in the middle of pattern matching operation. However, this isn't the case for a context free grammar. Context free grammars often involve recursion or may use the same pattern several times when matching a single string (that is, you may reference the same nonterminal several times while matching the pattern). The pattern matching data structure only maintains pointers (EndPattern, StartPattern, and StrSeg) to the last substring matched by a given pattern. Therefore, if you reuse a subpattern while matching a string and you need to execute a semantic rule associated with that subpattern, you will need to execute that semantic rule in the middle of the pattern matching operation, before you reference that subpattern again.

It turns out to be very easy to insert semantic rules in the middle of a pattern matching operation. All you need to do is write a pattern matching function that always succeeds (i.e., it returns with the carry flag clear). Within the body of your pattern matching routine you can choose to ignore the string the matching code is testing and perform any other actions you desire.

Your semantic action routine, on return, must set the carry flag and it must copy the original contents of di into ax. It must preserve all other registers. Your semantic action must not call the match routine (call sl_match2 instead). Match does not allow recursion (it is not reentrant) and calling match within a semantic action routine will mess up the pattern match in progress.

The following example provides several examples of semantic action routines within a program. This program converts arithmetic expressions in infix (algebraic) form to reverse polish notation (RPN) form.

; INFIX.ASM
;
; A simple program which demonstrates the pattern matching routines in the
; UCR library. This program accepts an arithmetic expression on the command
; line (no interleaving spaces in the expression is allowed, that is, there
; must be only one command line parameter) and converts it from infix notation
; to postfix (rpn) notation.

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


dseg            segment para public 'data'

; Grammar for simple infix -> postfix translation operation
; (the semantic actions are enclosed in braces}:
;
; E -> FE'
; E' -> +F {output '+'} E' | -F {output '-'} E' | <empty string>
; F -> TF'
; F -> *T {output '*'} F' | /T {output '/'} F' | <empty string>
; T -> -T {output 'neg'} | S
; S -> <constant> {output constant} | (E)
;
; UCR Standard Library Pattern which handles the grammar above:

; An expression consists of an "E" item followed by the end of the string:

infix2rpn               pattern {sl_Match2,E,,EndOfString}
EndOfString             pattern {EOS}

; An "E" item consists of an "F" item optionally followed by "+" or "-"
; and another "E" item:

E               pattern {sl_Match2, F,,Eprime}
Eprime          pattern {MatchChar, '+', Eprime2, epf}
epf             pattern {sl_Match2, F,,epPlus}
epPlus          pattern {OutputPlus,,,Eprime}           ;Semantic rule

Eprime2         pattern {MatchChar, '-', Succeed, emf}
emf             pattern {sl_Match2, F,,epMinus}
epMinus         pattern {OutputMinus,,,Eprime}          ;Semantic rule

; An "F" item consists of a "T" item optionally followed by "*" or "/"
; followed by another "T" item:

F               pattern {sl_Match2, T,,Fprime}
Fprime          pattern {MatchChar, '*', Fprime2, fmf}
fmf             pattern {sl_Match2, T, 0, pMul}
pMul            pattern {OutputMul,,,Fprime}            ;Semantic rule

Fprime2         pattern {MatchChar, '/', Succeed, fdf}
fdf             pattern {sl_Match2, T, 0, pDiv}
pDiv            pattern {OutputDiv, 0, 0,Fprime}        ;Semantic rule

; T item consists of an "S" item or a "-" followed by another "T" item:

T               pattern {MatchChar, '-', S, TT}
TT              pattern {sl_Match2, T, 0,tpn}
tpn             pattern {OutputNeg}                     ;Semantic rule

; An "S" item is either a string of one or more digits or "(" followed by
; and "E" item followed by ")":

Const           pattern {sl_Match2, DoDigits, 0, spd}
spd             pattern {OutputDigits}                  ;Semantic rule

DoDigits        pattern {Anycset, Digits, 0, SpanDigits}
SpanDigits      pattern {Spancset, Digits}

S               pattern {MatchChar, '(', Const, IntE}
IntE            pattern {sl_Match2, E, 0, CloseParen}
CloseParen      pattern {MatchChar, ')'}


Succeed         pattern {DoSucceed}


                include stdsets.a

dseg            ends



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

; DoSucceed matches the empty string. In other words, it matches anything
; and always returns success without eating any characters from the input
; string.

DoSucceed       proc    far
                mov     ax, di
                stc
                ret
DoSucceed       endp


; OutputPlus is a semantic rule which outputs the "+" operator after the
; parser sees a valid addition operator in the infix string.

OutputPlus      proc    far
                print
                byte    " +",0
                mov     ax, di                  ;Required by sl_Match
                stc
                ret
OutputPlus      endp


; OutputMinus is a semantic rule which outputs the "-" operator after the
; parser sees a valid subtraction operator in the infix string.

OutputMinus     proc    far
                print
                byte    " -",0
                mov     ax, di                  ;Required by sl_Match
                stc
                ret
OutputMinus     endp


; OutputMul is a semantic rule which outputs the "*" operator after the
; parser sees a valid multiplication operator in the infix string.

OutputMul       proc    far
                print
                byte    " *",0
                mov     ax, di                  ;Required by sl_Match
                stc
                ret
OutputMul       endp


; OutputDiv is a semantic rule which outputs the "/" operator after the
; parser sees a valid division operator in the infix string.

OutputDiv       proc    far
                print
                byte    " /",0
                mov     ax, di                  ;Required by sl_Match
                stc
                ret
OutputDiv       endp


; OutputNeg is a semantic rule which outputs the unary "-" operator after the
; parser sees a valid negation operator in the infix string.

OutputNeg       proc    far
                print
                byte    " neg",0
                mov     ax, di                  ;Required by sl_Match
                stc
                ret
OutputNeg       endp


; OutputDigits outputs the numeric value when it encounters a legal integer
; value in the input string.

OutputDigits    proc    far
                push    es
                push    di
                mov     al, ' '
                putc
                lesi    const
                patgrab
                puts
                free
                stc
                pop     di
                mov     ax, di
                pop     es
                ret
OutputDigits    endp



; Okay, here's the main program which fetches the command line parameter
; and parses it.

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

                meminit                         ; memory to the heap.


                print
                byte    "Enter an arithmetic expression: ",0
                getsm
                print
                byte    "Expression in postfix form: ",0

                ldxi    infix2rpn
                xor     cx, cx
                match
                jc      Succeeded

                print
                byte    "Syntax error",0

Succeeded:      putcr

Quit:           ExitPgm
Main            endp

cseg            ends



; Allocate a reasonable amount of space for the stack (8k).

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


; zzzzzzseg must be the last segment that gets loaded into memory!

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

A major issue we have yet to discuss is how to convert regular expressions and context free grammars into patterns suitable for the UCR Standard Library pattern matching routines. Most of the examples appearing up to this point have used an ad hoc translation scheme; now it is time to provide an algorithm to accomplish this.

The following algorithm converts a context free grammar to a UCR Standard Library pattern data structure. If you want to convert a regular expression to a pattern, first convert the regular expression to a context free grammar. Of course, it is easy to convert many regular expression forms directly to a pattern, when such conversions are obvious you can bypass the following algorithm; for example, it should be obvious that you can use spancset to match a regular expression like [0-9]*.

The first step you must always take is to eliminate left recursion from the grammar. You will generate an infinite loop (and crash the machine) if you attempt to code a grammar containing left recursion into a pattern data structure. You might also want to left factor the grammar while you are eliminating left recursion. The Standard Library routines fully support backtracking, so left factoring is not strictly necessary, however, the matching routine will execute faster if it does not need to backtrack.

If a grammar production takes the form A B C where A, B, and C are nonterminal symbols, you would create the following pattern:

A		pattern	{sl_match2,B,0,C}

This pattern description for A checks for an occurrence of a B pattern followed by a C pattern.

If B is a relatively simple production (that is, you can convert it to a single pattern data structure), you can optimize this to:

A		pattern	{B's Matching Function, B's parameter, 0, C}

The remaining examples will always call sl_match2, just to be consistent. However, as long as the nonterminals you invoke are simple, you can fold them into A''s pattern.

If a grammar production takes the form A B | C where A, B, and C are nonterminal symbols, you would create the following pattern:

A		pattern	{sl_match2, B, C}

This pattern tries to match B. If it succeeds, A succeeds; if it fails, it tries to match C. At this point, A''s success or failure is the success or failure of C.

Handling terminal symbols is the next thing to consider. These are quite easy - all you need to do is use the appropriate matching function provided by the Standard Library, e.g., matchstr or matchchar. For example, if you have a production of the form A abc | y you would convert this to the following pattern:

A               pattern {matchstr,abc,ypat}

abc             byte    "abc",0

ypat            pattern {matchchar,'y'}

The only remaining detail to consider is the empty string. If you have a production of the form A then you need to write a pattern matching function that always succeed. The elegant way to do this is to write a custom pattern matching function. This function is

succeed         proc    far
                mov     ax, di  ;Required by sl_match
                stc             ;Always succeed.
                ret
succeed         endp

Another, sneaky, way to force success is to use matchstr and pass it the empty string to match, e.g.,

success         pattern {matchstr, emptystr}
emptystr        byte    0

The empty string always matches the input string, no matter what the input string contains.

If you have a production with several alternatives and is one of them, you must process last. For example, if you have the productions A abc | y | BC | you would use the following pattern:

A               pattern {matchstr,abc, tryY}
abc             byte    "abc",0
tryY            pattern {matchchar, 'y', tryBC}
tryBC           pattern {sl_match2, B, DoSuccess, C}
DoSuccess       pattern {succeed}

While the technique described above will let you convert any CFG to a pattern that the Standard Library can process, it certainly does not take advantage of the Standard Library facilities, nor will it produce particularly efficient patterns. For example, consider the production:

Digits   0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Converting this to a pattern using the techniques described above will yield the pattern:

Digits		pattern	{matchchar, '0', try1}
try1		pattern	{matchchar, '1', try2}
try2		pattern	{matchchar, '2', try3}
try3		pattern	{matchchar, '3', try4}
try4		pattern	{matchchar, '4', try5}
try5		pattern	{matchchar, '5', try6}
try6		pattern	{matchchar, '6', try7}
try7		pattern	{matchchar, '7', try8}
try8		pattern	{matchchar, '8', try9}
try9		pattern	{matchchar, '9'}

Obviously this isn't a very good solution because we can match this same pattern with the single statement:

Digits  pattern {anycset, digits}

If your pattern is easy to specify using a regular expression, you should try to encode it using the built-in pattern matching functions and fall back on the above algorithm once you've handled the low level patterns as best you can. With experience, you will be able to choose an appropriate balance between the algorithm in this section and ad hoc methods you develop on your own.

Chapter Sixteen: Pattern Matching (Part 7)
29 SEP 1996