patgrab in the previous section is an example of a semantic action.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.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.
; 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
spancset to match a regular expression like [0-9]*.
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
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.