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.
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.
+,
-,
*,
/,
%,
&,
|,
=,
<,
>):
%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 to
falseand 1 to
true. 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-and
2 4/and
4 2%have 2 as result, and
2 4>and
4 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.
~:
c
d
a:
i:
b:
w
x
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 ^