Section 4: A 4. :: l3 l5 17 O l.4250000OOOOOOOe+0i $ Arithmetic Overflow. There is currently no provision for an arithmetic overflow as might if this were typed ?{io“iooo} Unfcrtunately for some strange reason this does not occuri foilowing udc execution extract OCCUI Consider the Udc Sequence 8. S udc UDC> ?{io“i0on} 0 UDC> ?{io“i0} 1410065407 UDC> ?{1o“i5} ~l530494977 UDC> “D S This extract also shows the gross errors incurred when using the exponentiation operator, caused by the formula used for this calculation since there is no exponentiation operator in Pascal [l.4.2f]. Alternative Printing Formats» The supplying of one of the arguments ”~pre" or "~post" could result in the selection of an alternative printing format ~ either prefix or postfix respectively, [2.3.6b], rather than the default infix. Floyd Productions w An Alternative Parsing Method» This is a parsing method attributed to R. W. Floyd (1961). matching parts of the input to the parser with a set of predefined patterns. Rules define how, once a matching pattern is found, the input is to be reduced. By successive application of these rules the input can be reduced to one symbol denoting a successful parse, The process of scanning the set of rules can be speeded up by the parsing procedure also rendering a position in the table of rules from which the search for the next rule begins“ This method is flexible and fast but unfortunately the rules are very hard to work out for a given language. It depends on Appendicesi @191: Original BNF Specificaticni :~= { ’;° } = ‘?’ °A‘ '%’ ~ ‘if’ ‘then’ ’[° ’]° '{° ’}' 9@V ‘I’ '&° '2‘ ’else‘ 431. 4.3: ¢O 3 G0 2: Adjusted BNF Specificationl := { ';° } 6'39 2 ‘if’ then else i@! ‘{’ <€Xp> '}° . . <€Xp> 9)! 9“! v*s !%§ .- -n ---~2°\/V am on fig! was 3 $35 f ‘z ’(§ ’)’ ‘A’ I ‘B’ i i E2“ { dig } * ‘O’ 3 *1‘ 1 ..§ 3 abs 1 39! Pseudocodes For All Proceduresg 4¢3.l: CheckArgs if there are arguments to the udc call then allow prompt suppression else disallow prompt suppression 4.3.2: VarTblInit for all simple variables make a new tree cell set centents to those for undefined value set this variable‘s entry in the variable table to this cell for all vector variables for all allowable index values make a new tree cell set contents to those for undefined value set this variable”s entry in the variable table to this cell 4.393: MakeOpRankTbl define operator precedences for all unary and binary operators with unary minus as lowest and logical ’or° as highest followed by an operator to force stack reduction, followed by an irreducible stack base operator £$3$4: MakeLeXStateTbl define new lexical analyser states from old states and current symbols for all non~error sequences, leaving remaining error sequences as default new state of zero 4,3,5: MakeLexSymTbl define lexical values for all final states of lexical analyser and for unary minus and end of command characters 493.6: Getlp clear input store reset current char to single space while the current char is not a semicolon and not at end of line current char is storable read current char if current char is colon then skip to read subsequent chars from next line current char is not storable if current char is semicolon then current char is not storable if current char is space then current char is not storable if current char is tab then current char is not storable if current char is storable store current char if current char is semicolon then prepare to suppress prompt else prepare not to suppress prompt if end of input line then skip to read subsequent chars from next line 4Q3&7: SaveToken ( code ) store default token semantic value 0 store lexical value defined by the lexical symbol table entry for value code if code is that for a number token then get numeric value of character sequence from token buffer and store this as semantic value if code is that for a simple variable store semantic value as the variable's alphabetic position if code is that for a vector variable store semantic value as the variable’s alphabetic position 4.3.8: LeXAnalyse clear token store reset input store pointer repeat empty token buffer empty char buffer set current state to initialisation value set default tokencode for error token while input store pointer has not reached the end of the input store and current state is not the error state get next char from input store store Char at end of char buffer get new state from state table based on old state and current char if current state is that for a complete token in char buffer then record current state in tokencode move contents of char butter to end of token buffer if token buffer in empty then retreat input store pointer to be able to read in the contents of char buffer again record error token in tokencede advance input store pointer past current error starting char else retreat input store pointer to be able to read in the contents of char buffer again if token recorded by tokencode is minus sign and the token store is not empty then if token at end of token store is variable or number or right parenthesis or right brace then SaveToken ( number code for binary minus ) [4e3a71 else SaveToken ( number code for unary minus ) [4.3.7] else SayeToken ( tokencode ) [4.3.7] until input store exhausted SaveToken ( number for end of command ) [4.3.7] 4.3.9: Error ( errortype ) for the value of errortype print an appropriate error message 4e3ol0: Traverse ( T ) if T points to an empty tree then no action else if lexical value of T is in operator set or if and brackets flag set then print ( lexical value of T is if then print if Traverse ( pointer to left subtree ) [4@3$lOj print then Traverse ( pointer to left subtree of right subtree ) [4e3clOj print else Traverse ( pointer to right subtree of right subtree ) [4i3ilOi if lexical value of T is in binary operator set then Traverse ( pointer to left subtree ) [4.3rlO} case of this operator in maximum: print /\ minimum: print \/ exponentiationz print modulus: print % multiplication: print * division: print / addition: print + less than: print < less than or equal to: print <= equal to: print == greater than or equal to: print >= greater than: print > logical and: print & logical or: print or binary minus: print ~ Traverse ( pointer to right suhtree 3 [4.3.lO] if lexical value of T is in unary operator set then case of this operator in unary minus: print ~ logical not: print S Traverse ( pointer tc left snbtree ) [4.3.lO] if lexical value of T is number then print semantic value of tree cell if lexical value of T is simple variable then print character appropriate to semantic value of the tree cell if lexical value of T is the undefined value then print @ if lexical value of T is vector variable then print character appropriate to semantic value of the tree cell print ( Traverse ( pointer to left subtree ) [4.3.lO] print ) if lexical value of T is in operatcr set or if and brackets flag set then print ) 493911: SUV ( T ) variable self dependency false if lexical Value of T is in binary operator set then if SDV ( pointer to left subtree ) {4.3tll} or SDV ( pointer to right suhtree ) [4.3,l2] then self variable dependency true if lexical value of T is in unary operator set then if SDV ( pointer to left suhtree ) [4$39ll] then self variable dependency true if lexical value of T is the undefined value er number then variable self dependency status false if lexical value of T is simple variable then if this variable‘s dependency code is the same as that of the variable to be assigned to then variable self dependency true else set variable self dependency to SDV ( pointer extending from this variables’s entry in variable table ) [4¢3§ll] if lexical value of T is vector variable then if this variable’s dependency code is the same as that of the variable to be assigned to then variable self dependency true else set variable self dependency to SDV ( pointer extending from this variables's entry in variable table ) [4.3.ll] if lexical value of T is if then set variable self dependency to SDV ( pointer to left suhtree ) [4.3.ll] or SDV ( pointer to left subtree of right snbtree ) [4.3.ll] or SDV ( pointer to right subtree of right subtree ) [4.3.ll] 4.3.12: Eval ( T ) make new tree cell if lexical value of T is simple variable then new tree cell pointer points to Eval ( pointer to this variable°s entry in variable table ) [4.3.l2} if lexical value of T is the undefined value then new tree cell pointer points to this tree cell if lexical value of T is number then new tree cell pointer points to this tree cell if lexical Value of T is vector variable then new tree cell pointer points to Eval ( pointer to this variahleis entry in variable table ) {4$3$l2] if lexical value of T is in unary operator set then get pointer to Eval ( left subtree ) [4.3.l2] if lexical value of tree cell pointed to by this pointer is the undefined value then new tree cell pointer points to tree cell with lexical value of the undefined value else if the lexical Value of T is unary minus: new cell‘s semantic value is minus T°s left subtree’s semantic value logical not: new cell's semantic value is 1 if T°s left subtree's semantic value is O or is 0 otherwise other fields of new cell set appropriately to contain a number if lexical value of T is in binary operator set then i‘ get pointers to Eval ( left subtree ) and to Eval ( right suhtree ) [4.3.l2] if either of the lexical value of the tree cells pointed to by this pcinter is the undefined value then new tree cell pointer points to tree cell with lexical value of the undefined value else if the lexical value of T is maximum: new cellis semantic value is the maximum of T’s subtreesl semantic values minimum: new cell‘s semantic value is the minimum of T°s suhtrees’ semantic values exponentiation: new cell°s semantic value is T’left snhtree°s semantic value raised to the power of T's right snbtree°s semantic value modulus: if T’s right subtree's semantic value is G then Error [4.3.9} else new cell’s semantic value is T°s left suhtree’s semantic value modulus T’s right subtree*s semantic value multiplication: new cell‘s semantic value is the product of T‘s subtrees’ semantic values division: if the T's right subtree’s semantic value is 0 then Error [4@3%9] else new cell's semantic value is the quotient of T°s subtrees‘ semantic Values addition: new cell°s semantic value is the sum of T's subtrees’ semantic values subtraction: new cell's semantic Value is the difference of T“s suhtrees' semantic values lesswthan: if T°s left subtree's semantic value is less than T's right subtree°s semantic value then new cell‘s semantic value is l else new cell‘s semantic value is O less~than~or~equal~to: if T’s left suhtree’s semantic value is less than or equal to Tis right subtree’s semantic value then new cell“s semantic Value is 1 else new cell’s semantic value is O equal-to: if T’s left subtree’s semantic value is equal to T’s right suhtree‘s semantic value then new cellis semantic value is l else new cell’s semantic value is O greater~than—or-egual~to: if T's left subtree's semantic value is greater than or equal to T’s right subtree’s semantic value then new cell’s semantic value is l else new cell's semantic value is O greaterwthans if T’s left subtree’s semantic value is greater than T’s right subtree's semantic value then new cell’s semantic value is 1 else new cell’s semantic value is O logical and: if T’s subtree‘s semantic values are both nonwzero then new cell°s semantic value is l else new cell°s semantic value is O logical or: if either T‘s subtree‘s semantic values are nonwzero then new cell’s semantic value is l else new cell‘s semantic value is 0 new cell's other fields set appropriately to contain a number if T‘s lexical value is if then get pointer to Evaluation ( left subtree ) [4.3.l2] if this points to an undefined value then new tree cell pointer points to tree cell with lexical value of the undefined value else if the semantic value in the tree cell this points to is non~zero then get pointer to Evaluation ( T‘s right subtree’s left subtree ) [4.3.l2] if this points to an undefined value then new tree cell pointer points to tree cell with lexical Value of the undefined value else new tree‘s semantic value is semantic value of the evaluation of T’s right subtree’s left suhtree new cell’s other fields set appropriately to contain a number else get pointer to Evaluation ( T‘s right subtree’s right subtree ) [4i39l2] if this points to an undefined value then new tree cell pointer points to tree cell with lexical value of the undefined value else new tree’s semantic value is semantic value of the evaluation of Tls right subtree's right subtree new cell's other fields set appropriately to contain a number return new cell 4.3.l3: GetToken advance token store pointer forward one record the semantic and lexical values of the token now being referenced if itis lexical value is of an error symbol then Error [4,3.9} ¢93&l&: Backsym move token store pointer back one 4¢3Gl5: PassSym ( passme ) GetToken [4@3¢l3] if the lexical value of the current token is not the same as passme's then Error {4.3i9] 4$30l6: TopDown GetToken [4a3al3} case of its lexical value in array variable: make new tree cell set lexical and semantic values to those of the array variable define left subtree as Evaluation [4.3.l2] of subsequent expression obtained by BottomUp [4.3.l8] parsing if left subtree is undefined then Error [4,3.9] define no right subtree return pointer to the new eel left parenthesis: return pointer to subsequent expression obtained by BottomUp [4i3il8] parsing PassSym ( right parenthesis ) [4i3il5] left brace: return pointer to Evaluation [4Q39l2] of the subsequent expression obtained by BottomUp [4i3.l8l parsing if: make new tree cell set lexical and semantic values to those of the if token set left subtree to pointer to subsequent expression obtained by BottomUp [4.3.l8] parsing Passsym ( then ) [4.3.lS] make new tree cell attached to right subtree of previous cell set lexical and semantic values to those of the if~actions token set left subtree to pointer to subsequent expression obtained by BottomUp [403al8J parsing Passsym ( else ) [4.3.l5] set right subtree to pointer to subsequent expression obtained by BottomUp [4.3.l8] parsing return pointer to if cell 4.3.17: Reduce pop operator stack make new tree cell if the popped operator is unary then else if there are insufficient expression pointers on the expression stack for this operator to act upon then Error [4.3.9] pop expression stack insert popped operator's lexical and semantic values in tree cell insert popped expression pointer as left subtree and no right subtree if there are insufficient expression pointers on the expression stack for this operator to act upon then Error [4,3,9] pop expression stack twice insert popped operator’s lexical and semantic values in tree cell insert popped expression pointers as left and right subtree push pointer to new cell onto expression stack 4,3il8: BottomUp reset expression stack push irreducible token on operator stack default procedure exit permission false repeat GetToken [4.3,l3] case of its lexical value in operator set: while operator rank of this token is greater than that of operator on top of operator stack Reduce [4.3.l7] operator stack variable, number or undefined value: make a new tree cell set lexical and semantic values of this tree cell to those of the current token define no subtrees push pointer to this tree cell on to expression stack vector variable, left parenthesis, left brace or if: Backsym [4.3.l4] to enable rereading of this token by another procedure push the pointer to expression derived from a top down parse onto the expression stack right parenthesis, right brace, then, end-of~command, else: Backsym [4.3,l4] overwrite current token‘s lexical Value with the fullwstack~reduction token of higher precedence than normal operators while operator rank of this token is greater than that of operator on top of operator stack Reduce [4a3»l7J operator stack set procedure exit permission true assig or question mark; Error [4.3.9] until procedure exit permission true if operator stack clear and l expression pointer on expression stack then else 4,3.l9: return this pointer value Error [4,3,9] Parse reset token store pointer GetToken [4.3.l3] if its lexical Value is simple variable: record variable to be assigned to Passsym ( assignment sign ) [4¢39l63 get pointer to subsequent expression parsed BottomUp [4.3.l8] make unique Code for assigned variable if SDV [4.3.ll] returns that this expression depends on a variable with the same unique code then Error [4.3.9] else store pointer to expression in variable table question mark: get pointer to subsequent expression parsed BottomUp [4e3al83 if this expression is a single simple variable then revise pointer to point to the expression pointed to by this variable in the variable table if this expression is a single vector variable then revise pointer to point to the expression pointed to by this variable in the variable table Traverse [4o3el0] the expression now pointed to vector variable: record variable to be assigned to get explicit value of index using Eval £4e3el2j if this value is undefined then Error [4a3@9] if this value is negative or above defined maximum index then Error [4.3.9] Passsym ( right parenthesis ) [4.3.l6] PassSym ( assignment sign ) [4.3.l6] get pointer to subsequent expression parsed BottomUp {4.3.l8] make unique code for assigned variable if SDV [4.3.ll] returns that this expression depends on a variable with the same unique code then Error [4.3.9] else store pointer to expression in variable table all other symbols: Error [4.3.9] Passsym ( end of command ) [4.3.l5] 4.3.20: lnit CheokArgs [4.3.l] it prompts not being suppressed then give prompt VarTblInit [4.3.2] MakeLexStateTbl [4.3¢4} MakeLexSymTbl [4.3.5] define the operator set define the binary operator set define the unary operator set 4.3.21: Main Init [4.3,20] while input file nonwempty Getlp [4.3.6] if command longer than RETURN then LexAnalyse [4.3.8] Parse [4.3.l9] if only 1 command on line and prompts not being suppressed then give prompt if prompts not being suppressed then print a blank line to clear CTRL~D char