Programmiersprachen – Programming Languages

LVA 185.208, VU, 3 ECTS, 2015 S

5 12+applies the operator

+to the arguments 5 and 12, giving 17 as result. White space between 5 and 12 is necessary to separate the integers from each other.

Post-fix expressions are evaluated using a stack:
Arguments are simply pushed onto the stack, operators take arguments from the stack and push results onto the stack.
For example, 1 2 3 4+*-

is evaluated to 13:
First, the four numbers are pushed onto the stack, then the evaluation of +

takes 4 and 3 from the top of the stack and pushes the result 7 onto the stack, the evaluation of *

takes 7 and 2 from the stack and pushes 14 onto the stack, and finally -

takes 14 and 1 from the stack and pushes 13 onto the stack.

Data enclosed in quotes build blocks.
Operators in blocks are not evaluated immediately.
However, a block is evaluated when applying the operator a

to it.
For example, '2*'

is a block.
When evaluating 4 3'2*'a+

, first 4, 3 and '2*'

are pushed onto the stack, then a

takes the block from the stack and causes its contents to be evaluated by pushing 2 onto the stack and applying *

to 2 and 3, and finally +

adds 4 to 6.
We can regard '2*'a

as an operator that doubles the integer on top of the stack.

- Input stream:
- A sequential stream of integers, blocks and operators typed into the keyboard (or added during execution, see below). Every character that is not part of an integer or block is regarded to be an operator.
- Output stream:
- Integers and blocks written to the output stream are displayed on a screen. The contents of blocks is displayed without surrounding quotes (so that blocks can be used in a similar way as strings), and spaces are automatically inserted between the written elements.
- Data stack:
- This is the stack holding data when evaluating expressions in post-fix notation.

For simplification there can be (reasonable) limits for the sizes of integers, blocks, the data stack and the size of the screen connected to the output stream.

- Integer or block:
- When occurring as first element of the input stream, an integer or block is simply taken from the input stream and pushed onto the data stack.
- Arithmetic operator, comparison operator or logical operator (
+

,-

,*

,/

,%

,&

,|

,=

,<

,>

): - These binary operators have the usual semantics, where
%

computes the rest of a division,&

is the logical AND and|

is the logical OR. Each of these operators takes two integers from the data stack and pushes an integer as result onto the data stack. The integer 0 corresponds tofalse

and 1 totrue

. An error is reported if any of the two topmost elements on the data stack is no integer or an argument of&

or|

differs from 0 and 1. The comparison operator=

is an exception: If=

is applied to two equal blocks or two equal integers, then the result equals 1, otherwise the result is 0. The ordering of arguments has to be considered for non-associative operations:2 4-

and2 4/

and4 2%

have 2 as result, and2 4>

and4 2<

give 1 (true

). An error shall be reported when executing/

or%

if the second element from the top of the data stack equals 0. - Negation
~

: - This unary operator changes the sign of an integer on the data stack. An error is reported if its argument is not an integer.
- Copy
c

- replaces the top element
`n`of the data stack with a copy of the`n`th element on the data stack (counted from the top of the stack). An error is reported if`n`is not a positive number or the stack does not contain a sufficient number of elements. - Delete
d

- takes the top element
`n`from the data stack and additionally removes the`n`th element from the data stack (counted from the top of the stack). An error is reported if`n`is not a positive number or the stack does not contain a sufficient number of elements. - Apply
a

: - If the single argument is a block, then the block is taken from the data stack and its content is inserted into the input stream to be executed next; the content of the block is divided into elements of the input stream in the same way as if typed on the keyboard. Otherwise this operation has no effect.
- Read integer
i

: - The whole execution is suspended until a complete integer (terminated by any character not being part of an integer) has been typed into the keyboard. This integer is directly pushed onto the data stack. It is not written to the input stream. An error occurs if something else than an integer is typed into the keyboard.
- Read block
b

: - The whole execution is suspended until a line has been typed into the keyboard. The line content is pushed as a new block onto the data stack. Nothing is written to the input stream.
- Write
w

- takes an argument from the data stack and writes it into the output stream.
- Exit
x

- stops the execution of the calculator.
- White space
- does nothing.
- Any other character in the input stream
- causes an error.

If an error occurs, the calculator simulator shall simply stop its execution and report an error message.

^, the top of the stack adjacent to

^) and its input stream (to the right of

^, the first element adjacent to

^). Arrows between state specifications show how the states change by executing operations.

The first example shows how to deal with conditional execution:
On the data stack we expect 0 (false) or 1 (true).
Depending on this value we want to execute the one or the other block.
First we push the block for the false-path '9~'

onto the stack, then the one for the true-path '9'

, and finally we execute '3c4d1+da'

, the code for conditional execution.
The steps show what happens if previously 0 was on the data stack.

0 ^ '9~''9''3c4d1+da'a --> 0'9~' ^ '9''3c4d1+da'a --> 0'9~''9' ^ '3c4d1+da'a --> 0'9~''9''3c4d1+da' ^ a --> 0'9~''9' ^ 3c4d1+da --> 0'9~''9'3 ^ c4d1+da --> 0'9~''9'0 ^ 4d1+da --> 0'9~''9'0 4 ^ d1+da --> '9~''9'0 ^ 1+da --> '9~''9'0 1 ^ +da --> '9~''9'1 ^ da --> '9~' ^ a --> ^ 9~ --> 9 ^ ~ --> -9 ^

The next example shows recursion in the computation of 3 factorial. For simplification we use A as shorthand for '2c1 3c-1c1=3c''Ca2d*' and C as shorthand for '3c4d1+da' (see above). Please note that the only purpose of A and C is a simplification to improve readability. In the calculator the blocks occur instead of their shorthands.

3 ^ A2c3d2ca2d --> 3A ^ 2c3d2ca2d --> 3A2 ^ c3d2ca2d --> 3A3 ^ 3d2ca2d --> 3A3 3 ^ d2ca2d --> A3 ^ 2ca2d --> A3 2 ^ ca2d --> A3A ^ a2d --> A3 ^ 2c1 3c-1c1=3c''Ca2d*2d --> A3 2 ^ c1 3c-1c1=3c''Ca2d*2d --> A3A ^ 1 3c-1c1=3c''Ca2d*2d --> A3A1 ^ 3c-1c1=3c''Ca2d*2d --> A3A1 3 ^ c-1c1=3c''Ca2d*2d --> A3A1 3 ^ -1c1=3c''Ca2d*2d --> A3A2 ^ 1c1=3c''Ca2d*2d --> A3A2 1 ^ c1=3c''Ca2d*2d --> A3A2 2 ^ 1=3c''Ca2d*2d --> A3A2 2 1 ^ =3c''Ca2d*2d --> A3A2 0 ^ 3c''Ca2d*2d --> A3A2 0 3 ^ c''Ca2d*2d --> A3A2 0A ^ ''Ca2d*2d --> A3A2 0A'' ^ Ca2d*2d --> A3A2 0A''C ^ a2d*2d ... --> A3A2A ^ a2d*2d --> A3A2 ^ 2c1 3c-1c1=3c''Ca2d*2d*2d --> A3A2 2 ^ c1 3c-1c1=3c''Ca2d*2d*2d --> A3A2A ^ 1 3c-1c1=3c''Ca2d*2d*2d --> A3A2A1 ^ 3c-1c1=3c''Ca2d*2d*2d --> A3A2A1 3 ^ c-1c1=3c''Ca2d*2d*2d --> A3A2A1 2 ^ -1c1=3c''Ca2d*2d*2d --> A3A2A1 ^ 1c1=3c''Ca2d*2d*2d --> A3A2A1 1 ^ c1=3c''Ca2d*2d*2d --> A3A2A1 1 ^ 1=3c''Ca2d*2d*2d --> A3A2A1 1 1 ^ =3c''Ca2d*2d*2d --> A3A2A1 1 ^ 3c''Ca2d*2d*2d --> A3A2A1 1 3 ^ c''Ca2d*2d*2d --> A3A2A1 1A ^ ''Ca2d*2d*2d --> A3A2A1 1A'' ^ Ca2d*2d*2d --> A3A2A1 1A''C ^ a2d*2d*2d ... --> A3A2A1'' ^ a2d*2d*2d --> A3A2A1 ^ 2d*2d*2d --> A3A2A1 2 ^ d*2d*2d --> A3A2 1 ^ *2d*2d --> A3A2 ^ 2d*2d --> A3A2 2 ^ d*2d --> A3 2 ^ *2d --> A6 ^ 2d --> A6 2 ^ d --> 6 ^