![]() Previous |
![]() Contents |
![]() Next |
No reckoning made, but sent to my account
With all my imperfections on my head.
Shakespeare, Hamlet
Its time to return to the calculator program that was developed in chapter 3, which was capable of evaluating arithmetic expressions like 2+3*4. Expressions were dealt with on a strict left-to-right basis, so that 2+3*4 would evaluate to 20. However, the normal rules of arithmetic tell us that the value of this expression should be 14, since the conventional interpretation involves performing multiplication before addition.
Modifying the calculator to deal with this will require delaying the addition operation until the multiplication has been performed. This is a well-known problem; algorithms to deal with this were first developed in the 1950s and refined in the 1960s. One approach is to use a data structure known as a stack. A stack is a collection with specific restrictions on how it can be accessed; the traditional comparison is with a pile of plates. New items can be added to the top of the stack (i.e. you can put more plates on top of the pile) and items can be removed from the top of the stack (i.e. you can remove plates from the top of the pile). The conventional names for these operations are pushing an item onto the stack and popping an item off the top. You can generally tell if someone is a programmer by asking what the opposite of push is; programmers say pop, everyone else says pull! There may be a few extra operations; for example, you may be able to find out how many items the stack contains or inspect the top item without removing it. What you cant do is add or remove items anywhere except at the top of the stack; if you were to try with a stack of plates the result might be a stack crash! A stack is said to have a last-in first-out (LIFO) organisation: the last item pushed onto the stack is the first one to be popped off.
Stacks are one of the most generally useful data structures around. They crop up in all sorts of situations; for example, the compiler relies on using a stack to keep track of procedure calls. When you call a procedure, your return address (the point in the calling procedure that you want to return to) is pushed onto a stack; returning from a procedure is simply a matter of popping the return address off the top of the stack and going back to the place it specifies. Stacks can also be used for evaluating arithmetic expressions according to the conventional rules of arithmetic.
The method for doing this requires two stacks, one for operands and one for operators. Whenever you see an operand, you put it on the operand stack; when you see an operator, you compare it with the operator on top of the operator stack. Each operation is given a priority (or precedence); multiplication has a higher priority than addition. If the operator youve just read has a higher priority than the one on top of the stack, you just push it onto the stack. This defers dealing with high-priority operators until youve had a chance to see what comes next. Otherwise, you remove the operator from the top of the stack, remove the top two values from the operand stack, apply the operator to the two operands and push the result onto the operand stack. You then repeat the process until the operator youre considering does have a higher priority than the one on top of the operator stack. In other words, when you see a low-priority operator you first of all deal with any deferred operators on the stack which have the same priority or higher. Finally, you push the operator youre considering onto the operator stack until you see what comes next.
To make this work, you need to prime the operator stack with an operator which has a lower priority than any other. At the end of the expression, operators must be removed one by one from the operator stack together with the top two operands from the operand stack; each operator is applied to its two operands and the result is pushed onto the operand stack. When you reach the low-priority operator on the bottom of the stack, the operand stack will contain a single value which is the result of the expression. Heres what happens if you evaluate 2+3*4+5 using this algorithm:
Input Symbol Operands Operators Action 1) 2+3*4+5. # (start state) 2) +3*4+5. 2 2 # Push 2 3) 3*4+5. + 2 # + + > #; push + 4) *4+5. 3 2 3 # + Push 3 5) 4+5. * 2 3 # + * * > +; push * 6) +5. 4 2 3 4 # + * Push 4 7) 5. + 2 12 # + + < *; apply * 8) 5. + 14 # + = +; apply + 9) 5. + 14 # + + > #; push + 10) . 5 14 5 # + Push 5 11) . 19 # . < +; apply +
The result is 19. Ive used # to represent the low-priority operator used to prime the operator stack. Operands and operators are pushed onto their respective stacks until step 7 is reached. Here weve got + and the operator stack has * on top. So the multiplication operator is removed from the operator stack, the top two items are removed from the operand stack (3 and 4), the multiplication operator is applied to the two operands, and the result (12) is pushed back onto the operand stack. Now we have a + on top of the operator stack, so step 8 repeats the process; 2+12 gives 14 which is pushed onto the operand stack. Now the top of the operator stack is #, which has a lower priority than +, so the + finally gets pushed onto the operator stack in step 9. At step 11 weve reached the full stop which signifies the end of the expression, so the + on top of the operator stack is removed, the two operands 14 and 5 are removed from the operand stack, and the result (19) is pushed onto the operand stack. The top operator on the stack is now #, so the value on top of the operand stack (19) is the final result.
At this point its worth considering the design of a package to implement a stack type. The stack type itself should be private to prevent users fiddling about with implementation details; it should also be limited to prevent attempts to copy one entire stack to another or comparing two stacks for equality. The package needs to be generic so that a stack of any type of item can be created; the generic parameter should be private for maximum flexibility, so that any type which supports assignment can be used. The package only needs to use assignment to store and retrieve the items, so this is no problem.
The two basic operations to be provided are Push and Pop. These will need the stack to be operated on as a parameter; it will need to be an in out parameter since it needs to be copied into the procedure and then modified. For convenience and completeness we can provide a few extra operations: a function Top which returns a copy of the top item on the stack, a function Size which returns the number of items on the stack, and a function Empty which returns a Boolean result to indicate whether or not the stack is empty.
There are two things that can go wrong: the stack can overflow as the result of attempting to push too many items onto the stack, or the stack can underflow as the result of attempting to access the top item of an empty stack. This means that we need two exceptions, Stack_Overflow and Stack_Underflow. Heres the resulting package specification, with the private part omitted for the moment:
generic type Item_Type is private; package JE.Stacks is type Stack_Type is limited private; procedure Push (Stack : in out Stack_Type; Item : in Item_Type); procedure Pop (Stack : in out Stack_Type; Item : out Item_Type); function Top (Stack : Stack_Type) return Item_Type; function Size (Stack : Stack_Type) return Natural; function Empty (Stack : Stack_Type) return Boolean; Stack_Overflow, Stack_Underflow : exception; private -- to be dealt with later end JE.Stacks;
Heres a modified version of chapter 3s calculator program which uses this stack package. Ive tried to keep the structural changes to a minimum so that you can compare this with the original version more easily:
with Ada.Text_IO, Ada.Integer_Text_IO, JE.Stacks; use Ada.Text_IO, Ada.Integer_Text_IO; procedure Calculator is package Operand_Stacks is new JE.Stacks (Integer); package Operator_Stacks is new JE.Stacks (Character); use Operand_Stacks, Operator_Stacks; Operand_Stack : Operand_Stacks.Stack_Type; Operator_Stack : Operator_Stacks.Stack_Type; Operator : Character; Operand : Integer; procedure Apply is Left, Right : Integer; Operator : Character; begin Pop (Operand_Stack, Right); Pop (Operand_Stack, Left); Pop (Operator_Stack, Operator); case Operator is when '+' => Push (Operand_Stack, Left + Right); when '-' => Push (Operand_Stack, Left - Right); when '*' => Push (Operand_Stack, Left * Right); when '/' => Push (Operand_Stack, Left / Right); when others => raise Program_Error; -- should never happen (!) end case; end Apply; function Prio (Operator : Character) return Natural is begin case Operator is when '+' | '-' => return 1; when '*' | '/' => return 2; when '#' => return 0; when others => raise Program_Error; -- should never happen (!) end case; end Prio; begin -- main program Push (Operator_Stack, '#'); Put ("Enter an expression: "); Get (Operand); Push (Operand_Stack, Operand); loop loop Get (Operator); exit when Operator /= ' '; end loop; if Operator = '.' then while Top(Operator_Stack) /= '#' loop Apply; end loop; Put (Top(Operand_Stack), Width => 1); exit; end if; case Operator is when '+' | '-' | '*' | '/' => while Prio(Operator) <= Prio(Top(Operator_Stack)) loop Apply; end loop; Push (Operator_Stack, Operator); when others => Put ("Invalid operator '"); Put (Operator); Put ("'"); exit; end case; Get (Operand); Push (Operand_Stack, Operand); end loop; New_Line; end Calculator;
This program uses an internal procedure called Apply which pops two operands and an operator and then pushes the result of applying the operator to the two operands; there is also an internal function called Prio which returns the priority of a selected operator. These procedures should never be called with anything except a valid operator, but Ive written them defensively; Murphys Law states that what can go wrong, will so rather than taking anything for granted Ive made sure that Program_Error will be raised by Apply and Prio if they come across an illegal operator character.
The program as it stands expects its input to be a sequence of integers separated by operators and ending with a full stop. However, we might want to be able to deal with expressions like 2*(3+4) which do not follow this pattern. In order to deal with parentheses, we need to read the input a character at a time rather than blindly assuming that the first thing on the line is an integer or that an integer follows every operator. Fortunately, Text_IO provides a procedure called Look_Ahead to enable us to look at the next input character without actually reading it. Look_Ahead takes two output parameters: a Character variable which will be set to the value of the next character and a Boolean variable which will be set True if were at the end of the line (in which case the character parameter wont be affected). Heres how we could use Look_Ahead to get either an operator or an integer, assuming the existence of a Character variable Ch, a Boolean variable EOL and an Integer variable I:
loop Look_Ahead (Ch, EOL); if EOL then Skip_Line; -- end of line, so go to next line elsif Ch = ' ' then Get (Ch); -- space, so read it and ignore it else exit; -- non-space, so exit loop end if; end loop; -- At this point, Ch is a copy of the next character, but the -- next character hasn't actually been read yet. We can read -- an Integer or a Character, as appropriate... if Ch in '0'..'9' then Get (I); -- digit, so get an integer in I else Get (Ch); -- non-digit, so read it into Ch end if;
Parentheses need to be dealt with in a special way. An opening parenthesis ( is given a priority of 0, just like the # which is used to prime the stack. Any operators which follow this will have a higher priority and so will be stacked up above it. When we get to the closing parenthesis we clear operators by applying them to their operands until the opening parenthesis is the top item on the stack. It is then discarded, as is the closing parenthesis. Well also need to check that there are no opening parentheses that havent been left unmatched at the end of the expression. This is what happens when 2*(3+4) is evaluated:
Input Symbol Operands Operators Action 1) 2*(3+4). # (start state) 2) *(3+4). 2 2 # Push 2 3) (3+4). * 2 # * * > #; push * 4) 3+4). ( 2 # * ( Push ( 5) +4). 3 2 3 # * ( Push 3 6) 4). + 2 3 # * ( + + > (; push + 7) ). 4 2 3 4 # * ( + Push 4 8) . ) 2 7 # * ( Apply + 9) . ) 2 7 # * Remove ( 10) . 14 # . < *; apply *
Heres a modified version of the program which allows for parentheses. Since Look_Ahead tells us when weve reached the end of the input line, we can use this as the expression terminator instead of requiring a full stop. Also, an exception Syntax_Error is used to respond to syntax errors in the input:
with Ada.Text_IO, Ada.Integer_Text_IO, JE.Stacks; use Ada.Text_IO, Ada.Integer_Text_IO; procedure Calculator is package Operand_Stacks i s new JE.Stacks (Integer); package Operator_Stacks is new JE.Stacks (Character); use Operand_Stacks, Operator_Stacks; Operand_Stack : Operand_Stacks.Stack_Type; Operator_Stack : Operator_Stacks.Stack_Type; Operator : Character; Operand : Integer; Line_End : Boolean; Got_Operand : Boolean := False; procedure Apply is Left, Right : Integer; Operator : Character; begin Pop (Operand_Stack, Right); Pop (Operand_Stack, Left); Pop (Operator_Stack, Operator); case Operator is when '+' => Push (Operand_Stack, Left + Right); when '-' => Push (Operand_Stack, Left - Right); when '*' => Push (Operand_Stack, Left * Right); when '/' => Push (Operand_Stack, Left / Right); when others => raise Program_Error; end case; end Apply; function Prio (Operator : Character) return Natural is begin case Operator is when '+' | '-' => return 1; when '*' | '/' => return 2; when '#' | '(' => return 0; when others => raise Program_Error; end case; end Prio; Syntax_Error : exception; begin -- main program Push (Operator_Stack, '#'); Put ("Enter an expression: "); loop -- Get next non-space character loop Look_Ahead (Operator, Line_End); exit when Line_End or Operator /= ' '; Get (Operator); -- got a space, so skip it end loop; -- Exit main loop at end of line exit when Line_End; -- Process operator or operand if Operator in '0'..'9' then -- it's an operand if Got_Operand then -- can't have an operand Put ("Missing operator"); -- immediately after another exit; end if; Get (Operand); -- read the operand Push (Operand_Stack, Operand); Got_Operand := True; -- record we've got an operand else -- it's not an operand Got_Operand := False; -- so record the fact exit when Operator = '.'; -- exit at end of expr. Get (Operator); -- else read the operator case Operator is -- and apply it when '+' | '-' | '*' | '/' => while Prio(Operator) <= Prio(Top(Operator_Stack)) Apply; end loop; Push (Operator_Stack, Operator); when '(' => -- stack left parenthesis Push (Operator_Stack, Operator); when ')' => -- unwind stack back to '(' while Prio(Top(Operator_Stack)) > Prio('(') loop Apply; end loop; Pop (Operator_Stack, Operator); if Operator /= '(' then Put ("Missing left parenthesis"); raise Syntax_Error; end if; when others => Put ("Invalid operator '"); Put (Operator); Put ("'"); raise Syntax_Error; end case; end if; end loop; -- Apply remaining operators from stack while Prio(Top(Operator_Stack)) > Prio('#') loop Apply; -- unwind stack, apply operations end loop; -- Display result or report error if Top(Operator_Stack) = '#' then Put (Top(Operand_Stack), Width => 1); New_Line; else Put ("Missing right parenthesis"); raise Syntax_Error; end if; exception when Syntax_Error => Put_Line (" -- program terminated."); end Calculator;
The main loop is executed until Look_Ahead reports the end of the line has been reached. If the character in Operator is a digit, an integer is read into Operand and pushed onto the stack and a Boolean variable called Got_Operand will be set to indicate that an operand has just been read. This is used to guard against two operands being entered one after the other; if this happens an error message is displayed and a Syntax_Error is raised. The processing of the operators is as it was earlier except that two extra cases are provided to deal with the left and right parentheses. A left parenthesis is just pushed onto the stack; a right parenthesis applies operators from the operator stack until an operator with a priority of zero is reached. If this isnt a left parenthesis it means that there are too many right parentheses in the expression, so an error message is displayed and a Syntax_Error is raised.
The main loop ends when Look_Ahead reports that the end of the line has been reached. Operators are then applied to their operands until an operator with a priority of zero is reached; if this isnt the # used to prime the stack it must be an unmatched left parenthesis, which means that there is a right parenthesis missing somewhere.
Weve seen how to use the stack package to improve on the calculator design from chapter 3; now its time to return to the stack package itself and look at ways of implementing its body. Since a stack is a collection, we could use an array or a linked list to implement it. Lets consider an array implementation first. Well need an array of items for the stack itself together with a count to tell us how many items there are on the stack. The private section of the package specification might look like this:
package JE.Stacks is -- as before private Max_Items : constant := 100; -- an arbitrary maximum size for stacks type Stack_Array is array (1..Max_Items) of Item_Type; subtype Stack_Pointer is Natural range 0..Max_Items; type Stack_Type is record Value : Stack_Array; Top : Stack_Pointer := 0; end record; end JE.Stacks;
The package has a built-in arbitrary limit of 100 items per stack. The stack pointer (Top) is set to zero by default so that all stacks will automatically start off empty. Pushing an item involves incrementing Top and storing the item at the array position it indicates; popping an item off the stack is the reverse process, i.e. the item at position Top is retrieved and then Top is decremented. The other functions are equally straightforward. Heres the package body:
package body JE.Stacks is procedure Push (Stack : in out Stack_Type; Item : in Item_Type) is begin Stack.Top := Stack.Top + 1; Stack.Value(Stack.Top) := Item; exception when Constraint_Error => raise Stack_Overflow; end Push; procedure Pop (Stack : in out Stack_Type; Item : out Item_Type) is begin Item := Top(Stack); Stack.Top := Stack.Top - 1; end Pop; function Top (Stack : Stack_Type) return Item_Type is begin return Stack.Value(Stack.Top); exception when Constraint_Error => raise Stack_Underflow; end Top; function Size (Stack : Stack_Type) return Natural is begin return Stack.Top; end Size; function Empty (Stack : Stack_Type) return Boolean is begin return Size(Stack) = 0; end Empty; end JE.Stacks;
Note how Pop uses Top to get the value of the topmost stack item, including the necessary checks for stack underflow, so as to avoid code duplication.
A linked list approach is just as simple. Heres what the private part of the specification looks like if we decide to take this approach:
with JE.Lists; package JE.Stacks is -- as before private package Item_Lists is new JE.Lists (Item_Type); type Stack_Type is new Item_Lists.List_Type; end JE.Stacks;
Notice that Stack_Type is effectively just a renaming of Item_Lists.List_Type. However, since Stack_Type was declared as a private type, you cant declare it as a subtype in the private part of the specification in order to effect a renaming; it must be declared as a type, so Ive declared it as a derived type. The only problem with this is that Stack_Type values will need to be explicitly converted to Item_Lists.List_Type values before operations on List_Type values can be applied:
function Size (Stack : Stack_Type) return Natural is begin return Item_Lists.Size (Item_Lists.List_Type(Stack)); end Size;
This is awkward; another approach which leads to more readable code is to declare Stack_Type as a record containing a List_Type component:
with JE.Lists; package JE.Stacks is -- as before private package Item_Lists is new JE.Lists (Item_Type); type Stack_Type is record L : Item_Lists.List_Type; end record; end JE.Stacks;
The Size function above can now be written like this:
function Size (Stack : Stack_Type) return Natural is begin return Item_Lists.Size (Stack.L); end Size;
This is much less complicated; using a record type like this is a trick worth remembering for future reference. Now we can use the operations on lists defined in Lists to implement the package body:
with JE.Lists; package body JE.Stacks is package ILP renames Item_Lists; -- for convenience procedure Push (Stack : in out Stack_Type; Item : in Item_Type) is begin ILP.Insert (ILP.First(Stack.L), Item); exception when Storage_Error => raise Stack_Overflow; end Push; procedure Pop (Stack : in out Stack_Type; Item : out Item_Type) is begin Item := Top(Stack); ILP.Delete (ILP.First(Stack.L)); end Pop; function Top (Stack : Stack_Type) return Item_Type is begin return ILP.Value(ILP.First(Stack.L)); exception when ILP.List_Error => raise Stack_Underflow; end Top; function Size (Stack : Stack_Type) return Natural is begin return ILP.Size(Stack.L); end Size; function Empty (Stack : Stack_Type) return Boolean is begin return Size(Stack) = 0; end Empty; end JE.Stacks;
The problem with the approaches above is that if we decide to change the implementation from an array to a linked list or vice versa, the package specification needs changing. This will mean recompiling any existing code that uses the stack package, which may be very inconvenient if its used in library units totalling hundreds of thousands of lines. A better approach is to try to hide all the implementation details inside the package body, so that any changes affect only the body and not the specification. That way we have to recompile the body, but since the specification wont have changed the client units wont need to be recompiled. The only thing that will need doing to client code is relinking it with the new body which will be much quicker than recompiling it.
How can we achieve this state of ultimate privacy? The answer is to use one of the features of access types that was mentioned when I first started talking about them; if you tell the compiler the name of a type in an incomplete declaration you can define an access type for it without the compiler needing to know anything more about the type. All access values are the same size, no matter what type of thing they point to, so the compiler can allocate memory for access variables without needing to know any details about what they point to. What we end up with is an opaque type whose name is mentioned but whose definition can be hidden inside the package body:
package JE.Stacks is -- as before private type Stack_Item; -- defined in package body type Stack_Type is access Stack_Item; end JE.Stacks;
The package body gets a little bit more complicated since a Stack_Type variable will start off set to null, so well need to create a Stack_Item variable with new the first time an item is pushed onto it. Well also need to check for null in all the packages procedures and functions. Heres how its done using an array:
package body JE.Stacks is Max_Items : constant := 100; -- arbitrary maximum stack size type Stack_Array is array (1..Max_Items) of Item_Type; subtype Stack_Pointer is Natural range 0..Max_Items; -- Completion of opaque type declaration from package specification type Stack_Item is record Value : Stack_Array; Top : Stack_Pointer := 0; end record; procedure Push (Stack : in out Stack_Type; Item : in Item_Type) is begin if Stack = null then Stack := new Stack_Item; end if; Stack.Top := Stack.Top + 1; Stack.Value(Stack.Top) := Item; exception when Storage_Error | Constraint_Error => raise Stack_Overflow; end Push; procedure Pop (Stack : in out Stack_Type; Item : out Item_Type) is begin Item := Top(Stack); Stack.Top := Stack.Top - 1; end Pop; function Top (Stack : Stack_Type) return Item_Type is begin return Stack.Value(Stack.Top); exception when Constraint_Error => raise Stack_Underflow; end Top; function Size (Stack : Stack_Type) return Natural is begin if Stack = null then return 0; else return Stack.Top; end if; end Size; function Empty (Stack : Stack_Type) return Boolean is begin return Size(Stack) = 0; end Empty; end JE.Stacks;
Push will allocate a new stack if its null; if we run out of memory to allocate the stack, a Storage_Error exception will be raised. Like Constraint_Error, this is simply reported back to the caller as a stack overflow. Pop and Top dont need changing; any attempt to access the top of a stack which hasnt been allocated (i.e. which is still null) will raise Constraint_Error, which will then be turned into a Stack_Underflow exception by Top. Size and Empty are modified so that if you use either of them with a stack that hasnt been allocated theyll behave as if the stack exists but is empty.
Changing the package to use a linked list is fairly straightforward:
with JE.Lists; package body JE.Stacks is package Lists is new JE.Lists (Item_Type); type Stack_Item is record L : Lists.List_Type; end record; procedure Push (Stack : in out Stack_Type; Item : in Item_Type) is begin if Stack = null then Stack := new Stack_Item; end if; Lists.Insert (Lists.First(Stack.L), Item); exception when Storage_Error => raise Stack_Overflow; end Push; procedure Pop (Stack : in out Stack_Type; Item : out Item_Type) is begin Item := Top(Stack); Lists.Delete (Lists.First(Stack.L)); end Pop; function Top (Stack : Stack_Type) return Item_Type is begin return Lists.Value(Lists.First(Stack.L)); exception when Lists.List_Error => raise Stack_Underflow; end Top; function Size (Stack : Stack_Type) return Natural is begin if Stack = null then return 0; else return Lists.Size (Stack.L); end if; end Size; function Empty (Stack : Stack_Type) return Boolean is begin return Size(Stack) = 0; end Empty; end JE.Stacks;
This reveals another advantage of burying the list in a record rather than using a derived type; if a derived type were used, you would need to write things like this in order to use Lists operations on a Stack_Type value:
return Lists.Value(Lists.First(Lists.List_Type(Stack.all))); -- instead of "return Lists.Value(Lists.First(Stack.L));"
Since Stack_Type is an access type, the value that a Stack_Type object called Stack points to would have to be be accessed using Stack.all; this would then need to be converted to List_Type before any List_Type operations could be performed on it.
Trying to detect and deal with all the possible errors that can occur in an arithmetic expression is really quite difficult. An alternative way of dealing with expressions known as recursive descent parsing can make life quite a bit easier. This is based on having a formal definition of the syntax of an expression. We can define an expression as a sequence of terms separated by adding operators. A term can then be defined as a sequence of primaries separated by multiplying operators, and a primary as either a number or an expression enclosed in parentheses. This is usually written using a formal notation similar to this:
Expression = Term { AddOp Term } Term = Primary { MulOp Primary } Primary = Number | ( Expression ) AddOp = + | - MulOp = * | /
Here the curly brackets { ... } indicate that what they enclose can be repeated any number of times (including zero times) and the vertical bar | means or. The first rule is equivalent to an infinitely long rule that looks like this:
Expression = Term | Term AddOp Term | Term AddOp Term AddOp Term | Term AddOp Term AddOp Term AddOp Term ... and so on
Primary is defined as being a number or an expression enclosed in parentheses. This seems slightly odd when you think about it; Expression is defined in terms of Term which is defined in terms of Primary which is defined in terms of Expression which is defined in terms of ... It seems completely circular, but actually it makes perfect sense. Look at how 2*(3+4) is analysed using these rules:
An apparently circular definition like this is known as a recursive definition. It may seem like a bit of a curiosity, but recursion turns up in all sorts of problems. Want to sort an array? Split it in two and sort each half, and then merge the sorted halves. This may sound silly, but its the basis of a well-known technique called merge sorting which outperforms all of the obvious ways of sorting that generally spring to peoples minds (e.g. the shuffle sort described in chapter 6). Want to generate all possible permutations of a sequence? Take each item in turn as the start of a permutation and append all possible permutations of the items that are left, so that the possible permutations of [1,2,3] are generated by 1 followed by all permutations of [2,3], 2 followed by all permutations of [1,3], and 3 followed by all permutations of [1,2]; this gives you [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] and [3,2,1].
All recursion has to stop somewhere; the merge sort stops recursing when the array to be sorted contains a single item and the permutation algorithm stops when you have to generate all possible permutations of a single item. In the case of parsing an expression recursion only occurs when you see a left parenthesis, so its impossible to get stuck in an infinite loop. In programming terms, recursion is where a function or procedure calls itself either directly or indirectly. Heres an example of a recursive function to calculate factorials: factorial N is the product of 1 * 2 * 3 * ... * N (and as a special case, factorial 0 is 1), which means that factorial N is N * factorial (N 1) for all N > 0, and 1 when N = 0:
function Factorial (N : Natural) return Positive is begin if N = 0 then return 1; else return N * Factorial(N-1); end if; end Factorial;
The recursion always stops because N gets smaller every time and eventually gets down to 0 which is where the recursion ends.
Writing a recursive descent parser involves converting the syntax rules given earlier into Ada procedures. The first thing we need is a function Next_Character which uses Look_Ahead to find out what the next non-space character is without reading it:
function Next_Character return Character is Ch : Character; EOL : Boolean; begin loop Look_Ahead (Ch, EOL); if EOL then return '.'; elsif Ch /= ' ' return Ch; else Get (Ch); end if; end loop; end Next_Character;
This produces a full stop as its result when it reaches the end of the current line. The next step is to implement a function called Expression:
function Expression return Integer is Value : Integer; Operator : Character; begin Value := Term; loop Operator := Next_Character; exit when Operator /= '+' and Operator /= '-'; Get (Operator); if Operator = '+' then Value := Value + Term; else Value := Value - Term; end if; end loop; return Value; end Expression;
This gets a Term (using another function well have to implement in a moment) and then sits in a loop accumulating more Terms as long as it sees an adding operator. Term is very similar to Expression:
function Term return Integer is Value : Integer; Operator : Character; begin Value := Primary; loop Operator := Next_Character; exit when Operator /= '*' and Operator /= '/'; Get (Operator); if Operator = '*' then Value := Value * Primary; else Value := Value / Primary; end if; end loop; return Value; end Term;
This is defined in terms of Primary, which looks like this:
function Primary return Integer is Value : Integer; Ch : Character; begin Ch := Next_Character; case Ch is when '0'..'9' => Get (Value); when '(' => Get (Ch); Value := Expression; if Next_Character /= ')' then raise Syntax_Error; else Get (Ch); end if; when others => raise Syntax_Error; end case; return Value; end Primary;
A primary must be either a number or a parenthesised expression, so the case statement in this function checks for a digit or a left parenthesis as the valid characters which can start an operand. If the character is anything other than a digit or left parenthesis, a Syntax_Error exception gets raised. This deals with errors arising from missing operands, as in * 2 or 1 + * 2 where Primary will see an operator rather than a digit or left parenthesis.
If the character is a digit, an integer is read from the input and returned as the value of the function; if its a left parenthesis, an expression is read and its value used as the functions return value. It is, however, necessary to check that a parenthesised expression ends with a right parenthesis, so Next_Character is used after reading the expression to check for this. If the next character is a right parenthesis, it is simply read in and ignored; if not, a Syntax_Error exception is raised. This deals with errors arising from missing right parentheses.
A main program using these functions simply needs to call Expression and then check that the next character is a full stop. If it isnt, theres a syntax error arising from a missing left parenthesis, a missing operator or an illegal character. If the character is a right parenthesis, this indicates a missing left parenthesis, e.g. 1 + 2); if its a digit theres a missing operator, e.g. 1 2, and if its anything else its an illegal character, e.g. 1 & 2. The functions above can be embedded in a program together with the exception Syntax_Error; heres what the main program might look like:
with Ada.Text_IO, Ada.Integer_Text_IO, JE.Parser; use Ada.Text_IO, Ada.Integer_Text_IO; procedure Evaluate is Syntax_Error : exception; function Next_Character return Character is separate; function Expression return Integer is separate; function Term return Integer is separate; function Primary return Integer is separate; Value : Integer; begin Put ("Enter an expression: "); Value := Expression; if Next_Character /= '.' then raise Syntax_Error; end if; Put (Value); New_Line; exception when Syntax_Error => Put_Line ("Syntax error!"); end Evaluate;
The functions themselves will need modifying to include separate clauses at the beginning, like this:
separate (Evaluate) function Expression return Integer is ... end Expression;
13.1 | Using a doubly linked list for a stack is overkill since items are only ever added to or removed from the front of the list. Modify the stack package to use a simple singly linked list which is manipulated directly by the operations in the package body, and test it using the calculator program. |
13.2 | Write a program to generate all possible anagrams of a word using the recursive method described in this chapter. If you want to get a list in alphabetical order, sort the characters making up the word into ascending order before generating the anagrams. To avoid generating duplicates, dont use the same letter twice. For example, to generate all unique anagrams of apple in alphabetical order, sort the letters to give aelpp, then display a followed by all anagrams of elpp, e followed by all anagrams of alpp, l followed by all anagrams of aepp, p followed by all anagrams of aelp, but dont do it again for the second p. |
13.3 | The double-ended queue (or deque) is yet another data structure that is useful in many situations. A deque is a sequence of items which allows you to add new items to either end or remove items from either end. Produce a deque package which uses an opaque type to represent a deque and write a test program to allow you to exercise the package. Model your package on the stack package shown in this chapter. |
13.4 | The data structure described in exercise 11.2 is known as a binary tree. It is a fundamentally recursive structure; the node at the root of the tree points to two other nodes which can be considered to be the roots of two smaller subtrees with the same structure. Modify your solution to exercise 11.2 using a recursive algorithm for searching the tree. |
![]() Previous |
![]() Contents |
![]() Next |
This file is part of
Ada 95: The Craft of Object-Oriented Programming
by John English.
Copyright © John
English 2000. All rights reserved.
Permission is given to redistribute this work for non-profit educational
use only, provided that all the constituent files are distributed without
change.