Universität Ulm, Fakultät für Mathematik und Wirtschaftswissenschaften, SAI

# Lösung zu Blatt 3 --- Allgemeine Informatik II (WS 1999)

## 4. Rechnen

```MODULE Calculator;

(* New:
Start = "!" Expression .
Start = Variable "=" Expression .
Factor = Variable .
S = Start
*)

IMPORT ASCII, Read, Streams, Strings, Write;

TYPE
Attribute = INTEGER;
VAR
expr: Streams.Stream;
at: Attribute;
vars: ARRAY 26 OF INTEGER;
CONST
pigsFly = FALSE;

PROCEDURE Parse(s: Streams.Stream;
VAR at: Attribute) : BOOLEAN;
(* parse input and return TRUE in case of success *)

VAR
ch: CHAR; (* current input character, 0X in case of eof *)
lastpos: INTEGER; (* Last position of a variable *)
eof: BOOLEAN; (* eof seen yet? *)

CONST
(* terminal symbols *)
plusSY = 0;
minusSY = 1;
multiplySY = 2;
divideSY = 3;
lparenSY = 4;
rparenSY = 5;
constantSY = 6;
eofSY = 7;
errorSY = 8;
printSY = 9;
variableSY = 10;
assignSY = 11;
TYPE
Symbol = SHORTINT; (* plusSY .. variableSY *)
VAR
sy: Symbol; (* current input token *)
const: INTEGER; (* set if sy = constantSY | variableSy *)

PROCEDURE NextCh;
BEGIN
IF eof OR ~Streams.ReadByte(s, ch) THEN
ch := 0X; eof := TRUE;
END;
END NextCh;

PROCEDURE GetSy;
BEGIN
(* skip white space *)
WHILE (ch = " ") OR (ch = ASCII.tab) OR (ch = ASCII.nl) DO
NextCh;
END;
CASE ch OF
| "+":   sy := plusSY; NextCh;
| "-":   sy := minusSY; NextCh;
| "*":   sy := multiplySY; NextCh;
| "/":   sy := divideSY; NextCh;
| "(":   sy := lparenSY; NextCh;
| ")":   sy := rparenSY; NextCh;
| "0".."9":
const := ORD(ch) - ORD("0");
NextCh;
WHILE (ch >= "0") & (ch <= "9") DO
const := const * 10 + ORD(ch) - ORD("0");
NextCh;
END;
sy := constantSY;
| "a".."z":
lastpos := ORD(ch) - ORD("a");
const := vars[lastpos];
NextCh;
sy := variableSY;
| "!":   sy := printSY; NextCh;
| "=":   sy := assignSY; NextCh;
| 0X:    sy := eofSY;
ELSE     sy := errorSY;
END;
END GetSy;

PROCEDURE Constant(VAR at: Attribute) : BOOLEAN;
(* Constant = "0" | "1" | ... | "9" . *)
BEGIN
IF sy = constantSY THEN
at := const;
GetSy;
RETURN TRUE
ELSE
RETURN FALSE
END;
END Constant;

PROCEDURE Variable(VAR at: Attribute): BOOLEAN;
(* Variable = "a" | ... | "z" . *)
BEGIN
IF sy = variableSY THEN
at := const;
GetSy;
RETURN TRUE
ELSE
RETURN FALSE
END;
END Variable;

PROCEDURE ^ Expression(VAR at: Attribute) : BOOLEAN;

PROCEDURE Factor(VAR at: Attribute) : BOOLEAN;
(* Factor = "(" Expression ")" | ("+" | "-") Factor | Constant | Variable . *)
VAR
minus: BOOLEAN;
BEGIN
IF sy = lparenSY THEN
GetSy;
IF ~Expression(at) OR (sy # rparenSY) THEN
RETURN FALSE
END;
GetSy;
RETURN TRUE
ELSIF (sy = plusSY) OR (sy = minusSY) THEN
minus := sy = minusSY;
GetSy;
IF Factor(at) THEN
IF minus THEN
at := - at;
END;
RETURN TRUE
ELSE
RETURN FALSE
END;
ELSIF sy = variableSY THEN
RETURN Variable(at)
ELSE
RETURN Constant(at)
END;
END Factor;

PROCEDURE Term(VAR at: Attribute) : BOOLEAN;
(* Term = Factor { ("*" | "/") Factor } . *)
VAR
leftop, rightop: Attribute;
opsy: Symbol;
BEGIN
IF ~Factor(leftop) THEN RETURN FALSE END;
WHILE (sy = multiplySY) OR (sy = divideSY) DO
opsy := sy;
GetSy; (* skip operator *)
IF ~Factor(rightop) THEN RETURN FALSE END;
CASE opsy OF
| multiplySY:  leftop := leftop * rightop;
| divideSY:    leftop := leftop DIV rightop;
END;
END;
at := leftop;
RETURN TRUE
END Term;

PROCEDURE Expression(VAR at: Attribute) : BOOLEAN;
(* Expression = Term { ("+" | "-") Term } . *)
VAR
leftop, rightop: Attribute;
opsy: Symbol;
BEGIN
IF ~Term(leftop) THEN RETURN FALSE END;
WHILE (sy = plusSY) OR (sy = minusSY) DO
opsy := sy;
GetSy; (* skip operator *)
IF ~Term(rightop) THEN RETURN FALSE END;
CASE opsy OF
| plusSY:   leftop := leftop + rightop;
| minusSY:  leftop := leftop - rightop;
END;
END;
at := leftop;
RETURN TRUE
END Expression;

PROCEDURE Start(VAR at: Attribute) : BOOLEAN;
VAR
pos: INTEGER;
BEGIN
IF sy = printSY THEN
GetSy;
IF Expression(at) & (sy = eofSY) THEN
Write.Int(at, 1); Write.Ln;
RETURN TRUE
ELSE
RETURN FALSE
END;
ELSE
IF ~(sy = variableSY) THEN RETURN FALSE END;
pos := lastpos;
GetSy;
IF ~(sy = assignSY) THEN RETURN FALSE END;
GetSy;
IF Expression(at) THEN
vars[pos] := at;
RETURN TRUE
ELSE
RETURN FALSE
END;
END;

END Start;

BEGIN (* Parse *)
eof := FALSE; NextCh; GetSy;
RETURN Start(at) & (sy = eofSY)
END Parse;

VAR
s: Streams.Stream;
line: ARRAY 80 OF CHAR;
BEGIN
REPEAT
IF Streams.stdin.count = 0 THEN
RETURN
END;
Strings.Open(s, line);
IF ~Parse(s, at) THEN
Write.Line("Not an expression!");
END;
Streams.Release(s);
UNTIL pigsFly;