Informatik-Treff: Abiturklausur (1997 LK 2. Klausur) 

Aufgabe 1: Aspekte des Compilerbaus, Verwaltung von Syntaxbäumen, Interpretieren von Syntaxbäumen

Im Unterricht wurden algebraische Terme (Infix-Schreibweise) auf syntaktische Korrektheit überprüft und in Postfix-Zwischencode übersetzt. Die Terrne werden im folgenden auf Zeichenketten (string) gespeichert. Die Operatoren sind + , - , * , / , die Operanden seien einziffrige Zahlen. Infix- und Postfixdarstellungen werden durch ";" abgeschlossen.

a) Übersetze folgende Terme "per Hand" in Postfix-Codierung:

• 2 - 3 * ( 5 + 6 ) ;
• 4 + 2 - 3 * 1 * 7 / 5 ;

b) Übersetze rückwärts in Infix-Notation. Achte auf richtige Klammerung:

• 2 8 - 2 9 * + ;
• 2 9 3 8 * - 5 6 + / + ;

c) Gegeben ist nun ein Postfix-Zwischencode. Mit Hilfe eines Kellers, in dem Teilbäume ( = Zeiger auf deren Wurzeln) verwaltet werden, soll der zugehörige Syntax-Baum erzeugt werden. Zeichne den Syntaxbaum "per Hand", der zu 3 6 4 5 * - - 5 + ; gehört.
 

type baum = ^knoten;
     knoten = record
                info: char;
                links, rechts: baum
              end;

var b,c: baum; 

type keller = ^kelem;
     kelem = record
               inhalt: baum;
               next: keller
             end;

var k: keller;

d) Gib eine Folge von Pascal-Befehlen an, die folgenden Baum B erzeugt:

e) Erläutere, wie man mit oben stehendem Keller einen Postfix-Zwischencode in einen Syntaxbaurn umwandeln kann. Hinweis:

Alter Keller:

Aktuelles Zeichen: - (minus)

Neuer Keller:

f) Schreibe eine function baumbau (a:s tring): baum , die zu einer Zeichenkette a (mit dem postfix-Zwischencode eines Funktionsterms) den zugehörigen Baum liefert.

g) Schreibe eine rekursive Pascal-Funktionsprozedur evaluate (b: baum): real , die einem Syntaxbaum die Zahl zuordnet, die bei seiner Auswertung herauskommt (im obigen Beispiel 2 * 4 - ( 1 + 3 ) = 4 ) . Achtung, dabei sind die Zeichen 0 ... 9 in Zahlen zu verwandeln.

h) Wir betrachten nun die Postfix-Terme als formale Sprache. Sie wird z.B. erzeugt durch:

U -> S ;
S -> S S O | D
O -> + | - | * | /
D -> 0 .. 9

Welchen Typ hat die oben stehende Grammatik? Zeichne den Ableitungsbaum für den Termn 3 6 4 5 * - - 5 + ; . Warum ist diese Grammatik für den Bau eines Parsers ungeeignet?
 

Aufgabe 2: Anwendung von Automaten zur Robotersteuerung

Ein Wagen mit zwei Photowiderständen als "Augen" soll in der Ebene hinter einer frei beweglichen Lampe herfahren und stehen bleiben, wenn er der Lampe zu nahe kommt. Entfernt sich die Lampe wieder, setzt der Wagen seine Suchfahrt fort. Die Widerstände l und r (vorne links und rechts am Wagen) können über die "function resistance (seite: char): integer" abgefragt werden. Beispiel  x : = resistance('1') . Die Ergebnisse liegen zwischen 1 und 100. Die Lampe befindet sich auf der Seite des Wagens, die den kleineren Widerstand liefert, also stärker beleuchtet wird.
 

a) Schreibe eine function signal: integer, die die beiden Widerstandswerte über resistance( ) abfragt und folgende Ausgabe erzeugt:

• 0, falls die Lampen sehr nahe am Wagen ist (mindestens ein Widerstandstandswert kleiner als 5)
• 1, falls die Lampe links von der Fahrtrichtung ist
• 2, falls die Lampe genau in Fahrtrichtung zu finden ist
• 3, falls die Lampe rechts von der Fahrtrichtung steht.

b) Deute die Signalfolge 00 ... 022 ... 233 ... 322 ... 200. Was könnte mit Lampe und Wagen geschehen sein? Gib zwei Signalfolgen an, die bei vernünftiger (und langsamer) Bewegung von Lampe und Wagen nicht auftreten können. Kommentiere.

c) Konstruiere das Netz eines Automaten, das alle Signalfolgen akzeptiert, die im Zusammenhang mit unserem Problem auftreten können. Du kannst auf einen gesonderten Fehlerzustand aus Gründen der Übersichtlichkeit verzichten. Die Zustände sollen durch ganze Zahlen bezeichnet werden.

d) Die Prozedur, die den Wagen steuert, könnte wie folgt aussehen:

procedure wagensteuerung;
var state, signal: integer;
begin
  state := 0;
  repeat
    state := uebergang(state,signal)
    move_a_little(state)
  until keypressed
end;

Schreibe die function uebergang (state,signal: integer): integer , die sich aus Deiner Lösung von c) ergibt. Wie würde sich procedure move_a_little(signal) gestalten, wenn man die Vorderräder der Wagen mit zwei Schrittmotoren und der procedure stepmotor(seite: char) unabhängig voneinander steuern können?

Bsp.: stepmotor('1') bewegt das linke Rad ein wenig nach vorne.

e) In das Steuerprogramm des Wagens soll ein Zähler eingebaut werden, der zählt, wie oft das Muster 11 ... 122 ... 233 ... 3 vor den "Augen" des Wagens abgelaufen ist (das Licht also von links nach rechts gewandert ist). Entwirf das Netz eines weiteren Automaten, der in der Folge der durch SIGNAL gelieferten Eingabezeichenfolge nach diesem Muster sucht. (Kein Programm verlangt).
 

Aufgabe 3: Technische Informatik - Schaltwerke

a) In Turbo-Pascal kann der Datentyp Shortint nur Werte zwischen -128 und +127 annehmen. Erläutere, warum das so ist und erkläre

• die Speicherung negativer Zahlen,
• die Addition und
• die Subtraktion

an den Beispielen a = 39, b = 27 .

b) Die Skizze stellt eine 4-Bit-Schieberegister dar, aufgebaut aus JK-Flipflops. Gib die Schaltwerttabelle eines JK-Flipflops an und erläutere damit die Funktionsweise des Schieberegisters.
 

c) Gib die Schalttabelle und die disjunktive Normalforrn für die Schaltterme eines Volladdierers an.

d) Minimiere die Schaltterme des Volladdierers sowohl mit Hilfe der Gesetze der booleschen Algebra als auch mittels Karnaugh-Diagrammen.

e) Zeichne das Schaltnetz eines Volladdierers.

f) Erläutere, wie sich die Schaltungen ausschließlich aus NOR-Gattem aufbauen lassen.

g) Entwickle aus Schieberegistern und anderen Bauteilen ein serielles Addierwerk für 4-Bit-Dualzahlen.