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;

   PROCEDURE ReadInput();
      VAR
	 s: Streams.Stream;
	 line: ARRAY 80 OF CHAR;
   BEGIN
      REPEAT
	 Read.Line(line);
	 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;
   END ReadInput;

BEGIN
   ReadInput();
END Calculator.