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

Art of Assembly: Chapter Sixteen


16.1.3 - Context Free Languages
16.1.4 - Eliminating Left Recursion and Left Factoring CFGs
16.1.5 - Converting REs to CFGs
16.1.6 - Converting CFGs to Assembly Language
16.1.7 - Some Final Comments on CFGs
16.1.8 - Beyond Context Free Languages

16.1.3 Context Free Languages


Context free languages provide a superset of the regular languages - if you can specify a class of patterns with a regular expression, you can express the same language using a context free grammar. In addition, you can specify many languages that are not regular using context free grammars (CFGs).

Examples of languages that are context free, but not regular, include the set of all strings representing common arithmetic expressions, legal Pascal or C source files, and MASM macros. Context free languages are characterized by balance and nesting. For example, arithmetic expression have balanced sets of parenthesis. High level language statements like repeat...until allow nesting and are always balanced (e.g., for every repeat there is a corresponding until statement later in the source file).

There is only a slight extension to the regular languages to handle context free languages - function calls. In a regular expression, we only allow the objects we want to match and the specific RE operators like "|", "*", concatenation, and so on. To extend regular languages to context free languages, we need only add recursive function calls to regular expressions. Although it would be simple to create a syntax allowing function calls within a regular expression, computer scientists use a different notation altogether for context free languages - a context free grammar.

A context free grammar contains two types of symbols: terminal symbols and nonterminal symbols. Terminal symbols are the individual characters and strings that the context free grammar matches plus the empty string, . Context free grammars use nonterminal symbols for function calls and definitions. In our context free grammars we will use italic characters to denote nonterminal symbols and standard characters to denote terminal symbols.

To match this string, we begin by calling the starting symbol function, expression, using the function expression expression + factor. The first plus sign suggests that the expression term must match "7" and the factor term must match "5*(2+1)". Now we need to match our input string with the pattern expression + factor. To do this, we call the expression function once again, this time using the expression factor production. This give us the reduction:

expression expression + factor factor + factor

The symbol denotes the application of a nonterminal function call (a reduction).

Next, we call the factor function, using the production factor term to yield the reduction:

expression expression + factor factor + factor term + factor

Continuing, we call the term function to produce the reduction:

expression expression + factor factor + factor term + factor IntegerConstant + factor

Next, we call the IntegerConstant function to yield:

expression expression + factor factor + factor term + factor IntegerConstant + factor 7 + factor

At this point, the first two symbols of our generated string match the first two characters of the input string, so we can remove them from the input and concentrate on the items that follow. In succession, we call the factor function to produce the reduction 7 + factor * term and then we call factor, term, and IntegerConstant to yield 7 + 5 * term. In a similar fashion, we can reduce the term to "( expression )" and reduce expression to "2+1". The complete derivation for this string is



expression	 expression + factor 

		 factor + factor 

		 term + factor 

		 IntegerConstant + factor 

		 7 + factor 

		 7 + factor * term 

		 7 + term * term 

		 7 + IntegerConstant * term 

		 7 + 5 * term 

		 7 + 5 * ( expression ) 

		 7 + 5 * ( expression + factor ) 

		 7 + 5 * ( factor + factor ) 

		 7 + 5 * ( IntegerConstant + factor ) 

		 7 + 5 * ( 2 + factor ) 

		 7 + 5 * ( 2 + term ) 

		 7 + 5 * ( 2 + IntegerConstant ) 

		 7 + 5 * ( 2 + 1 )

The final reduction completes the derivation of our input string, so the string 7+5*(2+1) is in the language specified by the context free grammar.



16.1.4 Eliminating Left Recursion and Left Factoring CFGs


In the next section we will discuss how to convert a CFG to an assembly language program. However, the technique we are going to use to do this conversion will require that we modify certain grammars before converting them. The arithmetic expression grammar in the previous section is a good example of such a grammar - one that is left recursive.

Left recursive grammars pose a problem for us because the way we will typically convert a production to assembly code is to call a function corresponding to a nonterminal and compare against the terminal symbols. However, we will run into trouble if we attempt to convert a production like the following using this technique:




expression  expression + factor

Such a conversion would yield some assembly code that looks roughly like the following:





expression      proc    near
                call    expression
                jnc     fail
                cmp     byte ptr es:[di], '+'
                jne     fail
                inc     di
                call    factor
                jnc     fail
                stc
                ret
Fail:           clc
                ret
expression      endp

The obvious problem with this code is that it will generate an infinite loop. Upon entering the expression function this code immediately calls expression recursively, which immediately calls expression recursively, which immediately calls expression recursively, ... Clearly, we need to resolve this problem if we are going to write any real code to match this production.

The trick to resolving left recursion is to note that if there is a production that suffers from left recursion, there must be some production with the same left hand side that is not left recursive. All we need do is rewrite the left recursive call in terms of the production that does not have any left recursion. This sound like a difficult task, but it's actually quite easy.

To see how to eliminate left recursion, let Xi and Yj represent any set of terminal symbols or nonterminal symbols that do not have a right hand side beginning with the nonterminal A. If you have some productions of the form:





A  AX1 | AX2 |  | AXn | Y1 | Y2 |  | Ym 

You will be able to translate this to an equivalent grammar without left recursion by replacing each term of the form A Yi by A Yi A and each term of the form A AXi by A' Xi A' | . For example, consider three of the productions from the arithmetic grammar:




expression  expression + factor

expression  expression - factor

expression  factor

In this example A corresponds to expression, X1 corresponds to "+ factor ", X2 corresponds to "- factor ", and Y1 corresponds to "factor ". The equivalent grammar without left recursion is




expression  factor E'

E'  - factor E'

E'  + factor E'

E'  

The complete arithmetic grammar, with left recursion removed, is




expression  factor E'

E'  + factor E' |  - factor E' |  

factor  term F'

F'  * term F' |  / term F' |  

term  IntegerConstant  |  ( expression )

IntegerConstant  digit  |  digit IntegerConstant

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

Another useful transformation on a grammar is to left factor the grammar. This can reduce the need for backtracking, improving the performance of your pattern matching code. Consider the following CFG fragment:




stmt  if expression then stmt endif

stmt  if expression then stmt else stmt endif

These two productions begin with the same set of symbols. Either production will match all the characters in an if statement up to the point the matching algorithm encounters the first else or endif. If the matching algorithm processes the first statement up to the point of the endif terminal symbol and encounters the else terminal symbol instead, it must backtrack all the way to the if symbol and start over. This can be terribly inefficient because of the recursive call to stmt (imagine a 10,000 line program that has a single if statement around the entire 10,000 lines, a compiler using this pattern matching technique would have to recompile the entire program from scratch if it used backtracking in this fashion). However, by left factoring the grammar before converting it to program code, you can eliminate the need for backtracking.

To left factor a grammar, you collect all productions that have the same left hand side and begin with the same symbols on the right hand side. In the two productions above, the common symbols are "if expression then stmt ". You combine the common strings into a single production and then append a new nonterminal symbol to the end of this new production, e.g.,




stmt  if expression then stmt NewNonTerm

Finally, you create a new set of productions using this new nonterminal for each of the suffixes to the common production:




NewNonTerm  endif | else stmt endif

This eliminates backtracking because the matching algorithm can process the if, the expression, the then, and the stmt before it has to choose between endif and else.



16.1.5 Converting REs to CFGs


Since the context free languages are a superset of the regular languages, it should come as no surprise that it is possible to convert regular expressions to context free grammars. Indeed, this is a very easy process involving only a few intuitive rules.

1) If a regular expression simply consists of a sequence of characters, xyz, you can easily create a production for this regular expression of the form P xyz. This applies equally to the empty string, .

2) If r and s are two regular expression that you've converted to CFG productions R and S , and you have a regular expression rs that you want to convert to a production, simply create a new production of the form T R S.

3) If r and s are two regular expression that you've converted to CFG productions R and S , and you have a regular expression r | s that you want to convert to a production, simply create a new production of the form T R | S.

4) If r is a regular expression that you've converted to a production, R, and you want to create a production for r*, simply use the production RStar R RStar | .

5) If r is a regular expression that you've converted to a production, R, and you want to create a production for r+, simply use the production RPlus R RPlus | R.

6) For regular expressions there are operations with various precedences. Regular expressions also allow parenthesis to override the default precedence. This notion of precedence does not carry over into CFGs. Instead, you must encode the precedence directly into the grammar. For example, to encode R S* you would probably use productions of the form:



		T   R   SStar

		SStar  S SStar | 
		

Likewise, to handle a grammar of the form (RS )* you could use productions of the form:




		T   R S   T  | 

		RS   R   S


16.1.6 Converting CFGs to Assembly Language


If you have removed left recursion and you've left factored a grammar, it is very easy to convert such a grammar to an assembly language program that recognizes strings in the context free language.

The first convention we will adopt is that es:di always points at the start of the string we want to match. The second convention we will adopt is to create a function for each nonterminal. This function returns success (carry set) if it matches an associated subpattern, it returns failure (carry clear) otherwise. If it succeeds, it leaves di pointing at the next character is the staring after the matched pattern; if it fails, it preserves the value in di across the function call.

To convert a set of productions to their corresponding assembly code, we need to be able to handle four things: terminal symbols, nonterminal symbols, alternation, and the empty string. First, we will consider simple functions (nonterminals) which do not have multiple productions (i.e., alternation).

If a production takes the form T and there are no other productions associated with T, then this production always succeeds. The corresponding assembly code is simply:




T               proc    near
                stc
                ret
T               endp

Of course, there is no real need to ever call T and test the returned result since we know it will always succeed. On the other hand, if T is a stub that you intend to fill in later, you should call T.

If a production takes the form T xyz, where xyz is a string of one or more terminal symbols, then the function returns success if the next several input characters match xyz, it returns failure otherwise. Remember, if the prefix of the input string matches xyz, then the matching function must advance di beyond these characters. If the first characters of the input string does not match xyz, it must preserve di. The following routines demonstrate two cases, where xyz is a single character and where xyz is a string of characters:





T1              proc    near
                cmp     byte ptr es:[di], 'x'   ;Single char.
                je      Success
                clc                             ;Return Failure.
                ret

Success:        inc     di                      ;Skip matched char.
                stc                             ;Return success.
                ret
T1              endp


T2              proc    near
                call    MatchPrefix
                byte    'xyz',0
                ret
T2              endp

MatchPrefix is a routine that matches the prefix of the string pointed at by es:di against the string following the call in the code stream. It returns the carry set and adjusts di if the string in the code stream is a prefix of the input string, it returns the carry flag clear and preserves di if the literal string is not a prefix of the input. The MatchPrefix code follows:





MatchPrefix     proc    far             ;Must be far!
                push    bp
                mov     bp, sp
                push    ax
                push    ds
                push    si
                push    di

                lds     si, 2[bp]       ;Get the return address.
CmpLoop:        mov     al, ds:[si]     ;Get string to match.
                cmp     al, 0           ;If at end of prefix,
                je      Success         ; we succeed.
                cmp     al, es:[di]     ;See if it matches prefix,
                jne     Failure         ; if not, immediately fail.
                inc     si
                inc     di
                jmp     CmpLoop

Success:        add     sp, 2           ;Don't restore di.
                inc     si              ;Skip zero terminating byte.
                mov     2[bp], si       ;Save as return address.
                pop     si
                pop     ds
                pop     ax
                pop     bp
                stc                     ;Return success.
                ret

Failure:        inc     si              ;Need to skip to zero byte.
                cmp     byte ptr ds:[si], 0
                jne     Failure
                inc     si
                mov     2[bp], si       ;Save as return address.

                pop     di
                pop     si
                pop     ds
                pop     ax
                pop     bp
                clc                     ;Return failure.
                ret
MatchPrefix     endp

If a production takes the form T R, where R is a nonterminal, then the T function calls R and returns whatever status R returns, e.g.,





T		proc	near
		call	R
		ret
T		endp

If the right hand side of a production contains a string of terminal and nonterminal symbols, the corresponding assembly code checks each item in turn. If any check fails, then the function returns failure. If all items succeed, then the function returns success. For example, if you have a production of the form T R abc S you could implement this in assembly language as





T               proc    near
                push    di              ;If we fail, must preserve di.
                call    R
                jnc     Failure
                call    MatchPrefix
                byte    "abc",0
                jnc     Failure
                call    S
                jnc     Failure
                add     sp, 2           ;Don't preserve di if we succeed.
                stc
                ret

Failure:        pop     di
                clc
                ret
T               endp

Note how this code preserves di if it fails, but does not preserve di if it succeeds.

If you have multiple productions with the same left hand side (i.e., alternation), then writing an appropriate matching function for the productions is only slightly more complex than the single production case. If you have multiple productions associated with a single nonterminal on the left hand side, then create a sequence of code to match each of the individual productions. To combine them into a single matching function, simply write the function so that it succeeds if any one of these code sequences succeeds. If one of the productions is of the form T e, then test the other conditions first. If none of them could be selected, the function succeeds. For example, consider the productions:






E'  + factor E' |  - factor E' |  

This translates to the following assembly code:





EPrime          proc    near
                push    di
                cmp     byte ptr es:[di], '+'
                jne     TryMinus
                inc     di
                call    factor
                jnc     EP_Failed
                call    EPrime
                jnc     EP_Failed
Success:        add     sp, 2
                stc
                ret

TryMinus:       cmp     byte ptr es:[di], '-'
                jne     EP_Failed
                inc     di
                call    factor
                jnc     EP_Failed
                call    EPrime
                jnc     EP_Failed
                add     sp, 2
                stc
                ret

EP_Failed:      pop     di
                stc                     ;Succeed because of E' -> e
                ret
EPrime          endp

This routine always succeeds because it has the production E' . This is why the stc instruction appears after the EP_Failed label.


To invoke a pattern matching function, simply load es:di with the address of the string you want to test and call the pattern matching function. On return, the carry flag will contain one if the pattern matches the string up to the point returned in di. If you want to see if the entire string matches the pattern, simply check to see if es:di is pointing at a zero byte when you get back from the function call. If you want to see if a string belongs to a context free language, you should call the function associated with the starting symbol for the given context free grammar.

The following program implements the arithmetic grammar we've been using as examples throughout the past several sections. The complete implementation is





; ARITH.ASM
;
; A simple recursive descent parser for arithmetic strings.

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


dseg            segment para public 'data'

; Grammar for simple arithmetic grammar (supports +, -, *, /):
;
; E -> FE'
; E' -> + F E' | - F E' | <empty string>
; F -> TF'
; F' -> * T F' | / T F' | <empty string>
; T -> G | (E)
; G -> H | H G
; H -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
;


InputLine       byte    128 dup (0)

dseg            ends

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

; Matching functions for the grammar.
; These functions return the carry flag set if they match their
; respective item. They return the carry flag clear if they fail.
; If they fail, they preserve di. If they succeed, di points to
; the first character after the match.


; E -> FE'

E               proc    near
                push    di
                call    F               ;See if F, then E', succeeds.
                jnc     E_Failed
                call    EPrime
                jnc     E_Failed
                add     sp, 2           ;Success, don't restore di.
                stc
                ret

E_Failed:       pop     di              ;Failure, must restore di.
                clc
                ret
E               endp



; E' -> + F E' | - F E' | e

EPrime          proc    near
                push    di

; Try + F E' here

                cmp     byte ptr es:[di], '+'
                jne     TryMinus
                inc     di
                call    F
                jnc     EP_Failed
                call    EPrime
                jnc     EP_Failed
Success:        add     sp, 2
                stc
                ret

; Try  - F E' here.

TryMinus:       cmp     byte ptr es:[di], '-'
                jne     Success
                inc     di
                call    F
                jnc     EP_Failed
                call    EPrime
                jnc     EP_Failed
                add     sp, 2
                stc
                ret

; If none of the above succeed, return success anyway because we have
; a production of the form E' -> e.

EP_Failed:      pop     di
                stc
                ret
EPrime          endp



; F -> TF'

F               proc    near
                push    di
                call    T
                jnc     F_Failed
                call    FPrime
                jnc     F_Failed
                add     sp, 2           ;Success, don't restore di.
                stc
                ret

F_Failed:       pop     di
                clc
                ret
F               endp




; F -> * T F' | / T F' | e

FPrime          proc    near
                push    di
                cmp     byte ptr es:[di], '*'   ;Start with "*"?
                jne     TryDiv
                inc     di                      ;Skip the "*".
                call    T
                jnc     FP_Failed
                call    FPrime
                jnc     FP_Failed
Success:        add     sp, 2
                stc
                ret

; Try F -> / T F' here

TryDiv:         cmp     byte ptr es:[di], '/'   ;Start with "/"?
                jne     Success                 ;Succeed anyway.
                inc     di                      ;Skip the "/".
                call    T
                jnc     FP_Failed
                call    FPrime
                jnc     FP_Failed
                add     sp, 2
                stc
                ret

; If the above both fail, return success anyway because we've got
; a production of the form F -> e

FP_Failed:      pop     di
                stc
                ret
FPrime          endp


; T -> G | (E)

T               proc    near

; Try T -> G here.

                call    G
                jnc     TryParens
                ret

; Try T -> (E) here.

TryParens:      push    di                      ;Preserve if we fail.
                cmp     byte ptr es:[di], '('   ;Start with "("?
                jne     T_Failed                ;Fail if no.
                inc     di                      ;Skip "(" char.
                call    E
                jnc     T_Failed
                cmp     byte ptr es:[di], ')'   ;End with ")"?
                jne     T_Failed                ;Fail if no.
                inc     di                      ;Skip ")"
                add     sp, 2                   ;Don't restore di,
                stc                             ; we've succeeded.
                ret

T_Failed:       pop     di
                clc
                ret
T               endp


; The following is a free-form translation of
;
; G -> H | H G
; H -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
;
; This routine checks to see if there is at least one digit. It fails if there
; isn't at least one digit; it succeeds and skips over all digits if there are
; one or more digits.

G               proc    near
                cmp     byte ptr es:[di], '0'   ;Check for at least
                jb      G_Failed                ; one digit.
                cmp     byte ptr es:[di], '9'
                ja      G_Failed

DigitLoop:      inc     di                      ;Skip any remaining
                cmp     byte ptr es:[di], '0'   ; digits found.
                jb      G_Succeeds
                cmp     byte ptr es:[di], '9'
                jbe     DigitLoop
G_Succeeds:     stc
                ret

G_Failed:       clc                             ;Fail if no digits
                ret                             ; at all.
G               endp


; This main program tests the matching functions above and demonstrates
; how to call the matching functions.

Main            proc
                mov     ax, seg dseg            ;Set up the segment registers
                mov     ds, ax
                mov     es, ax

                printf
                byte    "Enter an arithmetic expression: ",0
                lesi    InputLine
                gets
                call    E
                jnc     BadExp

; Good so far, but are we at the end of the string?

                cmp     byte ptr es:[di], 0
                jne     BadExp

; Okay, it truly is a good expression at this point.

                printf
                byte    "'%s' is a valid expression",cr,lf,0
                dword   InputLine
                jmp     Quit

BadExp:         printf
                byte    "'%s' is an invalid arithmetic expression",cr,lf,0
                dword   InputLine

Quit:           ExitPgm
Main            endp

cseg            ends

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

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


16.1.7 Some Final Comments on CFGs


The techniques presented in this chapter for converting CFGs to assembly code do not work for all CFGs. They only work for a (large) subset of the CFGs known as LL(1) grammars. The code that these techniques produce is a recursive descent predictive parser. Although the set of context free languages recognizable by an LL(1) grammar is a subset of the context free languages, it is a very large subset and you shouldn't run into too many difficulties using this technique.

One important feature of predictive parsers is that they do not require any backtracking. If you are willing to live with the inefficiencies associated with backtracking, it is easy to extended a recursive descent parser to handle any CFG. Note that when you use backtracking, the predictive adjective goes away, you wind up with a nondeterministic system rather than a deterministic system (predictive and deterministic are very close in meaning in this case).

There are other CFG systems as well as LL(1). The so-called operator precedence and LR(k) CFGs are two examples. For more information about parsing and grammars, consult a good text on formal language theory or compiler construction (see the bibliography).


16.1.8 Beyond Context Free Languages


Although most patterns you will probably want to process will be regular or context free, there may be times when you need to recognize certain types of patterns that are beyond these two (e.g., context sensitive languages). As it turns out, the finite state automata are the simplest machines; the pushdown automata (that recognize context free languages) are the next step up. After pushdown automata, the next step up in power is the Turing machine. However, Turing machines are equivalent in power to the 80x86, so matching patterns recognized by Turing machines is no different than writing a normal program.

The key to writing functions that recognize patterns that are not context free is to maintain information in variables and use the variables to decide which of several productions you want to use at any one given time. This technique introduces context sensitivity. Such techniques are very useful in artificial intelligence programs (like natural language processing) where ambiguity resolution depends on past knowledge or the current context of a pattern matching operation. However, the uses for such types of pattern matching quickly go beyond the scope of a text on assembly language programming, so we will let some other text continue this discussion.
16.1.3 - Context Free Languages
16.1.4 - Eliminating Left Recursion and Left Factoring CFGs
16.1.5 - Converting REs to CFGs
16.1.6 - Converting CFGs to Assembly Language
16.1.7 - Some Final Comments on CFGs
16.1.8 - Beyond Context Free Languages


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: