Conditions for underflow and overflow of an arithmetic stack
Dave Goodwin · The Computer Journal · 1977
The behaviour of an arithmetic stack is formally described as the loading of an arbitrary string of a context free language symbol by symbol on to a stack. Instances of a special symbol in the string being loaded invoke an operation which removes the top cell of the stack in some undefined way. Necessary and sufficient conditions for stack length boundedness are stated and proved. One application of the results concerns the choice between compile time and run time checks for underflow and overflow. Another concerns the testing for applicability of a certain algorithm for inverting Metcalfe-Reeves translators.