UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN JJUefi) uiucdcs-R-7^-658 y)uuti A BASIC LANGUAGE INTERPRETER FOR THE INTEL 8008 MICROPROCESSOR by 9 June, 197^ Alfred C. Weaver Michael H. Tindall Ronald L. Danielson Uf - ^ 1974 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLIN< UIUCDCS-R-7i+-658 A BASIC LANGUAGE INTERPRETER FOR THE INTEL 8008 MICROPROCESSOR by Alfred C. Weaver Michael H. Tindall Ronald L. Danielson June, 197^ Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois Ill ACKNOWLEDGEMENT The authors wish to express their appreciation to Professor James Vander Mey, who originally suggested and subsequently supervised the entire project; to Professor Thomas Wilcox, who consulted on the design of the software techniques; to Gordon Peterson, who wrote an assem- bler for a version of the Intel assembly language; and to Guy Riddle, who wrote an Intel 8008 simulator for the IBM 360/75. Digitized by the Internet Archive in 2013 http://archive.org/details/basiclanguageint658weav IV TABLE OF CONTENTS page 1. INTRODUCTION 1 2 . OPERATING SYSTEM k 2.1 Text Editing k 2 . 2 Syntax Checking 6 2.3 Run-time Monitoring 7 2 . k Error Handling 7 2 . 5 Immediately Executable Statements . „ 8 2.6 Input/ Output 8 3 . SYNTACTIC AND SEMANTIC ANALYSIS 10 3.1 Syntactic Analysis 10 3.2 Semantic Analysis 13 k. LEXICAL ANALYZER AND SYMBOL TABLE 15 k.l Lexical Analyzer 15 k.2 Symbol Table Manager 17 1+.3 Symbol Table Structure 18 5 . EXECUTION PACKAGE 20 6. SUMMARY o 21 APPENDIX A. BASIC LANGUAGE BNF 22 B. DESCRIPTION OF THE STATE TRANSITIONS FOR THE SYNTACTIC RECOGNIZER 2k C. STATE DIAGRAMS FOR BASIC LANGUAGE TABLE-DRIVEN INTERPRETER.. 31 D. PROGRAM EXAMPLE 37 1. INTRODUCTION This report concerns the design and implementation of a BASIC language interpreter which is restricted to the environment of the Intel 8008 microprocessor. The value of the project was in overcoming the severe restrictions imposed by an 8-bit machine with only four general purpose registers, one accumulator, and two registers used simultaneously to form one core address. Furthermore, the machine's numerical capability is characterized by its two arithmetic instructions : 8-bit add and subtract. All addresses (ik bits) must be broken into high and low order bytes and stored in the H and L registers, respectively, for any memory reference. With a cycle time of 20 microseconds average, the machine is no number -crunching giant, but is more than adequate for the dedicated processor we envisioned. This project is the direct result of a seminar course on mini- computers taught at the University of Illinois by Professor James Vander Mey. While the project itself was executed entirely on an Intel simulator, we feel that the techniques developed are directly applicable to the hardware described. The hardware environment envisioned for this project included: a microprocessor with a l6Kx 8-bit word memory (Intel MCS-8), an ASCII keyboard, a black-and-white television for the display, and a custom- designed hardware interface which continuously displays the contents of a 2K buffer in Intel memory. Design and implementation of the interface was wholly controlled by another group. The language which has been implemented is a version of BASIC which incorporates all of the most common features of the language and a few versatile extensions. A conscious effort was made to "design with forethought" so that future modifications, either by the authors or others, would not require extensive modification of the existing routines. The BASIC language statements currently implemented include: LET, DIM, DEF, REM, GOTO, IF, FOR, TO, NEXT, GOSTJB, RETURN, INPUT, PRINT, STEP, THEN, STOP, and END. The operators provided are addition, subtraction, multi- plication, division, exponentiation, and the Boolean operators AND, OR, NOT, LESS-THAN, LESS-THAN-OR-EQUAL, GREATER-THAN, GREATER -THAN-OR- EQUAL, EQUAL, and NOT-EQUAL. The extensions to the language include: up to 26 3-dimensional arrays, up to 26 user-defined functions, user functions with nested (but not recursive) definitions 5 levels deep, six built-in functions (sine, cosine, arctangent, exponential, logarithm, and square root), full floating point arithmetic performed with 5 byte operands (h byte mantissa, 1 byte exponent) with results rounded to h bytes (3 byte mantissa and 1 byte exponent), character strings in the PRINT statement, and FOR-loops nested up to 5 levels deep. The BNF for the BASIC language implemented is supplied in Appendix A. The use of specially encoded keyboard keys for all multi- character keywords (LET, DIM, ..., END, relational operators, and user functions FNx) allows our grammer to be LL(l), thus simplifying the parsing technique. The project broke neatly into two phases - design and development ■ and the development phase itself was split into three basic areas: (l) the operating system, including master control of the CPU, mode switching, context switching, polling routine for the keyboard, complete text editing system, screen display management, user source text memory management, and user "output page" memory management; (2) the syntactic/semantic analyzer, including BASIC syntax recognizer, error detection/location routines, lexical analyzer, and symbol table manager; (3) the execution routines , including specific utility routines needed by the syntax analyzer (stack control and lexical pointer movement), a floating point arithmetic package (add, subtract, multiply, divide, fix, float, compare, load, store, and error branching), a transcendental function evaluator (sine, cosine, log, exponential, arctangent, and square root), and a two-way floating -point-to-character- string and character-string-to-floating -point conversion package. The following sections and appendices present an explicit report of the design philosophy and characteristics of the three major areas. h 2. OPERATING SYSTEM The operating system is charged with the responsibility of managing the CPU. As a dedicated processor, the CPU exists only to serve the user, but it does so in one of six possible environments. 2.1 Text Editing In pure text editing mode the keyboard is used to build text on a display screen using the elementary operations of insert character, delete character, replace character, delete line, scroll up 1 or 8 lines, and scroll down 1 or 8 lines. No syntax checking of any kind is performed in this mode. To aid the user, a moveable cursor (@) is positioned immediately to the left of the character or line to be inserted, replaced, or deleted. Thus the programmer has constant and precise control over the location of any of his changes. The cursor is moved by depressing one of its special control keys : -> (right arrow) move right one character; AB@CD becomes AB0@D (left arrow) move left one character; AB@CD becomes A@BCD t (up arrow) move cursor to the beginning of the current line or, if it is already at the beginning of a line, to the beginning of the previous line; ABCD becomes ABCD EP@G @EFG and ABCD becomes @ABCD @EFG EFG I (down arrow) move cursor to the beginning of the next line; AB@CD becomes ABCD EFGH @EFGH The user's memory space, at addresses lkK through l6K-l} is bounded by non -ins er table markers at the beginning of the user's source text (static), end of source text (dynamic), and end of user's data page (dynamic). The display is initialized as follows: [~/gi iiiiiiiitiiiiiiirfiiiititttiiiiit*] where [ represents the beginning -of -text marker (source page and output page), @ represents the cursor, I represents the end-of-line marker, and ] represents the end-of -memory marker. The text editor functions are accomplished by manipulating a line of text or the entire program as necessary. A replace character requires no text movement, but an insert or delete character requires that all of the text from the cursor to the end-of -memory marker be shifted one byte in core. Insertion is typical of the operations performed, and some operation counts show that if an insertion is to occur n characters to the left of the end-of -memory marker then the elapsed time t from picking up the character in the polling loop until the CPU returns to the polling loop is : 20 microseconds/instruction * (50 + 20n) instructions For example: n t 10 0.5 milliseconds 100 kl milliseconds 1000 0.^4- seconds Assuming an average keyboard rate of 3 characters/second, a burst rate of 10 characters/second, and an average text movement of less than 100 characters, we found that the machine "will adequately keep up with the user by using only a single one- byte hardware buffer. Additional command codes were reserved (but not implemented) for such handy functions as FILE-SCREEN-TO-TAPE, MOVE-TAPE-TO-SCREEN, SORT-SCREEN-BY-SEQUENCE-NUMBERS , etc . Appendix D documents the operating system/ text editor. Each screen display shows the state of the screen just prior to the receipt of the next character from the keyboard. 2.2 Syntax Checking When operating in the "BASIC" mode, the operating system provides line-by-line syntax checking of the. text being inserted on the screen, in addition to providing all of the text editing features described in section 2.1 above. Every time the cursor moves right over an end-of - line marker (in response to a right arrow, down arrow, or insertion of an end-of -line character), the syntax analyzer is called to parse the line just created. Whenever the cursor moves left over an end-of -line, the syntax analyzer (SYNA) is called to "unparse" the line just entered. This feature allows the user to interactively construct a syntactically correct BASIC program. Special command keys are provided to allow the user to change from "BASIC" mode to "TEXT" mode, and vice -versa. 2.3 Run -time Monitoring When a RUN command is detected by the operating system (OS) command decoder, OS enters the third of its major roles, that of an execution monitor. In response to the RIM command, OS initializes all of the interpreter variables (primarily the symbol table and the parsing stacks), sets the lexical (LEXl) pointer to the first executable state- ment, removes the cursor from the program text, switches the screen display base address to point to the data page, and begins calling SYNA on a line-by-line basis. After each return from SYNA the keyboard strobe (an "in use" bit) is checked and any character on the data bus is read. The only character recognized while executing is a STOP IMMEDIATE command, which causes OS to jump to the immediately executable statement routines described below. Other characters are ignored until execution is term- inated, either normally (by execution of a STOP statement) or as the result of an error. Normal termination leaves OS in the "BASIC" (syntax checking) mode. Commands are provided for jumping from data page to program page and back again. Detection of an error causes SYNA to jump to an OS routine for error handling. 2.k Error Handling When the error routine is entered the screen base pointer is shifted back to the program page, a message describing the error is inserted on a line following the one in which the error was detected, 8 and the cursor is inserted in the program at the spot nearest the error. This enables the user to quickly locate his error. The operating system then jumps to the text editing/syntax checking routines in anticipation of error correction attempts by the user. 2.5 Immediately Executable Statements Immediately executable statements are handled as described under "run-time monitoring". The user may stop a running program by pressing the STOP IMMEDIATE key, thus causing the program to halt at the end of the currently executing line. The operating system then allows code to be entered line-by-line in the "immediately executable" mode. Each line must be followed by the EXECUTE IMMEDIATE command key, which causes the line just constructed to be parsed and immediately executed. The user may jump back and forth between the program and data pages, but may not modify the program unless he leaves the immediately executable mode. A RESTART command is provided which causes the user program to begin execution at the point where it was interrupted (unless one of the immediately executed statements caused a branch, in which case execution begins at the branch address). The user may operate the system as a desk calculator by initially jumping to the data page and inserting unnumbered BASIC statements, each followed by the EXECUTE IMMEDIATE command. 2 . 6 Input/Output The operating system provides input-output facilities which may be used by SYNA. when in the execute or execute immediate mode. All input requests and output text are displayed on the data page. The conversion routines in the floating point arithmetic package are used to provide the ASCII-to-binary and binary-to-ASCII conversions. Input requests may be made to provide data for a scalar variable or an array element. Array subscripts are taken from SYNA's expression stack. A typical such input request might be: INPUT X(2,5) > @ The input data is inserted to the right of the great er-than sign, and is converted to internal floating point by the appropriate conversion routine. There are three separate output routines: one which causes the data page display to skip to a new line , one which outputs numbers , and one which outputs character strings. The character string routine requires the H and L registers to point to the beginning of the string and leaves the LEXI pointer to the right of the terminal quote. The numeric routine displays a number pointed to by the top of SYNA's address stack. Commands are ignored during this I/O activity. The output routine for numbers will print them in its choice of FORTRAN I, F, or E format, depending upon the magnitude and precision of the particular number being output. The input routine accepts the input string in any format. All of the above routines are written as pure procedures, and in a modular fashion. There is a reasonable amount of optimization possible in the OS routines, particularly in the n-way branches. Total size of the text editor/ operating system is about 3000 bytes. 10 3. SYNTACTIC AND SEMANTIC ANALYSIS 3.1 Syntactic Analysis SYNA is the heart of the BASIC language capabilities of our system. It performs both syntactic correctness checking and interpretive BASIC language program execution. SYNA is called on a statement-by- statement basis from the operating system; when a statement has been correctly parsed or executed, a normal return is made to OS; if an error is detected, control passes to an error recovery procedure in OS where appropriate recovery measures are taken (these are documented elsewhere). The syntax analyzer is essentially a stack oriented pushdown automaton. As a statement is parsed, the analyzer makes a sequence of state transitions that depend on the current input symbol (token) in the statement. Entering certain states causes the syntax analyzer to accept the statement, and likewise, other combinations of the analyzer's state and input token cause the analyzer to reject the statement and signal an error. In an effort to conserve space, the state transitions are encoded in table form, making the syntax analyzer table-driven. A fairly small table driver routine causes new tokens to be input when required by a lexical analysis routine, moves the analyzer through the state table, manipulates the analyzer's stack, and invokes a set of execution routines that perform the actual operations defined in the BASIC language. For a more detailed explanation of the state transitions and a view of the 11 syntax table, see appendices B and C. In addition to the analyzer's parser stack, a number of other stacks are maintained by SYHA.. These include an address stack, an expression value stack and corresponding operator stack used for expres- sion evaluation, a FOR-loop stack and a user function evaluation stack. The parser stack is used strictly for state transitions by the pushdown automaton. The address stack (2 bytes wide) is used for executing GOTO and GOSUB statements, for array reference resolution, and for any general bookkeeping operation requiring two bytes of stack storage. The expres- sion stack (k bytes wide) is used to store temporary arithmetic components and results involved in expression evaluation. The operator stack (2 bytes wide) uses one byte to identify the arithmetic operator involved and the other byte to hold the operator's F precedence (see D. Gries , Compiler Construction for Digital Computers , chapter 5, "Simple Precedence Grammers"). The stack is used in conjunction with the expression stack in evaluating expressions. The FOR-loop stack is used to keep track of FOR-loop nesting in the program. Each time a new FOR-loop is entered, an entry is pushed onto the FOR-loop stack. When the loop is exited, the stack is popped one level. The last stack is a user function stack (3 bytes wide). One byte points to the symbol table location of the function, and the other two bytes hold the return address for use after the function has been evaluated. The function stack is needed since one function may be defined in terms of another function. Under the current implementation (easily modifiable) the function stack is 5 deep, the FOR-loop stack is k deep, the expression and oper- ator stacks are each 10 deep, and the parser stack is 15 deep. The syntax analyzer operates in one of three modes, determined 12 by the operating system. When the programmer pushes the RUN key, all variables (both compiler and program) are initialized to zero and then SYNA is called statement -by-statement throughout the program; SYNA. again performs a syntax check on each statement and then executes the statement. This is the EXECUTE mode, in which all stacks are fully operational and utilized. As explained in the operating system chapter, the programmer can type in his program in an interactive BASIC environment, giving him a syntax check on his statement as it is entered, but not actually exe- cuting the statement. This is the normal PARSE mode. The FOR-loop stack, parser stack, and address stack are operational in this mode. The expression stack, operator stack, and function evaluation stacks are not used since the statement is not actually executed. One primary goal for the project was to provide good syntax checking and error detection in this normal PARSE mode. To do this, FOR-loop nesting should be checked even though the loop is not actually being executed (indeed, at the time the analyzer is parsing the FOR statement, the loop contents and the NEXT statement probably do not even exist.). Thus, SYNA builds the FOR-loop stack at parse time, enabling the check on loop nesting. Also, we require array and function definition before use so that we can insure that all uses of the same variable are consistent. To handle this, SYNA sets a flag bit in the symbol table when an array is defined by a DIM statement, and likewise when a function is defined by a DEF statement. Now all uses of the array or function name can be checked for syntactic correctness and previous definition. The only complication which arises in the above scheme of syntax checking occurs when the programmer backs up the cursor and changes, 13 inserts, or deletes statements which have already been parsed. To adequately handle these occurances, the syntax parser actually needs to back up with the cursor and undo any FOR-loop nest checking or array/ function definitions. For this purpose, the operating system will call S"YNA in the UNPARSE mode whenever the cursor is backed up over an end- of-line. For example, if a NEXT statement is backed over, the FOR-loop stack will be pushed up one level to indicate that we are back inside a FOR-loop again. If a DIM statement is backed over, all the arrays dimensioned within that statement will have their "defined" bit turned off (i.e., "not defined") in the symbol table. Eventually, the programmer will move the cursor forward again using the right arrow or down arrow keys ; when this happens SYNA is called again in the regular PARSE mode, the statement is parsed again, and the normal parsing actions are taken. 3.2 Semantic Analysis It is apparent that, depending upon the mode when SYNA is called, different operations are performed when a statement is parsed. As far as the formal parser is concerned, it means that any given state can have different semantic routines associated with it, depending upon the mode. Thus, each state entry in the table has three bits, one for each of the EXECUTE, PARSE, and UNPARSE modes, as well as an execution/semantic rou- tine number. When a state is used in the table the execution/semantic routine is invoked only if the bit corresponding to the current mode is set. For example, the expression evaluation routine is an execution- only routine, having its EXECUTE bit set and its PARSE and UNPARSE bits not set in the SYNA table; thus this routine is called only if the mode is EXECUTE. Ik This concludes the discussion of the syntatic/semantic analyzer, The lexical analyzer and symbol table manager are discussed separately. 15 h. LEXICAL ANALYZER AND SYMBOL TABLE k.l Lexical Analyzer The lexical analyzer is a duty routine for the syntactic recog- nizer. The lexical pointer LPTR contains in two contiguous bytes the page number (high order 6 bits specif ing which 256-byte page) and byte number (low order 8 bits) of the ik bit addresses within the user area, lk-K. through 16K-I. On entry to LEXI, LPTR points one byte beyond the most recently scanned token (initially SYNA points it to l^K+1, the first byte of user source text). LEXI isolates the next non-blank (possibly the current) character, sets SEM (semantic class variable) to the ASCII code of the character being examined if it is not an identifier or sets SEM to the variable's displacement in the symbol table if it is an identifier, and performs a pseudo binary search to identify the currently scanned symbol as one of 15 token classes. The token class is recorded in SYMB. If the token is an operator, LEXI records its F and G precedence (see Gries) in the variables F and G. The token classes are: TOKEN ASCII SYMB SEM F G LET DIM DEF REM GOTO IF FOR ASCII SYMB SEM 129 15 129 130 15 130 131 15 131 132 15 132 133 15 133 13^ 15 13^ 135 15 135 16 TOKEN ASCII SYMB SEM F G TO 136 15 136 NEXT 138 15 138 GOSUB 139 15 139 RETURN 11+0 15 11+0 INPUT ll+l 15 11+1 PRINT ikz 15 11+2 STOP 1^3 15 11+3 END Ikk 15 11+1+ STEP ll+5 15 1^5 THEN lk6 15 ll+6 NOT ll+7 3 ll+7 12 13 AND ll+8 k ll+8 '5 1+ OR ll+9 k ll+9 3 2 FN 15k 7 stp SIN 155 6 155 7 6 ATN 156 6 156 7 6 COS 157 6 157 7 6 EXP 158 6 158 7 6 LOG 159 6 159 7 6 SQR 160 6 160 7 6 < 161 5 161 12 13 <= 162 5 l62 12 13 > 163 5 163 12 13 >= 161+ 5 16k 12 13 = 165 5 165 12 13 # 166 5 • 166 12 13 + 1*3 1 1+3 9 8 - 1+5 1 1+5 9 8 ■* k2 2 1+2 11 10 / kl 2 1*7 11 10 t 9h 2 9k 11 10 17 TOKEN ASCII ( 4o ) kl tt 34 5 44 end-of-line 92 A 65 B 66 SYMB 8 9 10 10 10 11 11 SEM 4o kl 34 44 92 stp stp 0 0 G Ik 0 90 65 ko 66 4o 90 4o 11 12 12 12 U8 14 k9 14 57 14 16 stp stp stp stp stp = symbol table pointer A( B( • o Z( 0 1 others (unknown) 4.2 Symbol Table Manager If a token is an identifier, a simple one character lookahead resolves the question of whether the identifier is an array or a simple scalar; likewise, after receiving the special FN key, the next character determines which function (FNA, FNB, ..., FNZ) is being referenced. If an identifier is referenced, LEXI calls the symbol table manager (LOOKUP) which, in turn, finds or inserts that identifier in the symbol table and returns the identifier's location as a displacement from the beginning of the symbol table; the displacement is returned in the variable SEM. 18 The symbol table search is based on a linear hash generated by AOT)ing the symbol's ASCII code with 31 (=00011111p) and multiplying the result by 8 (three left shifts). The 26 alphabetic characters now hash uniquely to locations 8, l6, 2k, . .., 208. Then a linear search is begun at the hash address HASH = 8 * mod (ASCII, 32 ) , checking each entry for one of three possibilities: (l) an empty entry (flag byte pointed to by HASH is zero), indicating that the desired entry is presently not in the table and causing insertion; (2) the variable name in the symbol table matches the recognized name in the B,C registers (SEM then returns the offset from STABH, the base address of the symbol table); or (3) the search fails 32 times and then signals an error - "symbol table full". k.3 Symbol Table Structure The structure of the symbol table is : flags first char second char binary value of floating point variables where The flag byte is subdivided into its bit fields as V6b5V3b2blbO b„ =0 entry empty = 1 entry in use b = 0 not an array = 1 variable is an array IDs - 0 not a user function = 1 variable is a user function 19 SYNA uses b to signal "defined" or -undefined" during the parse. The remaining bits could be used individually or in combination to signal other possible data types (e.g., character strings) in a future improved version. Single character scalar names are stored in the symbol table as [first char] [second char] = [letter] [blank], double character scalars as [letter] [digit], arrays as [letter] [(], and user functions as [FN] [letter]. Thus the type of any entry may be determined from either its flag bits or its name. For arrays and user functions whose value is not stored in the symbol table, the 5 byte value field is used for other information. In particular, the entries look like: scalar entry 1 5 byte value array entry X X upx up2 up3 user function high low disp X X where: up. is the i upper bound of the array, with all arrays internally having three dimensions whose default upper and lower bounds are zero; (high, low) is an address pointer which marks the return address when the function has been evaluated; disp is the symbol table displacement of the function's dummy parameter. Note that the design of the symbol table allows the simultan- eous use of the scalar A, the scalars AO, Al, ..., A9, the array A( , and the user function FNA with no ambiguity and no extra overhead in either LEXI or LOOKUP. 20 5. EXECUTION PACKAGE No computing system intended for scientific use would be complete without true number -crunching ability. Since our BASIC system is designed for a whole range of applications, it seemed imperative that extensive floating point arithmetic capabilities be included. In an effort not to "reinvent the wheel," we decided to purchase the floating point arith- metic package utilized by the Datapoint 2200, a popular minicomputer whose CPU is similar to an Intel chip. The Datapoint software provides the means for floating point addition, subtraction, multiplication, division, and comparison, as well as both ASCII-character-string -to- internal-floating -point and internal-floating -point-to-ASCII-character- string conversion0 21 6. SUMMARY The whole project, which extended for a period of approximately five months, successfully illustrated the feasibility of a BASIC inter- preter running in a microprocessor environment. The basic design of the system is good, and serves well as a model for similar interactive systems . It is regretable that time did not permit us to try our design on real -world hardware. We believe that the actual implementation of such a system might well be a project for future research. 22 APPENDIX A BASIC LANGUAGE BW | (CR) ,2 = {} 0 | J | | | | | < input statement> | | | LLET) f^\ | (ORj | rANDj I [ (+ | -) | (*|/) | | ( t) ©10101 ©101© | I I [] _(_ { , } _ )_ 23 A | B | C I ... | Z 0 | 1 | 2 | 3 | k | 5 | 6 | 7 [ 8 | 9 = + NOT) () (FN) | (SIN) f (cos) | (LOG) [~ (sqr) (exp) | ft [+ | -] {+ [.] | * 0+] [E[+ | -] []] (DIM) = _£_ { , ] _ ) 2 ,+ 0 { , _£_ { ,} } such that 0 < number < 255 JDEF) (FN) {_ ]_ (^\ (REM) (cr) K)TQ such that 0 < number < 999 (if) (THEM (FORJ C=) (TO) [ (STEFJ ] (NEXT) ^GOSUBy (return) (INPUT) ( , } (PRINT) { , | "" | any TTY character except " (STOP] KNm 2k APPENDIX B DESCRIPTION OF THE STATE TRANSITIONS FOR THE SYNTACTIC RECOGNIZER The parser that is used in our BASIC system is essentially a one stack push down automata; the parsing technique is top-down goal oriented with the stack used for state sub-calls and recursion. book- keeping. In the following discussion the abbreviations used are: SYMB: a token's symbol class, i.e., identifier, reserved word, etc. SEM: a token's concrete representation, i.e., "+", "IF", etc. In order to describe the parser's state transitions a few state transition diagram conventions or notations have been developed. A transition from one state to another will occur at least once for every new token from the input string. Each state in the diagram will have at least one branch coming out of it. These branches are usually labeled with the conditions necessary for that branch to be taken. An unlabeled branch is taken as a last resort. If none of the branches is satifsfied, it indicates an error condition. If a branch has more than one condition on it, the conditions are each placed on a separate branch and the branches are connected together; to reach the end of a branch, all inter- mediate branches must be satisfied. The end of a branch sequence contains the state transition information,, Usually, just the "next state to move into" is indicated; sometimes a box, such as 25 may appear at the end of a branch; this indicates an intermediary "state call" must take place before the transition to the "next state" occurs (in other words, save the "next state" on the parser stack and make the state transition to the state in the box)., Likewise, sometimes a symbol such as may occur in a branch; this indicates the state transition is to the state at the top of the stacko For example, examine the BASIC GOTO statement: : : = GOTO EOL The state transition diagram for this statement is: SI) SEM = "goto" . S2 S2j SYMB = , S3 S3 J SEM = eol . This is interpreted as : If you are in state SI and the current token is a "GOTO", then move into state S2. If you are in S2 and the current token class is , move into state S3. If you are in state S3, and the current token is "EOL" (end of line), move to the state for the beginning of a new statement. Note that in all cases here, if the given condition is not met, there is an error. As another example, consider the IF statement: ::= IF THEN EOL The transition diagram for this is: SI SM="if g Sk 26 SEM = eol # This is interpreted as: If you are in state SI and the current token is an "if", then push S2 onto the parser stack and make the transition to state (although not shown, state will parse an expression as defined by BASIC and, when finished, will make the transition to the state at the top of the stack, namely S2, and then pop the stack). The rest of the diagram is interpreted similarily. This concludes the discussion of the state transitions for our system. The table system Given the state transition diagrams for a language, the remaining problem is to encode the information and actions of the diagrams into a table format. To succeed, the table must contain fields for: 1) Checking the branch conditions. (a) Checking the SYMB or SEM values of the current token (b) Ability to check efficiently for all the branches of a state (c) Ability to detect an error condition (d) Ability to check multiple conditions, i.e., more than one branch condition to reach the end of the branch 2) Stack operations. (a) Push a state onto the parser stack (b) Pop a state off the parser stack and make the transition to that state 3) Normal "next state" transitions. k) Since taking a branch normally means accepting the current token and moving on to the next token in the input string, there must be someway of making an 'epsilon move', i.e., changing the state while not moving the input pointer. 27 5) In this system we wanted to be able to have the table drive the actual execution of the statement as well as just syntactically parse it. Also, since the system will keep up with the programmer (FOR- loop nesting checks, defined functions and arrays) even during simple parsing mode, the table needs to indicate what routines to perform and when they should be performed. With these requirements in mind, we describe the actual table system. The system is divided into two parts, the table itself and a routine to interpret the table. Consider the table to be actually a large vector, where each element of the vector is one "entry" in the table. There are four types of entries in the table: HEADER, VALUE, CONTROL, and ERROR. HEADER The HEADER entry contains information about the next few entries in the table. It tells what tests to make, how many of them to make, and what to do if they all fail. In particular, there are three fields in the entry: TYPE (2 bits): The TYPE field contains a number (0-3) that ident- ifies the type of branches for that state. QUAN {k bits): The QUAN field contains the number of branches for the state. FAIL (2 bits): The FAIL field contains a number indicating what to do if all the branch tests fail. These fields are discussed in more detail on page 29. VALUE The VALUE entry contains only one field. This field holds a number which is to be compared with either the current SYMB or SEM token value, depending on the previous HEADER that was processed. If the field's number matches the current token properly, then the correct branch has been 28 located for this state and the next CONTROL entry should be interpreted. On the other hand, if the field's number did not match the token, then this branch has failed; in this case, the previous HEADER information will determine what table entry to look at next. CONTROL The CONTROL entry is interpreted only when a correct branch has been located for a state. The CONTROL entry corresponds to "the end" of a branch in the state transition diagram. It contains fields for Push state, POP, Next state, whether more conditions must be checked, whether this is an epsilon move, and also an execution/parse routine number, along with three bits for the the mode checking - one for each mode: unparse, parse, execute, If the mode bit in the table that corresponds to the actual mode of the system is set, the routine is called. In all cases, if a field value is 0, then. that option is ignored when the CONTROL entry is interpreted. ERROR The ERROR entry is interpreted when all the branches have failed for a state and the HEADER'S FAIL field equals 1, indicating an error exists, The ERROR entry contains an error number, which can be extracted and passed on to the error display routine. These are the entries in the table. The detailed bit implementation follows HEADER quantity fail type 29 TYPE The TYPE field determines exactly what branch conditions must be checked for and what the order of the next entries in the table is. type = 0 Unconditional TRUE branch. The next table entry is a CONTROL entry that is immediately interpreted. type = 1 Branch condition : SYMB value check. The following two table entries consist of a VALUE entry followed by a CONTROL entry; the current token's SYMB value is compared to the VALUE table entry; if they are equal, then the CONTROL entry is interpreted; if unequal, then the CONTROL entry is jumped over in the table and different tests can be made (see fail). type = 2 Branch condition: SEM value check. Same form as type=l. type = 3 Special case test. QUAN contains routine number. CONTROL follows . QUAN The QUAN field determines how many similar branches a state has. It gives the number of VALUE/CONTROL pair entries following the HEADER. For type =3, the QUAN value is a special case routine number. FAIL The FAIL field is used only when all the other checks have failed. fail=0 The next entry is a new HEADER with a new set of condition checks. It is "flowed" into. f ail = 1 The next entry is an ERROR entry. fail = 2 The next entry is an alternate CONTROL entry that should be immediately interpreted. 30 VALUE value Contains one number to be used according to the previous HEADER information, ERROR ERROR # 8 Contains an error number that is passed to the error message writer when an error is detected. CONTROL entry: 18 bits Unparse mode bit POP Push state Execution Parse Routine § Mode bits Parse Execute End of branch bit Epsilon move reparse Next state 1 1 6 6 1 1 1 1 6 The CONTROL entry is divided into three bytes. With the exception of the Unparse bit, all the fields are interpreted in order as they come. For the Execution/Parse/Unparse routine, the Unparse bit is ORed into the third bit position of a byte, and the other mode bits are ORed into the first two bit positions. Then this byte is compared with the current mode switch (which has values: Unparse = h> Parse =2, Execute = l). If the corresponding bit is set the execution routine is called. APPENDIX C STATE DIAGRAMS' FOR BASIC LANGUAGE TABLE-DRIVEN INTERPRETER 31 SYMB = Const err 1 ST1 (2) STEND (k6) ST1 (2) SYMB = rswd err2 SEM = let SEM = goto SEM = if SEM= stop SEM= end SEM = for SEM= next SEM = rem SEM = gosub SEM= return SEM= input SEM= print SEM= dim SEM= def err 3 II (3) el) Gl (6) EXPR (37) IP1 (8) ST0P1 (9) ST0P1 (9) FORI (10) NEXT1 (16) pelUV — (pop) — reparse el) G0SUB1 (17) jS) G2 (7) INI (21) (e23j- PR1 (2k) DIM1 (28) DEF1 (31) 32 SYMB = ident .SYMB = array err k e2 ARR1(19) 12(h) ^(^7) reparse < L2 ( h )) SEM=eq err 5 EXPR(37) 13(5) L3(5)L__SM=eol err SYMB = const err 7 -(pop) — reparse G2(7) G2(7)l SEM=eol err 8 pop) reparse IF1 ( 8 )) SEM=then err 6 Gl(6) SEM= eol err 8 pop) reparse FORI ,(io), SYMB = ident err F0R2 (11) SEM= eg err 5 EXPR(37) F0R3(12) F0R3 (12) SEM= to err 9 EKPR(37) -F0RJ+(13) 33 SEM= step EM= eol err 6 S'EM = eol err SYMB = ident SYMB= const err 7 SEM = eol SEM= comma SEM= thesis err )) SYMB = ident SYMB = array err 11 elOl ell) Jel2 & ARR1(19) EXPR(37) F0R5(lU) -F0R6 (15) reparse -FOR6(15) reparse pop) reparse •G2(7) •G0SUB2(l8) pop) reparse EXPR(37) JVRR2(20) EXPR(37) ■ARR2(20) IN3(23) -IN2(22) reparse IN3(23) reparse 3k DEF (3D SEM = comma SEM = eol err 11 PR1 ( 2k )) SEM=eol err SYMB = array err 12 SEM= comma SEM= thesis err Sffl= comma EM= eol err 13 SYMB = user fen err ik INI (21) 'pop) .(POP) ^>R2(25) Pe27l ^pe28\ DIMl(28) (pop) reparse reparse reparse PRM27) PR3(26) — repa: rse PR4(27) reparse reparse EXPR(37) _DIM2(29) EKPR(37)[ DIM2(29) DIM3(30) reparse DEF1(32) 35 SEM = par en SYMB = ident err 16 SEM = thesis /def^A err 17 SEM = ea err 5 SEM= eol SYMB = punlef t SYMB = ident SYMB = array SYMB = const SYMB = opun/opnot SYMB = bif SYMB = user fen err SEM= par en err 15 DEF2(33) DEF^(35) .(pe3l). IP°P ARR1(19) pe33) EXPR(37) DEF3(3*0 EXPR(37) .DEF5(36) reparse EXPR(37)| 0PER(^5) 0PER(l+5) EXl(38) reparse 0PER(1+5) EXPR(37) ARGl(^O) ARGl(^O) BIF1(39) ■FCNl(te) 0PER(i+5) reparse 0PER(^5) reparse ,ARG2()4l) 36 SEM = thesis err 17 reparse EXPRFCN ( kk ) FCM2 r epar s e (U3) test Mode = execute Special Case 1 SYMB = oplla SYMB = opbin SYMB = punrite SYMB = oprel SYMB = opcond STACKTOP=oper special case 3 -err 15 EXPR(37) (ek2\ [eh^ Special Case 2 stacktop- o-yevik'o) OPER(l^) — reparse reparse .reparse EXPR(37) EXPR(37) reparse EKPR(37) EXPR(37) reparse ^ -UeW l£(k) repar se 37 APPENDIX D PROGRAM EXAMPLE The following pages show the successive (simulated) states of the TV screen in response to various keyboard commands issued in the text -editing mode. 38 The simulated TV screens below show the successive states of the visual image as it responds to insertion, deletion, replacement, and cursor movement under control of the BASIC text editor. The screens are presented in columns, and should he read top to bottom and left to right. 9 LET A9 LET A = 9 LET A = 6 9 LET 9 LEt A 3 LET A = 63 LET A = 6 IF 9 39 LET A = 6 IF A S LET A = 6 IF A = 7 THEN 9 LET A = 6 IF A = 7 THEN P = OS LET A = 6 IF A = » LET A = 6 IF A = 7 THEN P3 LET A = 6 IF A = 7 THEN P = Q 3 LET A = 6 IF A = 7a LET A = 6 IF A = 7 THEM P 3 LET A = 6 IF A = 7 THEN P = 0 Da LFT A = 6 IF A = 7 ^ LET A = 6 IF A = 7 THEN P = 3 LET A = 6 IF A = 7 THEN P DE9 = 0 1+0 LFT A = 6 IF A = 7 THEN DEF3 LET A = 6 P = 0 if A = 7 THEN P = DEFINE A<^ LET A = 6 IF A = 7 THEN P OEFINF At It 2) fl = 0 LET A = 6 TF A = 7 "HEM DEFI? P = 0 LET A IF A = DEFINE 7 THEN P = AtlS) LET A = 6 IF A = 7 THEN DEFINE All, 2) 3 P = 0 LET A = 6 IF A = 7 ■ DEFINE 'HEN P = 0 LET A = 6 IF A = 7 THEN P = DEFINE A(l,» LET A = 6 IF A = 7 THEN P aDEFINF A (1,2) = 0 LET A = 6 IF A * 7 THEN DEFINE? LET A = 6 P = 0 IF A = 7 THEI^ P = DEFINE AC1,25> LET A = 6 IF A = 7 THEN P D^EFINE A (Lf 2) = 0 kl LET ft = 6 IF ft = 7 THEN P = DEFINE 4(1,2) LET A' - 6 IF A = 7 THEN P = DEF3> A<1,2» LET A = 6 IF A = 7 THEN P = 3EF A (1,2) Q LET A = 6 IF A = 7 THFN P = DEF3INE A(l,2) LET A = 6 IF A = 7 THEN P = DE3F A(l,2) LET A = 6 IF A = 7 THEN P = Q 3F A (1,2) LET A = 6 IF A = 7 THEN DEFINE A(l,2) P = 0 LET A = 6 IF ft = 7 THEN P = 03>EF A( 1,2) LET A = 6 IF A = 7 THEN P = a A( 1,2) LET A = 6 IF A = 7 THEN P = 0 DFF^E A(l,2) LET A = 6 IF ft = 7 THEN P = 3DEF A(l,2) LET A = 6 IF A = 7 THEN P = 3 A(l,2) 42 LET A = 6 IF A = 7 THFN DEF a A( I ,?) p = O LFT A = 6 TF A = 7 THEN OFF Ml,?) THIS P = 0 LET A = 6 TF A = 7 THEN DEF A(l,2) THIS LH p = n LET A = 6 IF A = 7 THFN DEF Ml, 2) P = q LET A = 6 IF A = 7 THFN DEF A (1,2) THISS P = 0 LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LIN3 P = 0 LET A = 6 tf A = 7 THEN DEF A (1,2) T3 P = Q LET A = 6 IF A = 7 THEN DEF A(l,2) THIS ?? P = 0 LET * = 6 IF A = 7 'HEN DEF A(l,2) THIS LI NFS P = O LET A = 6 IF A = 7 THEN DEF A (1,2) TH3 P = 0 LET A = 6 IF A = 7 THFN DEF A(l,2) THIS LS P = 0 LET A = 6 IF A = 7 THFN DEF Ad, 2) THIS LINE 9 P = 0 ^3 LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINF W3! LET A = 6 P = 0 IF A = 7 THEN! P = OEF A (1,2) THIS LINF WILL S> LET A = 6 IF A = 7 THEN P = OEF A (1,21 THIS LINE WILL BE OS) LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINF WIS) LET A = 6 P = Q IF A = 7 THEN P = DEF A(l,2) THIS LINF WILL B3 LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL P = 0 BE DE3 LET A = 6 IF A = 7 THFN P DEF A(l,2) THIS LINE WHS! LET A = 6 = 0 IF A = 7 THEN P = I OEF A<1,2) THIS LINE WTLL BES> LET A = 6 IF A = 7 THEN DEF A(L,2) THIS LINE WILL P = 0 BE DELS* LET A = 6 IFA=7THFNP=Q DEF A(L,2) THIS LINF WILL^ LET A = 6 IF A = 7 THEN P = DEF A(l,2) THIS LINE WILL BE LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL P = 0 BE DELE 3 kk LET A = 6 IF A = 7 THFM DEF A (1,2) THIS LINE WILL p = 0 BE DELETE LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL R9 P = 0 BE DELE_ED LET A = 6 IF A = 7 THEN DEF 4(1,2) THIS LIME WILL p = 0 BE DELETE? LET A = 6 IF A = 7 THEN DEF A (1,2) THIS LINF WILL RES! P = 0 nE DELETED LET A = 6 IF A = 7 THFN DEF All, 2) ^HIS LINE WILL p = KE DELETED? LET ft = 6 IF A = 7 THEN DEF A(L,2) THIS LINE WILL REPS p = 0 «E DELFTED LET A = 6 IF A = 7 THEN DEF AQ,2) THIS LINE WILL P = 0 BE DELETED LET A = 6 IE A = 7 THEN VEF A(lf2) THIS LINE WILL RFPL? P = Q BE DFLETED ^ LET A = 6 IF A = 7 THEN DEF A<1,2) THIS LINE WILL REPLAY P = 0 RE DELETED LET A = 6 IF A = 7 THEN DEF A (1,2) THIS LINE WILL REPLACE R^ P = 0 BE DELETED LET A = 6 IF A = 7 "THEN DEF A(l»2) THIS LINE WILL REPLACE P = Q BE DELETED LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL REPLACE P a P = 0 BE DELETED LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINF WILL REPLACED P = 0 BE DELETFD LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL REPLACE P W3 P = 0 BE DELETED LET A = 6 TF A = 7 THFN DEF A(L,2) THIS LINE WILL REPLACE a P = 0 BE DELETED LET A = 6 IF A = 7 THEN DEF A(lf2) THIS LINE WILL REPLACE P WIS) P = 0 BE DELETED k6 LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL REPLACE B WITa P = 0 PE DELETED LET A = 6 IF A = 7 THEN DEF A(l,2) THIS LINE WILL REPLACE R WI^h P = 0 BE DELETED L3 LET A = 6 IF A = 7 THEN P = 0 DEF A(l,2) THIS LINE WILL BE DELETED REPLACE P Wl^Hfl! LET A = 6 IF A = 7 THEN P = 0 DEF A (1,2) THIS LINE WILL BE DELETED REPLACE R WI~H L S) LET A = 6 IF A = 7 THEN DEF Ml, 2) THIS LINE WILL REPLACE R with P = 0 BE DFLETFO LET A = 6 IF A = 7 THEN P = 0 DEF A(l,2) THIS LINE WILL BF DELETED REPLACE R WITH L 3 LET A = 6 IF A = 7 THEN P = 0 DEF A(l,2) THIS LINF WILL BE DELETED RE°LACE p WITH 3 LET A = 6 IF A = 7 THEN P = o DEF A (1,2) THIS LINE WILL BE DELE REPLACE P WITH L P S» TD k! LET A = 6 IF A = 7 THEN P = 0 DEE AM, 2) THIS LINE WILL BE REPLACE R WITH L 9 DELETED P LET A = 6 IF A = 7 THEN P = 0 DEF AM, 2) THIS LINE WILL BE DELETED REPLACE R WITH L La LET A = 6 IF A = 7 THEN P = 0 DEF A (1,2) THIS LINE WILL PE DELETED REPLACE R WITH L P3 LET A = 6 IF A = 7 THEN P = Q DEF AM, 2) THIS LINE WILL BE DELETED ^REPLACE P WITH L L LET A = 6 IF A = 7 THEN P = Q DEF AM, 2) THIS LINE WILL BE DELETFD REPLACE R WITH L ?DR LET A = 6 IF A = 7 THE>^ DEF AM, 2) 3THIS LINE WIl L REPLACE P WITH P = 0 BE L DELETED L LET t = 6 IF A = 7 THEN P = 0 nEF AM, 2) THIS LINE WILL BE DELETED REPLACE P WITH L ^P LET A = 6 IF A = 7 THEN P = 0 DEF AM, 2) ^REPLACE R WITH L 48 LET A = 6 IF A = 7 THEN OEF A (1,2) REPLACE R WITH 3 P = 0 LET A = 6 IF A = 7 THEN P = DEF Ad, 2) REPLACE R WITH L BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-7U-658 3. Recipient's Accession No. 4. Title and Subtitle A BASIC Language Interpreter for the Intel Microprocessor 5. Report Date June 197^ 7. Author(s) Weaver, A.C., Tindall, M.H. , Danielson, R.L. 8- Performing Organization Rept. No. UIUCDCS-R-7U-b50 °. Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 10. Project/Task/Work Unit Nc 11. Contract/Grant No. 12. Sponsoring Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 13. Type of Report & Period Covered 14. IT :»iij pk-mentary Notes '6. Abstracts A BASIC language interpreter has been designed for use in a microprocessor environment. This report discusses the development of 1) an elaborate text editor and 2) a table-driven interpreter. The entire system, including text editor, interpreter, user text buffer, and full floating point arithmetic routines fits in l6K 8-bit words. 17. K v Words and Document Analysis. 17a. Descriptors BASIC language interpreter microprocessor text editor 17b. (Jentificrs Open-Ended Terms 17c. ( OSATI Kield/Group IK. til.ibility Statement release unlimited 19. Security ( lass (This Report ) UNU.AS.SU-Il.p 20. Sa urn v ( lass ( Th i Page UN( LASSIFIED 21. No. ol I k8 ages M N Til IB I 10- 70) 22. I'n, e no charge USCOMM-DC 40'jJI-l' Jl FEB 1 7 1981