Algorithmic Notation (Compiler Writing) Part 2

ARITHMETIC OPERATIONS AND EXPRESSIONS

The algorithmic notation includes the standard binary and unary operators, and, of course, these are given the standard mathematical order of precedence. Table A-l should make this clear.

Arithmetic expressions may contain variables which have been assigned numeric values and are evaluated the same way as in mathematics. Thus, we may write the notation we assume two types of numeric values, real and integer. , In

Table A-l Arithmetic Operators and Precedence

	Operation	Symbol	Order of evaluation
1.	Parentheses		Inner to outer
2.	Exponentiation		Right to left
	Unary plus, minus
3.	Multiplication		Left to right
	Division
4.	Addition		Left to right
	Subtraction

As this implies, a real variable can hold any value, whereas an integer variable can only hold integer values with any fraction being truncated. As an example, if R is of type real and I of type integer,will assign a value of .75 to R whilewill assign a value of 0 to I.

STRINGS AND STRING OPERATIONS

The algorithmic notation facilitates the processing of nonnumeric information. A character string is just that, a string of capitalized characters enclosed in single quotation marks (‘THIS IS A VALID STRING’). For clarity, a blank is often denoted by a box; ‘□□’ is a string containing two blanks. The null, or empty, string is denoted by two adjacent quotation marks, ". Note that this is not the same as ‘□’ which is a string containing a single blank.

The simplest string operation is that of concatenation denoted by ‘ ° 1; for example, ‘FRUMIOUS’ ° ‘□’ » ‘BANDERSNATCH’ is equivalent to ‘FRUMIOUSDBANDERSNATCH’. Just as variables may hold numeric constants or values of arithmetic expressions, so they may represent character strings, thus, we may write G «- ‘GRYPHON’. Other string manipulations include functions such as LENGTH, INDEX, and SUB, which are patterned after PL/I’s LENGTH, INDEX, and SUBSTR functions, respectively. The SUB function, however, is more general and is as follows:

SUB(SUBJECT, i, j) or SUB(SUBJECT, i) returns as a value the substring of SUBJECT that is specified by the parameters i and j, or i and an assumed value of j. The parameter i indicates the starting cursor position of the substring, while j specifies the length of the required .substring. If j is not provided, j is assumed to be equal to k – i + 1, where k is equal to the length of the argument SUBJECT. To complete a definition of SUB, some additional cases must be handled.

Consider the following examples for the function SUB. SUB(‘ABCDE’, 2) and SUB(‘ABCDE’, 2, 7); both return ‘BCDE’, SUB(‘ABCD’, 3, 2) returns ‘CD’, and SUB(‘ABCDE’, 0, 3) and SUB(‘ABCDE’, 6) both return "

RELATIONS AND RELATIONAL OPERATORS

In this topic the relational operatorsare written the same, way as, and have the same meaning as, their mathematical counterparts. Relations between variables and expressions will be considered valid if the variables have been assigned some value. A relation evaluates to a logical expression, that is, it has one of two possible values, true or false. Numerical relations are clear. Relations between strings are possible and depend on a collating sequence such as ‘□&#… ABC … Z01 … 9′. According to this sequence, special characters are lexically less than letters which, in turn, are lexically less than digits. Of course, relations between data types are not possible. In the following examples, Z has the value 10 and MT has the value ‘MOCK TURTLE’:

Relations 1, 2, and 3 have the values false, true, and true, respectively.

LOGICAL OPERATIONS AND EXPRESSIONS

The algorithmic notation also includes the standard logical operators. These are:

Operator	Notation
negation	not
logical and	and
logical or	or

which are given in decreasing order of their precedence. These may be used to connect relations to form compound relations whose only values are true and false. In order that logical expressions be clear, we assume that operator precedence is as follows:

Precedence	Operator
1	Parentheses
2	Arithmetic
3	Relational
4	Logical

Consider the following, assuming that ONE is a variable whose value is 1:

Expressions 1, 2, and 3 have the values false, true, and false, respectively.

Just as we have numeric and character variables, so we have logical variables (for example, FLAG «- true). Logical expressions are most often used as conditions in repeat and if statements. In a repeat statement one might have:

INPUT AND OUTPUT

In the algorithmic notation, input is obtained and placed in a variable by the statement "Read(variable name)." Output has the form " Write(literal or variable name)" with literals enclosed in quotation marks. For example, we may output the value of X by writing Write(X) if X is any variable, or we may output messages by writing Write(‘STACK UNDERFLOW’). Input and output are not limited to single variables; Read(X, Y, Z) is certainly valid and causes three consecutive pieces of data to be read into X, Y, and Z, respectively. In fact, we may extend input and output to arrays; for example:

Lastly, end of file may be used as the terminating condition of a repeat statement (e.g., Repeat while there is input data).

SUBALGORITHMS

A subalgorithm is an independent component of an algorithm and for this reason is defined separately from the main algorithm. The purpose of a subalgorithm is to perform some computation, when required, under control of the main algorithm. This computation may be performed on zero or more parameters passed by the calling routine. The format used is the same as for algorithms except that a return statement replaces an exit statement and a list of parameters follows the subalgorithm’s name. Note that subalgorithms may invoke each other and that a subalgorithm may also invoke itself recursively. Consider the following recursive function:

Function FACTOR I AL(N). This function computes N! recursively. N is assumed to be a nonnegative integer.

In the algorithmic notation there are two types of subalgorithms: functions and procedures.

Functions

A function is used when one wants a single value returned to the calling routine. Transfer of control and returning of the value are accomplished by "Return(value)". A function begins as follows: Function NAME (PARM1, PARM2,…, PARMN). The following example function should make clear the format of functions:

Function AVERAGE(VAL1, VAL2, VAL3). The purpose of this function is to compute the average of three values. We assume all variables to be real. AV is a local variable of type real used to return the computed value.

A function is invoked as an implicit part of an expression; for example, E «- AVERAGE(X, Y, Z) results in the returned value being put into E.

Procedures

A procedure is similar to a function but there is no value returned explicitly. A procedure is also invoked differently. Where there are parameters, a procedure returns its results through the parameters. Here is an example of a typical procedure:

Procedure DIVIDE(DIVIDEND, DIVISOR, QUOTIENT, REMAINDER). This procedure divides the DIVIDEND by the DIVISOR giving the QUOTIENT and REMAINDER. Assume all numbers to be integer.

 

Note that no value is returned explicitly but that the quotient and remainder are returned through two of the parameters. A procedure is invoked by means of a call statement: for example, "CALL DIVIDE(DDEND, DIV, Q, R)".

Parameters

In all sub-algorithms there is a one-to-one positional correspondence between the arguments of the invocation and the sub-algorithm parameters. With the AVERAGE function we just described there is a one-to-one correspondence between the parameters VAL1, VAL2, and VAL3 and the arguments X, Y, and Z of the invocation E <- AVERAGE(X, Y, Z). All parameters are assumed to be "call by reference" unless otherwise specified; therefore, if parameters are to be "call by value", this should be stated in the preamble, as should all other assumptions. Lastly, as mentioned before, there may not be any parameters. In this case, all variables are assumed to be global. Of course, there be global variables as well as parameters.