The Education Master 1994 (4th Edition)

home *** CD-ROM | disk | FTP | other *** search

/ The Education Master 1994 (4th Edition) / EDUCATIONS_MASTER_4TH_EDITION.bin / files / progscal / tinypasc / tu.doc < prev next >

Wrap

Text File | 1986-06-03 | 97.6 KB | 2,047 lines

Pascal in 25 Rules or Less William A. Barrett QCAD Systems, Inc., 1164 Hyde Ave, San Jose, CA 95129 In this article, we're going to design and implement a small subset Pascal compiler, using the Turbo Pascal compiler and a couple of other software tools that you can purchase for a nominal charge. It is capable of translating a Pascal subset program into 8086 symbolic assembly language, which can then be assembled into a running program on an IBM PC. When you look at our tiny Pascal, it may strike you as being so ridiculously simple that it has no useful applications. However, as we'll explain, it provides all the important features of a high-level programming language, and can be extended indefinitely by writing more support functions. By reading this article, or better, by ordering the support software described at the end of this article, you will not only have your own extensible compiler going, but will have learned how language translators and compilers are organized and written. So... carry on, please! Tiny Pascal Features A full Pascal language, like Turbo, has about a hundred features, and a large support library. We're going to choose just a few features, and simplify the language to such an extent that it probably isn't fair to call it Pascal -- it just resembles Pascal in some ways. In particular, we want a description of our language in just twenty-five production rules or less, since the Qparser demo pack supports just that many. Twenty-six rules, and the demo system won't work! Does this sound like a contest you've entered? Anyway, we've managed to pack all this into those twenty-five rules: * All four arithmetic operations in full expressions -- but on 16-bit integers only. * Assignment, IF-THEN-ELSE, BEGIN-END blocks, and WHILE-DO. * Functions with parameters * READ, WRITE, WRITELN with limited string support * Global variables * Integer literals Although our feature list is very short, it's large enough to write some impressive and useful programs. The reason is that tiny Pascal supports functions that can return values. If you need a capability, then you can always write a function to provide that capability. A Tiny Pascal Program A complete program written in tiny Pascal follows this paragraph. You should be able to follow what it does. When you run this through the tiny Pascal compiler, you will get page 1 Pascal in 25 Rules or Less an assembler program that is ready to be assembled and executed on your PC. That program will also contain all the high-level tiny Pascal statements as comments. The fully compiled and assembled listing is given near the end of this article. {TURUN -- A sample program written in Tiny Pascal } var I, J, K, PROBLEM; {*********************} function ISLESS(N1, N2); begin {returns 1 if n1<n2, 0 otherwise} if n2-n1 then isless:=1 {truth value test is >0} else isless:=0; end; function ADDEMUP(LOWER, UPPER, SUM); begin end; {makes it a forward declaration} {*********************} function ISEQUAL(N1, N2); begin if n2-n1 then isequal:=0 {false} else if n1-n2 then isequal:=0 else isequal:=1; end; {***********************} function ADDEMUP(LOWER, UPPER, SUM); {SUM is a local} begin sum:=0; while isless(lower, upper) do begin sum:=sum+lower; lower:=lower+1; end; addemup:=sum+lower; { the last one was left out } end; {*********************} function MAIN(SUM, UPPER); begin i:=1; j:=i+5; k:=j-16; problem:=i+(j*k); writeln('I: ', i, ' J: ', j, ' K: ', k, ' Problem: ', problem); write('Enter upper '); upper:=read; sum:=addemup(1, upper); {sum of integers 1..upper} if isequal(sum, (upper*(upper+1))/2) then writeln('Sum = ', sum) else begin writeln('BUG: Sum = ', sum, '; should be ', (upper*(upper+1))/2); end; end; page 2 Pascal in 25 Rules or Less More About Tiny Pascal Our functions pass parameters by VALUE only -- there's no VAR parameter capability. However, a function can return an integer value, or it can set the value of a global variable. That's a bit awkward sometimes, but it's still better than assembler. There are no Boolean data types as such, but the language uses 0 and 1 as a substitute where necessary. In particular, the expression in an IF or a WHILE tests an integer value for greater-than-zero (true) or less-than-or-equal-to-zero (false). That's good enough. For example, you would write if n1-n2 then ... in tiny Pascal, which is equivalent to if n1-n2>0 then ... or if n1>n2 then ... in full Pascal. The comparison operators can of course be added with more production rules. There are also no local variables in tiny Pascal, but it turns out they really aren't needed. For example, function ADDEMUP(LOWER, UPPER: integer): integer; var SUM: integer; begin ... end; in full Pascal can be written function ADDEMUP(LOWER, UPPER, SUM); begin ... end; in tiny Pascal. Note that we don't bother with the type designators (i.e. : integer) since only one type is supported. Also our compiler is arranged so that if ADDEMUP is called with only two parameter values, SUM is initialized to 0. For example, addemup(5, 10) causes LOWER=5, UPPER=10, and SUM=0 inside ADDEMUP. So you see the extra formal parameters have the same effect as the local variables in full Pascal. Of course, you can also call ADDEMUP with all three parameters, or none -- that's an unsafe defect in tiny Pascal which can't be avoided with our tight production rule limit. You'll just have to be sure to call functions with the correct number of parameters. Functions can be called within expressions, or on a line by themselves. For example, both of these statements are OK: addemup(5, 10); {returned value is ignored} x := y - addemup(5, 10); {returned value is subtracted page 3 Pascal in 25 Rules or Less from y} Literal strings are permitted only within a WRITE or WRITELN statement; they're intended to decorate messages to the standard output device only. If you want strings to appear in expressions and other functions, then you will have to introduce declarations for them and type designators -- that'll take more productions. READ and WRITE Tiny Pascal supports three I/O functions: READ, WRITE and WRITELN. READ is called with no parameters, and returns an integer value entered at the keyboard. WRITE takes any number of integer expressions or strings, and writes them to the console screen in left-to-right order. No line return is emitted at the end, so you can call WRITE several times before sending a line return. WRITELN is the same as WRITE, except that it emits a line return after writing its parameters. Both these can take no parameters if you like -- WRITE does nothing, and WRITELN emits a return. It happens that our integers will be read or written in hexadecimal for simplicity, but you can easily change the STDIO.HDR file to support decimal notation instead. The MAIN Program There must be one function whose name is MAIN in each tiny Pascal program. That'll be the first function called. It may have parameters, but we haven't provided any way of passing parameters to it from the console -- Turbo parameters are strings anyway and would have to be translated into integers somehow. MAIN can of course call any other procedure, and it's through procedure calls and use of the control structures that algorithms can be built up. Recursion and FORWARD Functions Tiny Pascal supports recursion -- a function can call itself any number of times. Each time a function is called, its local variables are pushed onto a runtime stack, along with its return address. A special 8086 register -- the BP register -- is used to mark the position of these variables so that they can be accessed from within a function. We'll explain just how that works later. Sometimes you'll have a procedure A that calls B that calls A. The problem is that A needs a declaration for B. You can supply that in tiny Pascal by writing a function for B with an empty Stmt, like this: function B(P1, P2); begin end; You can even omit the begin end; if you want to. The tiny Pascal compiler will recognize this as a so-called forward declaration. In full Pascal, you'd write it like this: page 4 Pascal in 25 Rules or Less function B(P1, P2: integer): integer; forward; The Grammar Computer languages are described by a context-free grammar, which is just a list of production rules. Here's the grammar for tiny Pascal, all twenty-five rules of it: \ TU.GRM -- tiny Pascal grammar held to 25 productions Goal -> FDeclList FDeclList -> FDeclList FuncDecl ; -> FuncDecl ; FuncDecl -> FUNCTION <identifier> ( ExprList ) ; Stmt #FDECL -> VAR ExprList #VDECL \ Global variables \ ExprList must be identifiers only Stmt -> <identifier> := Expr #ASSIGN -> IF Expr THEN Stmt ELSE Stmt #IFTHEN -> WHILE Expr DO Stmt #WHILEDO -> BEGIN StmtList END #BLOCK -> Expr #SEXPR \ procedure call only! StmtList -> StmtList Stmt ; #STLIST2 -> <empty> Expr -> Expr + Term #ADDOPR -> Expr - Term #SUBOPR -> Term Term -> Term * Primary #MPYOPR -> Term / Primary #DIVOPR -> Primary Primary -> ( Expr ) #PAREN -> <integer> \ only type INTEGER supported -> <string> -> <identifier> \ variable or function call w/o parameters -> <identifier> ( ExprList ) #FUNCP ExprList -> ExprList , Expr #EXPRLIST2 -> Expr #EXPRLIST1 First, a word about the notation. Each rule takes up one line. A backslash starts a comment, which runs to the end of the line. The pound sign (#) marks a production flag, which we'll use as a kind of handle in the compiler's parser. A rule with nothing to the left of the symbol -> is assumed to have the same symbol as the preceding rule. For example, the third rule is written -> FuncDecl ; but actually means FDeclList -> FuncDecl ; The first rule, with the left member Goal, expands into a complete tiny Pascal program. From the second and third rules, a program is a sequence of FuncDecl, separated by semicolons. Each FuncDecl in turn is either a FUNCTION declaration or a VAR declaration, according to the fourth and fifth rules. In fact, we will insist that a program consist only of some page 5 Pascal in 25 Rules or Less VAR declarations (the global variables) followed by the FUNCTION declarations. Each FUNCTION declaration carries a name (the <identifier>), an expression list (with at least one expression), and a statement Stmt. Note that a Stmt can be a list of statements StmtList enclosed in a BEGIN-END pair, so that the body of a function can consist of one, two, three or more statements. There are four kinds of statement, an assignment, an IF-THEN-ELSE, a WHILE-DO, a BEGIN-END block, and an expression -- which in fact must be just a function call. Note that the ELSE must always be present in an IF-THEN-ELSE, unlike full Pascal. Also note that Stmt can be <empty>, i.e. absent. Thus if a-b THEN ELSE BEGIN ... END is a legal statement. For expressions, we support all four arithmetic operations on our integers, as well as parenthesizing. The production rules guarantee that the usual Pascal precedence rules apply, and that things inside parentheses will be evaluated first. The form <integer> stands for any unsigned integer. <string> stands for a Pascal literal string, for example 'Here is a Pascal string' The form <identifier> stands for any legal Pascal name. Inside an expression, the name could stand for a global or local variable, or a function name. As a function name, the function will be called with zero or more parameters, returning some value. Compiler Overview Let's first take a broad look at our compiler, then we'll look at some of the details. We need to look at the forest before we study the trees. (The details are in fact voluminous as you might expect, and are best examined from the source files directly using your favorite editor.) We'll be using a compiler generator tool for the backbreaking part of the job -- our choice is called Qparser, and is available from QCAD Systems, Inc. Qparser accepts the 25-rule grammar we've written above and generates a complete Pascal program from it automatically. All you have to do is run two programs called LR1 and LR1P with the appropriate file names, and you'll get a Turbo Pascal source file. (Specific instructions are included with the product.) Now Qparser only generates a parser -- that's a program that will take a tiny Pascal source file and break it down into small steps. Each step will be a production rule reduce or apply operation. We need to add some more Pascal source code to that `front-end' compiler, to get it to generate assembler code. In particular, the compiler will: page 6 Pascal in 25 Rules or Less 1. Construct an abstract syntax tree (AST) for a whole function. This will be built from unit records allocated from the heap, linked together with pointers in various ways. The AST will carry a complete description of all the variables, statements, expressions, function calls, etc. in the function. 2. When a function AST is complete, its local variables will be added to a symbol table, along with their positions relative to register BP. 3. Then the statements and expressions are turned into 8086 assembly code through a recursive tree-walking procedure called EVAL. EVAL is rather simple to describe, and -- as we shall see -- produces rather tight 8086 code for our integer operations, assignments, function calls, IF-THENs, and WHILE-DOs. It's also easy to understand, extend or modify. The tiny Pascal compiler acts somewhat like a batch compiler -- it collects all the lines for a function, then emits all the code for the function. We've tried to make the resulting assembly code easy to read by copying the function source lines as comments, and by writing the names of local variables as comments. (Local variable references will all appear as offsets from register BP in the assembly code, rather than as names.) Designing the Compiler Once we've written the grammar, we can pass it through Qparser, then try out the automatically-generated parser on a sample program -- such as TURUN given earlier. That will verify that our grammar describes what we expect it to. The next big step is designing compiler data structures to support the AST that will hold all the features of a complete function. It turns out that's easy to do, too -- the Qparser files contains a sample Pascal record structure designed for that purpose, called a SEMREC. Here's what the generic SEMREC looks like as supplied in the Qparser software: type SEMTYPE = (OTHER, IDENT, FIXED, STRNG); SEMRECP = ^semrec; SEMREC = record case SEMT: semtype of { semantic stack structure } ident: (SYMP: symtabp); fixed: (NUMVAL: integer); strng: (STX: integer); {index to string table} end; This supports only three kinds of object: an identifier, a fixed-point integer and a string. Identifiers are actually written into a symbol table -- the symtabp is a pointer to a symbol table record. An integer has a value, NUMVAL. A string is written to a global packed array of char called STRTAB, starting at the index STX, and ending on a chr(0). Note that the type SEMRECP is a pointer to a SEMREC. We're going to build our AST around a tree whose nodes are page 7 Pascal in 25 Rules or Less linked by SEMRECP pointers. Each of the SEMREC structures will be allocated from the Pascal heap as needed, and we'll dispose of them all after we're through with them, at the end of scanning a tiny Pascal function. Arithmetic Operators The AST for the four arithmetic operators is the easiest to grasp. We extend SEMREC to these operators by adding two lines to our SEMREC declaration. The result is: SEMREC = record case SEMT: semtype of { semantic stack structure } ident: (SYMP: symtabp); fixed: (NUMVAL: integer); strng: (STX: integer); {index to string table} addop, subop, mpyop, divop: (LEFT, RIGHT: semrecp); end; Of course, we also need to add the enumerated type names addop, etc. to the SEMTYPE list: SEMTYPE = (OTHER, IDENT, FIXED, STRNG, ADDOP, SUBOP, MPYOP, DIVOP); Let's look at an example of an arithmetic expression and see how it is expressed as an AST: X * (Y-Z) / 15. Figure 1 shows the AST we want. The - operator must be performed first, since we need its result before the * operator, and it in turn is needed before the division / can be performed. This ordering is clearly dictated by an inflexible AST rule: the children of a node must be evaluated before the node itself. The leaves of our tree are identifiers (X, Y, Z) or numbers (15). A number clearly stands for itself, while each identifier stands for some numeric value at runtime. In fact, an identifier will be associated with some memory address whose contents will be fetched in an appropriate instruction. Let's next see how the AST of figure 1 would be described by SEMREC structures linked by pointers. That's shown in figure 2, where each SEMREC is a box, and its LEFT and RIGHT pointers are connected to other SEMREC boxes. The root is a SEMREC whose SEMT=divop. Its LEFT child is another SEMREC whose SEMT=mpyop. The leaves are also SEMREC's, since a SEMRECP pointer must point to a SEMREC, but the leaf nodes are either SEMT=ident or SEMT=fixed. The ident nodes point to a symbol table entry which will carry the identifier name, its type, its address and possible other information. How the AST is Built The AST will be built through parser actions. We don't have the space here to go into the theory of the parsing machine -- that's described in several different references [1, 2]. However, we'll try to explain enough to see how our page 8 Pascal in 25 Rules or Less AST gets built. Let's look at our arithmetic expression again: X * (Y-Z) / 15. When the parser scans this, it will go through the following sequence of production steps: Primary -> <identifier> ; <identifier> = X Primary -> <identifier> ; <identifier> = Y Primary -> <identifier> ; <identifier> = Z Expr -> Expr - Term #SUBOPR ; Y - Z Primary -> ( Expr ) #PAREN ; (Y-Z) Term -> Term * Primary #MPYOPR ; X * (Y-Z) Primary -> <integer> ; 15 Term -> Term / Primary #DIVOPR ; X * (Y-Z) / 15 Expr -> Term We've left out several intermediate steps, but these are the important ones. Essentially, a derivation of our expression is being reconstructed in reverse order -- we start with the expression, match various production right parts to the expression, and eventually end up with a single expression node -- Expr. Notice how the identifiers X, Y and Z are picked up first and `reduced' to a Primary. Then the Y and Z primaries are combined in the SUBOPR production. That agrees with our notion that the subtraction has to come first. The parentheses are covered by the PAREN production; we can then reduce the multiplication with the MPYOPR production. The integer 15 gets scanned next; we didn't need it until now, but it's involved in the division, and finally the division is covered through the DIVOPR production. This sequence of events is the same as if we evaluated the expression with a reverse-Polish calculator, like those manufactured by the Hewlett-Packard Co. We enter X, then enter Y, enter Z, subtract, multiply, enter 15 and divide. On each `enter', a value is pushed into a stack, which saves it for future reference. Each operation is between a number on the stack top and a number just below it; the stack is popped and the result appears on the stack top. Thus when the multiply is performed, it acts on the two operands X and (Y-Z). When the divide is performed, it acts on the operands X*(Y-Z) and 15. Using the Semantics Stack Qparser also provides a stack that works almost like that on a reverse-Polish calculator. The difference is that the Qparser stack can be very deep, and it is keyed to production apply actions. Let us explain what that means -- it's crucial to understanding how our AST is built. Qparser's stack is called SEM. SEM is declared as an array of SEMRECP pointers. The stack top index is named TOS, which increases as more items are pushed onto the stack and decreases as the stack is popped. Thus SEM[TOS]^ points to a SEMREC object on the top of the stack; SEM[TOS-1]^ points to an object just below the stack top, etc. (SEM[n] may also be NIL, which means there is no object.) Now the Qparser software will perform the following page 9 Pascal in 25 Rules or Less services for you in response to scanning its input source: 1. Each tagged production will cause procedure APPLY to be called with an integer parameter that designates the production. The APPLY procedure looks like this: procedure APPLY(PFLAG: integer; var TSEMP: semrecp); begin case PFLAG of ADDOPR: ... ASSIGN: ... BLOCK: ... etc. WHILEDO: ... VDECL: ... end end; Note that PFLAG causes an immediate branch to one of the legs of the CASE statement -- a leg that corresponds to one particular production. 2. When a production such as Term -> Term * Primary is invoked through an APPLY call, the top three SEM stack elements will be aligned with Term, *, and Primary, respectively. SEM[TOS] will point to something associated with Primary, SEM[TOS-1] will be NIL (since * needn't carry information), and SEM[TOS-2] will point to something associated with Term. This is an important concept, and is illustrated in figure 3. Just before our APPLY action, the stack has three elements on its top, which carry pointers to the roots of the trees X and (Y-Z), respectively. (See figure 2 for the whole tree.) 3. In the APPLY procedure, you have an opportunity to do something about the SEM information, and to return a pointer to a SEMREC through the var parameter TSEMP. Consider production Term -> Term * Primary again (figure 3). We assume that SEM[TOS-2] (= Term) points to a tree node, as does SEM[TOS] (= Primary). We want to construct a new SEMREC tree node whose SEMT is MPYOP, whose LEFT will point to Term and whose RIGHT will point to Primary. TSEMP will be assigned to point to this new node. That's easy -- here's the Pascal code fragment needed for the job: MPYOPR: { Term -> Term * Primary } begin new(tsemp); {allocate a new node} with tsemp^ do begin {and fill in its record fields} left:=sem[tos-2]; {points to Term} right:=sem[tos]; {points to Primary} semt:=mpyop; end end; 4. When APPLY returns, the var parameter TSEMP is returned to the parser, which will (a) strip off the top three pointers on the SEM stack then (b) push the TSEMP pointer. Notice that the top three pointers have already page 10 Pascal in 25 Rules or Less been linked to TSEMP, so losing them is no big deal. By pushing TSEMP on the stack, we have effectively associated our new tree root with the Term on the left side of the production Term -> Term * Primary. Refer to figure 4. This is how the stack will look just after returning from APPLY. The top three pointers have been scraped off, and replaced by the TSEMP pointer. We clearly have a larger tree rooted in the stack top -- again look at figure 2 for the whole tree, and you'll see that we've added one node to it. That closes the loop on our operations. Eventually our new Term will show up again in the APPLY procedure, this time as an element in the right part of some production; it will carry the root of a tree, and that tree will get built into something bigger. Certain actions are done for us automatically by the parser and lexical analyzer system of Qparser -- the <identifier>, <integer> and <string> forms are loaded into the SEM stack automatically when and where they are needed. For example, consider the production Stmt -> <identifier> := Expr, tagged ASSIGN in our production set. When this pops up in an APPLY call, there will be a SEMREC pointer in SEM[TOS-2] that corresponds to the <identifier>; it will carry the tag SEMT=ident, and the SYMP pointer will point to a symbol table entry that corresponds to the identifier. Single productions needn't be tagged -- the parser will preserve whatever is attached to the right member, passing it along to the left member. (A single production has exactly one token in its right member, for example Primary -> <identifier>). Also, TSEMP is by default NIL, so if we choose not to set TSEMP, a NIL will be pushed on the stack. Other Tree Nodes Well, we've seen how an arithmetic expression is built up as an AST. The same principle can be applied to any form in our language. Let's look at some others. Consider the assignment production Stmt -> <identifier> := Expr, tagged ASSIGN. We'll use the tag SEMT=assignop for it, and use our friends LEFT and RIGHT as pointers to the <identifier> and Expr. The APPLY code that builds this tree node looks almost the same as for the multiply case: ASSIGNOP: { Stmt -> <identifier> := Expr } begin new(tsemp); {allocate a new node} with tsemp^ do begin {and fill in its record fields} left:=sem[tos-2]; right:=sem[tos]; semt:=assignop; end end; In fact, it looks so much alike that we've created a procedure that deals with all these binary operator cases, called BIN_TREE; this takes one parameter, the SEMT value, and expects to find a LEFT node in SEM[TOS-2] and a RIGHT page 11 Pascal in 25 Rules or Less node in SEM[TOS]. Not all the tree nodes have binary operators. Let's look at an expression list, which is carried by two productions: ExprList -> ExprList , Expr #EXPRLIST2 -> Expr #EXPRLIST1 These don't look quite like our binary operators, but in fact can be handled in a very similar way. We'll create yet another SEMT enumerated type EXPR_LIST with a LEFT and RIGHT. LEFT will point to an expression subtree, but RIGHT will be NIL or point to another EXPR_LIST. Figure 5 shows the general idea for a list of two subtrees. (This structure is borrowed from Lisp -- the LEFT pointer acts like CAR and the RIGHT pointer acts like CDR). The code for these two productions looks like this: EXPRLIST1: { ExprList -> Expr } if not(is_void(sem[tos])) then begin tsemp:=new_sem(expr_list); tsemp^.left:=sem[tos]; end; EXPRLIST2: { ExprList -> ExprList , Expr } if not(is_void(sem[tos])) then begin tsemp:=new_sem(expr_list); tsemp^.left:=sem[tos]; tsemp:=nconc(sem[tos-2], tsemp); end else tsemp:=sem[tos-2]; Some new functions are shown in this code fragment. NEW_SEM allocates a SEMREC from the Pascal heap using NEW, and assigns its SEMT to the passed parameter. More importantly, it also initializes LEFT and RIGHT (or other pointers) to NIL, rather than letting them be garbage. NEW_SEM is always used rather than NEW directly in order to achieve this useful initialization. The IS_VOID function tests its SEMREC parameter for NIL. Finally, NCONC takes two parameters, a list L and an element E. It attaches the element to the end of the list by altering the RIGHT pointer of the last element of the list L to point to the element E. (Again, this is inspired by the Lisp function of the same name). Let's now look at these operations in more detail. The EXPRLIST1 operation must either return NIL or an EXPR_LIST that points to the Expr. It turns out that Expr will never be NIL, but we've written it this way for robustness. The EXPRLIST2 operation looks at the Expr; if it is NIL, then we can simply return the pointer to the ExprList (it, too, may be NIL). If Expr isn't NIL, then we call NCONC to stitch it onto the end of the ExprList, as suggested by figure 5. Function Declaration It's time to consider the function declaration production FuncDecl -> FUNCTION <identifier> ( ExprList ) ; Stmt page 12 Pascal in 25 Rules or Less #FDECL When this pops up in an APPLY action, we have scanned through the function name (the <identifier>), its parameter list (ExprList), and its body (the Stmt). Assuming we've done all our AST building correctly, the ExprList and Stmt are the roots of some trees, possibly very large. The scanning and parsing action have worked through the function declaration completely, but we haven't (1) generated any code, nor (2) done anything about declaring the procedure or its parameters. In fact, we need to perform these actions in this order: 1. Add the function identifier to the symbol table at the global scope level, if it isn't already there. (It could have been previously declared with an empty Stmt part, i.e. as a forward.) 2. Raise the scope level by one. 3. Add the ExprList identifiers to the symbol table, checking each one for multiple declarations. These should each be a single identifier rather than an expression; we can easily test their tree roots for this case and complain about an error. We did it this way to save on productions. Each of the identifiers will be assigned a location in the stack relative to base register BP -- we'll explain how that works shortly. 4. Evaluate the Stmt tree. A recursive procedure is needed for this that will work through the entire statement tree, emitting code appropriate to each of the forms in our language. We'll see that this is much easier than it appears on the surface and is almost trivial for some of the language forms. All we need are some simple translation forms in 8086 assembler and our AST will unfold very neatly into code. During the evaluation phase, every identifier will have a pointer to a symbol table entry which will carry a relative address and a type for the name. That will be useful in generating instructions for the identifier. The Symbol Table We need to describe our symbol table system. There are various ways of organizing symbol tables; we're going to focus on the one used in the Qparser system. User names are associated with the <identifier> form in the grammar. The default <identifier> form is a Pascal name -- something that starts with a letter and continues with letters, digits, or underscores. The first character that isn't in this set stops the name -- it could be a space, a left parenthesis, or whatever. Names will be upper cased as in Pascal. Note that certain keywords look like identifiers, for example, IF, WHILE, BEGIN, etc. The lexical scanner scans one of these as though it were an identifier, then searches the symbol table for it. The keywords have previously been entered and tagged as such, therefore a successful `find' will immediately indicate that the supposed identifier is in fact a keyword. Making this distinction is vital to the page 13 Pascal in 25 Rules or Less parser, since the keywords are important clues to recognition of the program phrases. If the identifier isn't a keyword, it will be entered anyway under an innocuous tag (user). Now that we've discussed how the symbol table works in general, let's look at the symbol table record structure: type SYMBOL = string[maxtoklen]; SYMTYPE = (RESERVED, SYMERR, USER, VAR_TYPE, FUNC_TYPE); SYMTABP = ^symtabtype; SYMTABTYPE = record { structure for <identifier>s and keywords } NEXT: symtabp; LEVEL: int; SYM: symbol; case SYMT: symtype of reserved: (TOKVAL: tokrange); var_type: (VADDR: integer); {relative to BP} func_type: (FADDR: integer; {code location} PBYTES: integer; {bytes of parameters} IS_ACTUAL, {TRUE if an actual declaration has been seen} IS_SYSTEM {system procedure, demands special treatment} : boolean); end; There are five classes of symbol. RESERVED is for the keywords. SYMERR is used during error recovery when the parser needs to make up an identifier for insertion purposes. USER is a generic name attached to user identifiers when they are first seen. VAR_TYPE refers to the global and local variable names -- its VADDR field provides (in the local case only) an offset from BP. FUNC_TYPE refers to a declared function. These are somewhat complicated in our tiny Pascal. FADDR actually isn't used, but could be to refer to a code location. Since we generate symbolic assembly code, we will just produce a symbol procedure label and let the assembler worry about where the function will be located. PBYTES is the number of bytes of formal parameters the function carries. We need this in order to generate an appropriate EXIT instruction, and also to generate calls. IS_ACTUAL will be false until a declaration with a full statement body is seen; after that, IS_ACTUAL will be true. We use this to catch such errors as undeclared functions and two functions with full statement bodies. IS_SYSTEM designates the function as a `system' function, slated for special handling. Our WRITE, WRITELN, READ and a couple of other functions are in this class. These are supported by special assembler routines and aren't called quite the same way as user-declared functions. A symbol name is stuffed in SYM, which is just a string. NEXT carries a link to another SYMTABTYPE record, and is page 14 Pascal in 25 Rules or Less used in a hash table linked-list system for rapid symbol searching. The LEVEL parameter designates the scoping level of the name. Reserved names are carried at level -1. Global names are at level 0 and locals at level 1. In full Pascal, the LEVEL would be incremented by one for every descent into a lexically nested procedure or function. Tiny Pascal supports only one global level of procedures, so LEVEL never exceeds 1. There are several major symbol table actions of interest in tiny Pascal. Reserved names are pushed into an otherwise-empty table as the first action of the compiler, at level -1. This action is essentially automatic by virtue of the Qparser generator. When an <identifier> form is seen, the identifier string is picked up by the lexical analyzer and entered in the table, if not already there. The analyzer also builds a SEMREC structure of type IDENT and pushes it into the SEM stack at the appropriate place. APPLY will therefore `see' an IDENT structure of type USER upon the first appearance of some user identifier. Eventually, we choose to add attributes to the identifier. This will occur when a production appears that reveals what attributes are required. In tiny Pascal, that production is the FuncDecl production FDECL. The action required is to scan through the ExprList, and change the attributes of the names to VAR_TYPE, assigning VADDR values as we go. Correction: if the name doesn't carry a USER tag, it may have been previously declared as a global variable or a function; we need to override the previous use without destroying the previous use. Our symbol table scheme permits doing that by carrying successive names in a first-in-first-out stack organization. Once these names have been declared, there will be no further declarations of names in the function body; only references to names that should previously have been declared. These name references will show up as we scan the AST in the EVAL function. Among other things, we watch out for identifiers carrying a USER tag -- these haven't been declared anywhere and deserve an error complaint. Getting Rid of Unwanted Names When the function body has been fully evaluated and all code generated, we need to get rid of the local variables in the symbol table. A function called CLEARSYM does the trick. It locates all the names in the symbol table whose LEVEL is greater than 0, and removes them from the table. That's important, since the scope of a function's local variables is the lexical range of that function and no further. By doing this, we make it possible to use the same name in different procedures without confusing the compiler or assembler. page 15 Pascal in 25 Rules or Less The Run Time Environment We need to describe how we propose to generate 8086 code from our AST. (If you're not familiar with the 8086, we recommend [3] as a reference.) There are four kinds of code generation problem confronting us: 1) Function declaration -- what assembler forms are needed to open a function and what are needed to close it? 2) Function call -- how are the parameters passed and how is the call generated? 3) Expression and assignment evaluation -- how are the register and memory instructions used to maximum benefit and efficiency? 4) Control structures -- how are the conditional and unconditional branches to be coded? We'll address each of these in turn. Unfortunately, items (1) and (2) depend on each other. Our procedure call strategy must be defined before we can decide on just how a call and a declaration are to be carried out. That will also determine how our local variable addresses are computed. So let's look at function calls first. Function Call Environment Our language is intended to support recursion, which means that a given function may have been called several times before any exit has taken place. Each of these uncompleted calls is called an activation, and each activation requires an activation record that contains a set of local variable values, a return value and a return address. The activation records will be carved out of the 8086's stack, where the stack top is pointed to by register SP. The micro's stack will also be used to hold temporary expression values, so SP will be moving up and down in a somewhat unpredictable fashion. We need a way of marking the position of the activation record that doesn't depend on SP. The current activation record will be pointed to by register BP. Figure 6 shows our activation record design. The stack top is at the bottom, perversely. (Does that mean that we programmers don't know which way is up?) In the 8086, the PUSH operation causes SP to decrease in numeric value -- the stack will start at the end of some segment and work toward its beginning. The figure shows an activation record for a function with three parameters, P1, P2, and P3, in left-to-right order, as it might appear when we're ready to start executing some function body instructions. However, the record got that way partly through call operations and partly through code at the front end of the function. The function call will 1) reserve space for a function return value through a PUSH AX operation, 2) PUSH each parameter in their order of appearance, and then 3) CALL the function. The CALL instruction will push the return address on the stack. At this point, SP will point to the stack top page 16 Pascal in 25 Rules or Less (of course), and BP will be pointing at some previous activation record deeper in the stack. Among the first instructions executed within the function will be PUSH BP MOV BP,SP The first of these pushes the previous value of BP in the stack, and the second sets BP to the new stack top. Notice that parameter P1 is at BP+8 (each stack location is a 2-byte word), P2 is at BP+6, P3 is at BP+4, and the function return value is at BP+10. These offsets can be calculated by the compiler and associated with each of the respective names. Furthermore, the 8086 instruction set and our assembler permit us to use forms like 8[BP] to refer to an address offset from BP by +8 bytes. We can therefore easily generate symbolic address references to any of the function's variables. Function EXIT An EXIT from a function is similarly easy. We need to restore the previous BP value to the one carried at BP in the stack, then return, popping the right number of parameters from the stack. For the configuration of figure 6, we therefore need POP BP RET 8 We overlooked one thing -- since we are dealing with a function, it's important to send the return value back to whatever expression the function was called from. We're going to adopt the convention that every expression will yield its value in the 16-bit AX register. However, our function's return value is in the stack. We therefore need the instruction MOV AX,10[BP] before we POP BP. Then we can remove the parameters and return value from the stack upon a RET instruction. Note that the `10' in this instruction is equal to 4 plus twice the number of parameters of the function. Also the `8' in the RET instruction is 2 plus twice the number of parameters. Function CALL Before we discuss function calling, we need to assert something about the way expressions will be evaluated. We will write a general-purpose procedure called EVAL that takes an expression root (a SEMREC pointer), then generates code such that the arithmetic result of the tree will be left in the AX register. By asserting this first, we can design EVAL to make sure that that is in fact what will happen in every case. We can also use EVAL itself to deal page 17 Pascal in 25 Rules or Less with subtrees, with assurance that AX will receive the result. Of course, it's important that EVAL never change the value of BP or set SP capriciously. It may push some stuff on the stack, but we'll also make sure that whatever is pushed will eventually be popped. Certain other 8086 registers may also be used in very local situations, for example in connection with a multiply or divide instruction. Given that EVAL will take an AST tree and produce code for AX, calling a function will be very easy. In fact, the function call will show up in EVAL itself, whenever we see the SEMT=funcall! Here's what we need to do (refer to figure 6): PUSH AX ; this reserves a return value word eval(P1) ; parameter P1 is evaluated, result to AX PUSH AX ; push result on the stack eval(P2) PUSH AX etc. CALL function We can of course just use the function name in the CALL instruction, since the assembler can figure out where it is. Note that this code sequence will work nicely within an expression, since the result of the CALL is to pop down the stack to exactly the place just before the first PUSH AX, and to yield the function's result in AX. We can also use this sequence for a procedure call, where the return value is ignored. AX will just get lost, and there's no change in the stack. ADD and SUB Let's now turn our attention to evaluating other expressions. We need to take a close look at the 8086 instruction set and decide just how to handle arithmetic. We find that integer addition and subtraction are handled alike, but are coded somewhat differently than multiplication and division. Our ADD or SUB will be between AX and some operand, which may be another register value, an immediate value, a memory value or an indirection through a register. Our AST will look like figure 7. We imagine that the LEFT subtree will somehow yield AX -- that's easy if we just call EVAL on the LEFT subtree. We would then like to emit an ADD or SUB instruction whose operand is the right subtree. Unfortunately, that's not possible if the right subtree is anything other than 1) a literal value, i.e. SEMT=fixed, or 2) a global variable, or 3) a local variable. A global variable can be accessed by its name alone, while a local will be accessed as an offset through BP, e.g. 6[BP]. So before we just go ahead and evaluate the LEFT subtree, we need to test the RIGHT subtree -- is it `simple', i.e., will it fit into an ADD or SUB instruction operand field? If it is, then we can just EVAL(LEFT), then emit the appropriate ADD or SUB instruction. The more difficult case in fact requires that we save the page 18 Pascal in 25 Rules or Less result of evaluating one of the subtrees before evaluating the other one. Since we want the left one in AX in order to emit an instruction, we must evaluate the right one first. That will yield the result in AX, but we musn't just leave it there while evaluating the left subtree -- AX will very likely get changed as a result. Our solution is to PUSH AX before evaluating the LEFT subtree. After that evaluation, AX will hold the left subtree. We choose to POP DX, then emit an ADD or SUB instruction between AX and DX. We therefore arrive at the following compiler coding for the ADD and SUB cases of EVAL: addop, subop: if is_simple(right) then begin eval(left); {goes to AX} code3(opcode(semt), ' AX,', nameof(right)); end else begin eval(right); code('PUSH AX'); {put in stack temporarily} eval(left); {left side to AX} code('POP DX'); {get the right value back from stack} code2(opcode(semt), ' AX,DX'); end; Some unfamiliar functions are used in this code fragment. OPCODE(SEMT) returns a string that represents the 8086 instruction for the SEMT. NAMEOF(root) returns a string that represents a valid operand for the subtree whose root is root -- it may be a literal constant, a named variable, or an offset-BP form. CODE takes one string and formats it as a symbolic assembler line with no label. A space in the string is interpreted as a tab stop, to produce a pretty formatted effect in the assembly code. CODE2 takes two strings, concatenates them and calls CODE with the result. CODE3 and CODE4 are similar. Note that although we pushed a word in the stack in the non-simple case, it gets popped out two lines later. We therefore can assert that EVAL will keep the stack orderly, provided it does so everywhere else. MPY and DIV These operations are somewhat more messy to encode in the 8086. The IMUL instruction requires one operand in the AX register, the other in another register (we will use CX). It returns a result in the pair DX-AX, with AX carrying the least significant word. Without attempting any optimizations, we therefore evaluate the right subtree, PUSH it, evaluate the left, then POP CX and emit the opcode. Division requires one additional step -- DX should be a sign extension of AX before dividing by CX. Fortunately, the instruction CWD performs this for us. Here's the resulting EVAL code fragment: mpyop, divop: begin eval(right); {divisor to AX} page 19 Pascal in 25 Rules or Less code('PUSH AX'); eval(left); {dividend to AX} if semt=divop then code('CWD'); {sign extend into DX} code('POP CX'); code2(opcode(semt), ' CX'); end; Assignment The assignment operation calls for a certain adjustment, depending on whether the right subtree is a literal fixed-point number or not. Here's the EVAL fragment: assignop: begin if right^.semt=fixed then {an immediate on the right is OK} code4('MOVW ', nameof(left), ',', nameof(right)) else begin eval(right); {goes to AX} code3('MOV ', nameof(left), ',AX'); end end; The use of MOVW is required since the left operand will be a name or an indirect BP reference (we can only assign to a variable or a function return value), while the right operand could be a byte or a word. We therefore need a word MOV in this case. In the other case, the right subtree is EVALed as usual, and the right MOV operand will be AX, stamping this as a word operation. Thus we must nurse the assembler along which otherwise wouldn't have the foggiest idea of which operation we intend. WHILE DO The WHILE-DO form is supported by a LEFT pointer and a RIGHT pointer. LEFT points to an expression subtree carrying the boolean expression (it will be tested for >0 = TRUE, and <=0 = FALSE). We have to encode this as 8086 branch instructions, and have no idea how far the branches must reach. Thus we use long branch instructions, hoping that an intelligent assembler can substitute short branches if possible. We need to manufacture a couple of temporary labels, and assign that job to a function NEW_LABEL -- this increments a global label counter, then appends its string value to the string 'XXX'. Thus we create new labels such as XXX1, XXX2, etc. as needed. The function LCODE takes two strings; the first one will become an assembler label, and the second the opcode-operand field. Here's the EVAL code fragment for a WHILE-DO: while_do: begin label1:=new_label; lcode(label1, 'EQU $'); eval(left); {boolean condition} code('CMP AX,0'); label2:=new_label; page 20 Pascal in 25 Rules or Less code2('JLE ', label2); eval(right); {statement or statement list} code2('JMP ', label1); lcode(label2, 'EQU $'); end; Note that we attach a label before evaluating the boolean condition; this will later appear in a JMP around the whole WHILE-DO form back to the boolean test. Following the boolean test is a comparison of AX to 0 (recall that EVAL yields a result in AX). We need the CMP since we aren't sure how AX got loaded, hence whether the sign flag of the 8086 was set correctly. The comparison is followed by a conditional jump to the end of the WHILE-DO form -- note how label2 reappears on an EQU $ as the last coded line. The beauty of EVAL appears between the conditional and the unconditional jump. It's quite capable of dealing with any number of statements, function and procedure calls, etc., so that a quite large and sophisticated sequence of code will appear in that innocent eval(right) call. Yet we drop in a JMP and the labelled EQU $ at just the right place. And -- the correctness of this evaluation speaks for itself. Statement List We've seen how a sequence of expressions is turned into a linked list of SEMREC nodes. We do the same thing with a sequence of statements. An EVAL fragment can be written for a STMTLIST as follows: stmtlist: while root<>nil do begin eval(root^.left); root:=root^.right; end; The ROOT is of course a value parameter passed to EVAL; its LEFT points to some statement and its RIGHT to the rest of the statement list. It's OK in Turbo Pascal to change the value of a passed value parameter, so we just do it. Once a ROOT is evaluated, we don't need it anymore, so we might as well use it to point to the next one. This could also have been coded using a recursive call on EVAL, but sequences of statements might get very lengthy, and could use up lots of stack space before they unwind. IF-THEN-ELSE Since an IF-THEN-ELSE has three parts, we need a special SEMREC clause to deal with it: if_then_else: {if B1 then S1 else S2} (B1, S1, S2: semrecp); This node of an AST is then easily coded as follows. We've discussed all the functions that appear in this EVAL code fragment: page 21 Pascal in 25 Rules or Less if_then_else: begin label1:=new_label; eval(b1); {boolean condition} code('CMP AX,0'); code2('JLE ', label1); eval(s1); {THEN statement} label2:=new_label; code2('JMP ', label2); lcode(label1, 'EQU $'); eval(s2); {ELSE statement} lcode(label2, 'EQU $'); end; Summary The following listing was generated by the Chasm assembler. It is the compiled version of program TURUN given near the beginning of this paper. This is a complete program. It fits into one segment, starting at address 100H. The stack pointer is set to location STACKORG, which is at the end of a 2000 byte block near the end of the program. (This is actually unnecessary since DOS will by default set SP to the end of a segment.) The program then begins with a call to MAIN. When MAIN returns, an INT 020H is executed, which returns control cleanly to DOS. You can step through this program with the DOS DEBUG system if you want to see what's happening in detail. Refer to the DOS manual for details. A few points about this assembled listing: A bug in our version of the Chasm assembler (which I've been assured has been repaired) made it impossible to code the RET instruction with a number; instead we've written the opcode as a DB followed by the number as a DW. You'll see this in line 124 for example. Chasm also noticed four JMP instructions that could be encoded as short jumps. As we've explained, our simple compiler doesn't keep track of the span between a JMP and its target, and that span could be any number of bytes. Thus we've taken the safe approach in our compiler and coded long jumps. An optimizing assembler could turn these into short jumps. Also, our compiler has copied the contents of a support file called STDIO.HDR (not to be confused with the C library of the same name) into the assembly code. STDIO supports the WRITE and READ functions. You can see where this file begins and ends from the comments. Are you impressed? We hope so. If you've followed our development and reasoning this far, you will have noticed that the code generation algorithms for our tiny Pascal statements seem very clear and transparent. Yet when you look at the generated assembly code, it isn't at all clear what's going on. Some of the PUSH AX instructions came from one part of the compiler algorithm and some from another part. But that's the way it is. Many software writers prefer a high-level programming language because a few very clear source statements can turn page 22 Pascal in 25 Rules or Less into a rats nest of assembly code -- but if the compiler generates that code correctly, we don't care how convoluted and hard-to-understand the resulting code is. TURUN.ASM 2/19/86 Page: 1 12:56:04 LOC OBJ LINE SOURCE CHASM version 4.00 0100 1 ; Tiny Pascal assembler code 0100 BC290B 2 MOV SP,OFFSET(STACKORG) 0103 8BEC 3 MOV BP,SP 0105 E81901 4 CALL MAIN 0108 CD20 5 INT 020H 010A 6 ; <STDIO.HDR> included 010A 7 ; STDIO.HDR 010A 8 ; 010A 9 ; READ and WRITE routines needed for Tiny Pascal 010A 10 ; 010A 11 SYS_RCHAR PROC NEAR ; Read single character from 010A B401 12 MOV AH,1 010C CD21 13 INT 021H 010E C3 14 RET ; value comes back in AL 010F 15 ENDP 010F 16 010F 17 SYS_WRCHAR PROC NEAR ; Write a single character ( 010F B402 18 MOV AH,2 0111 CD21 19 INT 021H 0113 C3 20 RET 0114 21 ENDP 0114 22 0114 23 SYS_WHEX PROC NEAR ; Write a single HEX number 0114 80FA0A 24 CMP DL,10 0117 7C07 25 JL SYS_01 0119 80C237 26 ADD DL,55 ; 'A' - 10 011C E8F0FF 27 CALL SYS_WRCHAR 011F C3 28 RET 0120 80C230 29 SYS_01 ADD DL,'0' 0123 E8E9FF 30 CALL SYS_WRCHAR 0126 C3 31 RET 0127 32 ENDP 0127 33 0127 34 SYS_IWRT PROC NEAR ; Write an integer to stdout 0127 B604 35 MOV DH,4 ; used as a counter 0129 D1C0 36 SYS_11 ROL AX 012B D1C0 37 ROL AX 012D D1C0 38 ROL AX 012F D1C0 39 ROL AX 0131 8AD0 40 MOV DL,AL 0133 80E20F 41 AND DL,0FH 0136 50 42 PUSH AX 0137 E8DAFF 43 CALL SYS_WHEX 013A 58 44 POP AX 013B FECE 45 DEC DH 013D 75EA 46 JNZ SYS_11 013F C3 47 RET 0140 48 ENDP 0140 49 page 23 Pascal in 25 Rules or Less 0140 50 SYS_SWRT PROC NEAR ; Write a string terminated 0140 8A5700 51 SYS_21 MOV DL,0[BX] 0143 80FA00 52 CMP DL,0 0146 7501 53 JNZ SYS_22 ; zero terminator? 0148 C3 54 RET 0149 E8C3FF 55 SYS_22 CALL SYS_WRCHAR 014C 43 56 INC BX 014D EBF1 57 JMPS SYS_21 014F 58 ENDP 014F 59 014F 60 SYS_WRTLN PROC NEAR ; write carriage return/lin 014F B20D 61 MOV DL,0DH 0151 E8BBFF 62 CALL SYS_WRCHAR 0154 B20A 63 MOV DL,0AH 0156 E8B6FF 64 CALL SYS_WRCHAR 0159 C3 65 RET 015A 66 ENDP 015A 67 015A 68 READ PROC NEAR ; read a HEX number fr 015A BA0000 69 MOV DX,0 ; clear DX 015D E8AAFF 70 READ_01 CALL SYS_RCHAR ; get one character in 0160 71 ; won't affect DX 0160 3C0D 72 CMP AL,0DH 0162 7506 73 JNZ READ_02 0164 52 74 PUSH DX ; save the thing we've 0165 E8E7FF 75 CALL SYS_WRTLN ; send a carriage retu 0168 58 76 POP AX ; was an ENTER 0169 C3 77 RET 016A 3C20 78 READ_02 CMP AL,' ' 016C 74EF 79 JZ READ_01 ; ignore spaces 016E 2C30 80 SUB AL,'0' ; start conversion to 0170 3C09 81 CMP AL,9 0172 7E02 82 JLE READ_03 0174 2C07 83 SUB AL,7 ; turn 'A' into 0AH 0176 3C0F 84 READ_03 CMP AL,0FH 0178 7E02 85 JLE READ_04 017A 2C20 86 SUB AL,32 ; turn 'a' into 0AH 017C 240F 87 READ_04 AND AL,0FH ; clip for good measur 017E D1E2 88 SHL DX ; prepare DX for hex v 0180 D1E2 89 SHL DX 0182 D1E2 90 SHL DX 0184 D1E2 91 SHL DX 0186 08C2 92 OR DL,AL 0188 EBD3 93 JMPS READ_01 ; go do some more 018A 94 ENDP 018A 95 018A 96 READLN PROC NEAR 018A EBCE 97 JMPS READ ; does the same thing 018C 98 ENDP 018C 99 018C 100 ; ... end of include STDIO.HDR 018C 101 ; {TURUN -- A sample program written in Tiny Pascal 018C 102 ; var I, J, K, PROBLEM; 018C 103 ; 018C 104 ; {*********************} 018C 105 ; function ISLESS(N1, N2); 018C 106 ; begin {returns 1 if n1<n2, 0 otherwise} 018C 107 ; if n2-n1 then isless:=1 {truth value test is page 24 Pascal in 25 Rules or Less 018C 108 ; else isless:=0; 018C 109 ; end; 018C 110 ISLESS PROC NEAR 018C 55 111 PUSH BP 018D 8BEC 112 MOV BP,SP 018F 8B4604 113 MOV AX,4[BP] ; N2 0192 2B4606 114 SUB AX,6[BP] ; N1 0195 3D0000 115 CMP AX,0 0198 7E08 116 JLE XXX0 019A C746080100 117 MOVW 8[BP],1 ; ISLESS **** Diagnostic: Could use JMPS 019F E90500 118 JMP XXX1 01A2 119 XXX0 EQU $ 01A2 C746080000 120 MOVW 8[BP],0 ; ISLESS 01A7 121 XXX1 EQU $ 01A7 8B4608 122 MOV AX,8[BP] ; ISLESS 01AA 5D 123 POP BP 01AB C2 124 DB 0C2H 01AC 0600 125 DW 6 01AE 126 ENDP 01AE 127 ; SYMBOL TABLE 01AE 128 ; ISLESS 8[BP] 01AE 129 ; N1 6[BP] 01AE 130 ; N2 4[BP] 01AE 131 01AE 132 ; 01AE 133 ; function ADDEMUP(LOWER, UPPER, SUM); 01AE 134 ; begin end; {makes it a forward declaration} 01AE 135 ; 01AE 136 ; {*********************} 01AE 137 ; function ISEQUAL(N1, N2); 01AE 138 ; begin 01AE 139 ; if n2-n1 then isequal:=0 {false} 01AE 140 ; else 01AE 141 ; if n1-n2 then isequal:=0 01AE 142 ; else isequal:=1; 01AE 143 ; end; 01AE 144 ISEQUAL PROC NEAR 01AE 55 145 PUSH BP 01AF 8BEC 146 MOV BP,SP 01B1 8B4604 147 MOV AX,4[BP] ; N2 01B4 2B4606 148 SUB AX,6[BP] ; N1 01B7 3D0000 149 CMP AX,0 01BA 7E08 150 JLE XXX2 01BC C746080000 151 MOVW 8[BP],0 ; ISEQUAL **** Diagnostic: Could use JMPS 01C1 E91800 152 JMP XXX3 01C4 153 XXX2 EQU $ 01C4 8B4606 154 MOV AX,6[BP] ; N1 01C7 2B4604 155 SUB AX,4[BP] ; N2 01CA 3D0000 156 CMP AX,0 01CD 7E08 157 JLE XXX4 01CF C746080000 158 MOVW 8[BP],0 ; ISEQUAL **** Diagnostic: Could use JMPS 01D4 E90500 159 JMP XXX5 01D7 160 XXX4 EQU $ 01D7 C746080100 161 MOVW 8[BP],1 ; ISEQUAL 01DC 162 XXX5 EQU $ page 25 Pascal in 25 Rules or Less 01DC 163 XXX3 EQU $ 01DC 8B4608 164 MOV AX,8[BP] ; ISEQUAL 01DF 5D 165 POP BP 01E0 C2 166 DB 0C2H 01E1 0600 167 DW 6 01E3 168 ENDP 01E3 169 ; SYMBOL TABLE 01E3 170 ; ISEQUAL 8[BP] 01E3 171 ; N1 6[BP] 01E3 172 ; N2 4[BP] 01E3 173 01E3 174 ; 01E3 175 ; {***********************} 01E3 176 ; function ADDEMUP(LOWER, UPPER, SUM); 01E3 177 ; {SUM is a local} 01E3 178 ; begin 01E3 179 ; sum:=0; 01E3 180 ; while isless(lower, upper) do begin 01E3 181 ; sum:=sum+lower; 01E3 182 ; lower:=lower+1; 01E3 183 ; end; 01E3 184 ; addemup:=sum+lower; { the last one was left ou 01E3 185 ; end; 01E3 186 ADDEMUP PROC NEAR 01E3 55 187 PUSH BP 01E4 8BEC 188 MOV BP,SP 01E6 C746040000 189 MOVW 4[BP],0 ; SUM 01EB 190 XXX6 EQU $ 01EB 50 191 PUSH AX 01EC 8B4608 192 MOV AX,8[BP] ; LOWER 01EF 50 193 PUSH AX 01F0 8B4606 194 MOV AX,6[BP] ; UPPER 01F3 50 195 PUSH AX 01F4 E895FF 196 CALL ISLESS 01F7 3D0000 197 CMP AX,0 01FA 7E15 198 JLE XXX7 01FC 8B4604 199 MOV AX,4[BP] ; SUM 01FF 034608 200 ADD AX,8[BP] ; LOWER 0202 894604 201 MOV 4[BP],AX ; SUM 0205 8B4608 202 MOV AX,8[BP] ; LOWER 0208 050100 203 ADD AX,1 020B 894608 204 MOV 8[BP],AX ; LOWER **** Diagnostic: Could use JMPS 020E E9DAFF 205 JMP XXX6 0211 206 XXX7 EQU $ 0211 8B4604 207 MOV AX,4[BP] ; SUM 0214 034608 208 ADD AX,8[BP] ; LOWER 0217 89460A 209 MOV 10[BP],AX ; ADDEMUP 021A 8B460A 210 MOV AX,10[BP] ; ADDEMUP 021D 5D 211 POP BP 021E C2 212 DB 0C2H 021F 0800 213 DW 8 0221 214 ENDP 0221 215 ; SYMBOL TABLE 0221 216 ; ADDEMUP 10[BP] 0221 217 ; LOWER 8[BP] 0221 218 ; UPPER 6[BP] 0221 219 ; SUM 4[BP] page 26 Pascal in 25 Rules or Less 0221 220 0221 221 ; 0221 222 ; {*********************} 0221 223 ; function MAIN(SUM, UPPER); 0221 224 ; begin 0221 225 ; i:=1; 0221 226 ; j:=i+5; 0221 227 ; k:=j-16; 0221 228 ; problem:=i+(j*k); 0221 229 ; writeln('I: ', i, ' J: ', j, ' K: ', k, ' Probl 0221 230 ; write('Enter upper '); 0221 231 ; upper:=read; 0221 232 ; sum:=addemup(1, upper); {sum of integers 1..up 0221 233 ; if isequal(sum, (upper*(upper+1))/2) then 0221 234 ; writeln('Sum = ', sum) 0221 235 ; else begin 0221 236 ; writeln('BUG: Sum = ', sum, '; should be ', 0221 237 ; (upper*(upper+1))/2); 0221 238 ; end; 0221 239 ; end; 0221 240 MAIN PROC NEAR 0221 55 241 PUSH BP 0222 8BEC 242 MOV BP,SP 0224 C70653030100 243 MOVW I,1 ; I 022A A15303 244 MOV AX,I ; I 022D 050500 245 ADD AX,5 0230 A35503 246 MOV J,AX ; J 0233 A15503 247 MOV AX,J ; J 0236 2D1000 248 SUB AX,16 0239 A35703 249 MOV K,AX ; K 023C A15703 250 MOV AX,K ; K 023F 50 251 PUSH AX 0240 A15503 252 MOV AX,J ; J 0243 59 253 POP CX 0244 F7E9 254 IMULW CX 0246 50 255 PUSH AX 0247 A15303 256 MOV AX,I ; I 024A 5A 257 POP DX 024B 01D0 258 ADD AX,DX 024D A35103 259 MOV PROBLEM,AX ; PROBLEM 0250 BB4D03 260 MOV BX,OFFSET(SS0) 0253 E8EAFE 261 CALL SYS_SWRT 0256 A15303 262 MOV AX,I ; I 0259 E8CBFE 263 CALL SYS_IWRT 025C BB4803 264 MOV BX,OFFSET(SS1) 025F E8DEFE 265 CALL SYS_SWRT 0262 A15503 266 MOV AX,J ; J 0265 E8BFFE 267 CALL SYS_IWRT 0268 BB4303 268 MOV BX,OFFSET(SS2) 026B E8D2FE 269 CALL SYS_SWRT 026E A15703 270 MOV AX,K ; K 0271 E8B3FE 271 CALL SYS_IWRT 0274 BB3803 272 MOV BX,OFFSET(SS3) 0277 E8C6FE 273 CALL SYS_SWRT 027A A15103 274 MOV AX,PROBLEM ; PROBLEM 027D E8A7FE 275 CALL SYS_IWRT 0280 E8CCFE 276 CALL SYS_WRTLN 0283 BB2B03 277 MOV BX,OFFSET(SS4) page 27 Pascal in 25 Rules or Less 0286 E8B7FE 278 CALL SYS_SWRT 0289 E8CEFE 279 CALL READ 028C 894604 280 MOV 4[BP],AX ; UPPER 028F 50 281 PUSH AX 0290 B80100 282 MOV AX,1 0293 50 283 PUSH AX 0294 8B4604 284 MOV AX,4[BP] ; UPPER 0297 50 285 PUSH AX 0298 B80000 286 MOV AX,0 029B 50 287 PUSH AX 029C E844FF 288 CALL ADDEMUP 029F 894606 289 MOV 6[BP],AX ; SUM 02A2 50 290 PUSH AX 02A3 8B4606 291 MOV AX,6[BP] ; SUM 02A6 50 292 PUSH AX 02A7 B80200 293 MOV AX,2 02AA 50 294 PUSH AX 02AB 8B4604 295 MOV AX,4[BP] ; UPPER 02AE 050100 296 ADD AX,1 02B1 50 297 PUSH AX 02B2 8B4604 298 MOV AX,4[BP] ; UPPER 02B5 59 299 POP CX 02B6 F7E9 300 IMULW CX 02B8 99 301 CWD 02B9 59 302 POP CX 02BA F7F9 303 IDIVW CX 02BC 50 304 PUSH AX 02BD E8EEFE 305 CALL ISEQUAL 02C0 3D0000 306 CMP AX,0 02C3 7E12 307 JLE XXX8 02C5 BB2403 308 MOV BX,OFFSET(SS5) 02C8 E875FE 309 CALL SYS_SWRT 02CB 8B4606 310 MOV AX,6[BP] ; SUM 02CE E856FE 311 CALL SYS_IWRT 02D1 E87BFE 312 CALL SYS_WRTLN **** Diagnostic: Could use JMPS 02D4 E92D00 313 JMP XXX9 02D7 314 XXX8 EQU $ 02D7 BB1803 315 MOV BX,OFFSET(SS6) 02DA E863FE 316 CALL SYS_SWRT 02DD 8B4606 317 MOV AX,6[BP] ; SUM 02E0 E844FE 318 CALL SYS_IWRT 02E3 BB0B03 319 MOV BX,OFFSET(SS7) 02E6 E857FE 320 CALL SYS_SWRT 02E9 B80200 321 MOV AX,2 02EC 50 322 PUSH AX 02ED 8B4604 323 MOV AX,4[BP] ; UPPER 02F0 050100 324 ADD AX,1 02F3 50 325 PUSH AX 02F4 8B4604 326 MOV AX,4[BP] ; UPPER 02F7 59 327 POP CX 02F8 F7E9 328 IMULW CX 02FA 99 329 CWD 02FB 59 330 POP CX 02FC F7F9 331 IDIVW CX 02FE E826FE 332 CALL SYS_IWRT 0301 E84BFE 333 CALL SYS_WRTLN 0304 334 XXX9 EQU $ page 28 Pascal in 25 Rules or Less 0304 8B4608 335 MOV AX,8[BP] ; MAIN 0307 5D 336 POP BP 0308 C2 337 DB 0C2H 0309 0600 338 DW 6 030B 3B2073686F75 339 SS7 DB '; should be ',0 6C6420626520 00 0318 4255473A2053 340 SS6 DB 'BUG: Sum = ',0 756D203D2000 0324 53756D203D20 341 SS5 DB 'Sum = ',0 00 032B 456E74657220 342 SS4 DB 'Enter upper ',0 757070657220 00 0338 2050726F626C 343 SS3 DB ' Problem: ',0 656D3A2000 0343 204B3A2000 344 SS2 DB ' K: ',0 0348 204A3A2000 345 SS1 DB ' J: ',0 034D 493A2000 346 SS0 DB 'I: ',0 0351 347 ENDP 0351 348 ; SYMBOL TABLE 0351 349 ; MAIN 8[BP] 0351 350 ; SUM 6[BP] 0351 351 ; UPPER 4[BP] 0351 352 0351 353 ; 0351 354 ; GLOBAL VARIABLES 0351 0000 355 PROBLEM DW 0 0353 0000 356 I DW 0 0355 0000 357 J DW 0 0357 0000 358 K DW 0 0359 359 ; RUNTIME STACK 0359 360 DS 2000 0B29 0000 361 STACKORG DW 0 0B2B 362 ; MAIN stack space 0B2B 0000 363 DW 0 0B2D 0000 364 DW 0 0B2F 0000 365 DW 0 0B31 366 ; NO errors 0 Error(s) detected 5 Diagnostic(s) offered 817 (331H) Bytes of object code generated Symbol Table Dump: ADDEMUP.........P01E3 I...............M0353 ISEQUAL.........P01AE ISLESS..........P018C J...............M0355 K...............M0357 MAIN............P0221 PROBLEM.........M0351 READ............P015A READLN..........P018A READ_01.........P015D READ_02.........P016A READ_03.........P0176 READ_04.........P017C SS0.............M034D SS1.............M0348 SS2.............M0343 SS3.............M0338 SS4.............M032B SS5.............M0324 SS6.............M0318 SS7.............M030B STACKORG........M0B29 SYS_01..........P0120 SYS_11..........P0129 SYS_21..........P0140 SYS_22..........P0149 page 29 Pascal in 25 Rules or Less SYS_IWRT........P0127 SYS_RCHAR.......P010A SYS_SWRT........P0140 SYS_WHEX........P0114 SYS_WRCHAR......P010F SYS_WRTLN.......P014F XXX0............P01A2 XXX1............P01A7 XXX2............P01C4 XXX3............P01DC XXX4............P01D7 XXX5............P01DC XXX6............P01EB XXX7............P0211 XXX8............P02D7 XXX9............P0304 Where to Obtain Software We invite you to try writing your own compiler, or at least to try the tools and source code we used in writing this one. Here's what you need -- you'll find the cost very reasonable: The Qparser demo system. Order from QCAD Systems, 1164 Hyde Ave, San Jose, CA 95129, phone 800/538-9787 (408/727-6671 in CA). Price is $10 plus $2 shipping and handling. CA residents add sales tax. Check, money order, or bank card accepted. This comes with a booklet that carries you through a simple pocket calculator example, but contains the all-important parser generator needed for our tiny Pascal compiler. If you want to go beyond 25 productions, the unlimited Qparser system will cost you $400. Source for the tiny Pascal compiler. Order from QCAD Systems, same address and phones as above. Ask for the "tiny Pascal disc": $10 plus $2 shipping and handling, plus sales tax, etc. The Chasm assembler. You can purchase an abridged version of this assembler (but powerful enough to support tiny Pascal) from PC Software Interest Group, 1030 E. Duane, suite D, Sunnyvale, CA 94086. Call 408/730-9291 for membership and ordering information. Ask for disk number 10. A membership in PC-SIG is $20 for one year, and entitles you to any number of software discs at $6 each from their catalog of over 540 discs. You can also order a full Chasm assembler for $40 directly from the author, David Whitman, 136 Wellington Terrace, Lansdale, PA, 19446, phones 215/641-7114 (day), 215/362-8526 (evenings). Tiny Pascal was written to be compatible with Chasm, but it can easily be adapted to other assembler conventions. The Qparser demo system disc can also be ordered from PC-SIG for $6 -- ask for disk number 419. (This version has the booklet information on the disc as a README file.) References [1] Compiler Construction--Theory and Practice, Barrett, Bates, Gustafson and Couch, Science Research Associates, Chicago, second edition. This is a companion textbook to the Qparser system. This and reference [2] develop the theory of grammars, parsers, translation, symbol table management and much more. [2] Principles of Compiler Design, Aho and Ullman, page 30 Pascal in 25 Rules or Less Addison-Wesley. [3] 8086 Family User's Manual, Intel Corp, 9800722-03. Order from the Literature Dept, Intel Corp, 3065 Bowers Ave, Santa Clara, CA, 95051. A definitive volume on the 8086 architecture, development systems, software and related semiconductor products. page 31