Fachrat Informatik - Forum

Moin,

1) Auf S. 16: Die alphas sind "semantische Aktionen", also Codefragmente, die an der entsprechenden Stelle vom Parserprogramm ausgeführt werden sollen. Die Reihenfolge ist dabei wichtig.

2) Eine Grammatik ist S-attributiert, wenn sie nur synthetische Attribute hat (Skript S.7). Gut hieran ist, dass sie mit zwei Stacks leicht bottom-up zu parsen ist. L-attributiert hatte dagegen den Vorteil, dass sie leicht top-down zu parsen ist. Jede S-Grammatik ist eine L-Grammatik. Gut zu wissen ist noch, dass LL(1)-Umformungen einer S-Grammatik wie das Entfernen von Linksrekursionen sie höchstens so "schlecht" machen, dass sie L-attributiert wird, d.h. die Fähigkeit top-down zu parsen geht dabei nicht kaputt.

3) Denke ich auch.

4) Innere Blöcke "sehen" Variablen von äußeren Blöcken, das gilt auch für die Rümpfe von Prozeduren. Die dynamischen Links verketten aber den Aufrufstapel - und weil der nichts damit zu tun hat, welcher Block lexikalisch um eine Prozedurdefinition herumliegt, braucht man die statischen Links.

Mal eine andere nicht inhaltliche Frage... Da im ModKat "Frequenz: ungeregelmäßig" steht... hat denn jemand Erfahrungen oder Wissen darüber, wann die Veranstaltung ggf. das nächste Mal angeboten wird?

Da Parchmann im Ruhestand ist, nur noch (bisher) eine Veranstaltung pro Jahr macht und er anscheinend eher sein Angebot an Vorlesungen möglichst vielfältig durchgehen möchte ist es fraglich, ob die Vorlesung (in absehbarer Zeit) überhaupt noch angeboten wird. Andererseits ist Parchmann wohl immer offen für Vorschläge, insofern ists auch nicht ganz auszuschließen. Die Prüfung muss meines Wissens aber auf jeden Fall im kommenden Semester (Sommer) nochmal angeboten werden/wird angeboten.

Gruß,
Anselm

Zur S-Attributierung: Normalerweise sollte angegeben werden, welche Attribute synthetisch und welche inherit sind. Dann ists natürlich einfach zu beantworten. Allerdings kann mans auch anhand der Berechnungsvorschriften ablesen:
In diesem Fall berechnet sich val jeweils aus Attributen der rechten Seiten und ist somit synthetisch. Da es außerdem anscheinend das einzige auftretende Attribut ist, ist die Grammatik wohl S-attributiert. Aber wie gesagt: Eigentlich müsste eingehend definiert werden, welche Attribute verwendet werden und damit wäre es direkt klar. Denn formal kann man ja auch noch Attribute definieren, die dann aber nirgends berechnet werden und würde damit zwar unter Umständen formal gesehen keine S-Attributierung haben, weil inherite Attribute auftreten, aber diese werden praktisch gar nicht verwendet.

Die Reihenfolge der Alphas ist im Allgemeinen wichtig, weil es beliebige Programmstücke mit Seiteneffekten sein können. Beispielsweise legt das erste Alpha einen neuen Variablennamen in der Symboltabelle ab, und das zweite sucht dann den Eintrag und ergänzt noch den Typ.

Ich hänge mich hier mal dran:

Auf Seite 104 steht als letzter Satz, dass die Knoten 4,5,6,7 keine Schleife bilden, da die Kopf-Bedingung verletzt ist. Wieso bzw. woran sieht man das?

4 ist nicht der einzige Eintrittspunkt. Man kann über 10->7 die Schleife betreten.

Quoted from "nano"

4 ist nicht der einzige Eintrittspunkt. Man kann über 10->7 die Schleife betreten.

Danke für die Antwort! Das steht ja auch so im Skript. Ich hatte bloß scheinbar nicht ganz verstanden, was einen Schleifenkopf auszeichnet und dachte, man könnte auch bei den anderen Schleifen den Kopf verschieben und hätte dann das gleiche "Problem". Beim Nachvollziehen deiner Antwort habe ich aber bemerkt, dass 10 von 7 dominiert wird. Dadurch kommt auch 7 in Frage für den Eintrittspunkt, anders als bei 4→3 und 8→3, wo es trotzdem der gleiche Knoten ist und deshalb die Schleifen zusammengefasst werden.

Warum ist es wichtig, ob 10 von 7 dominiert wird bzw. wieso kommt es nur dann als Eintrittspunkt in Frage für die Schleife 4,5,6,7?

Es geht doch um natürliche Schleifen von Rückwärtskanten und Rückwärtskanten sind so definiert, dass der Zielknoten den Ausgangsknoten dominiert. Definition bei 6.6.2.

BTW: Wurden alle Kapitel in der Vorlesung behandelt bzw. kommen alle Kapitel in der Prüfung dran oder hat Herr Parchmann etwas davon gesagt, dass etwas nicht drankommt? Also z.B. irgendwelche Unterkapitel von 7?

Verlauf meiner Prüfung heute:

Zunächst prinzipiellen Aufbau eines Compilers erklären, ohne Rückfragen (also
nicht sehr detailliert).

Dann gings direkt zu Grammmatiken für Boolesche Ausdrücke.
Auf welche Art können die Werte codiert werden (numerisch oder durch stelle im
programmcode)
Er hat ne kleine Grammatik hingeschrieben und ich sollte erklären wie man dafür
3Adresscode generieren kann -> mit na attributierten Grammatik mit true, false
und code (inherit, inherit, synthetisch).
Beispielhaft sollte ich fürs "or" dann die Berechnungen hinschreiben.
Dann kamen wir noch drauf, dass man statt der Generierung der Zeichenkette in
"code" auch emit verwenden kann -> dafür braucht man dann ne
Ausführungsreihenfolge, also nen SDTS.
Um die Regeln nur am Ende der Produktionen stehen zu haben (für
Bottom-Up-Parsing) muss man dann noch vor dem zweiten
Ausdruck nen extra Nicht-Terminal einfügen, das das label setzt und die Stelle
hochreicht.
Dann gings um die Alternative zu der Verwendung von inheriten Attributen:
Backpatching. (Hab von mir aus gesagt, dass dafür die Maschinensprache halt
Zeilennummern statt labels für Sprünge verwenden muss). Auch hier sollte ich
wieder die Regeln für das "or" angeben.

Danach gings zum Laufzeitstack: Was passiert, wenn ne Prozedur aufgerufen wird
-> AR anlegen. Sollte auch den Aufbau des AR beschreiben. Er fragte dann noch,
was bei der definition der funktion angelegt wird und was beim call, bin nicht
ganz sicher wie er das meinte, konnte es auch nicht so gut beantworten.
Einige Werte wie die Größe des Bereichs für temporäre und lokale Vars. muss auf
jeden Fall schon bei der Definition bestimmt werden, beim Call dann noch so
Dinge wie die Rücksprung-Adresse. Habe die Frage so verstanden, dass es ums
anlegen geht und der AR wird ja komplett beim Call angelegt, evtl. gings eher um
den Zeitpunkt der Bestimmung der Werte.

Dann kamen wir zur Code-Optimierung:
Welche Schritte gibt es da: ich habe nur bilden einfacher Blöcke (sollte kurz
sagen, was das ist und wie man sie bestimmt) und bilden des Flussgraphen gesagt,
danach hat er mich unterbrochen und ist zur Datenflussanalyse übergegangen.
Da gings zuerst um Lebendigkeit (was ist das, wann ist ne Var lebendig, wofür
braucht man Infos über Lebendigkeit? -> ggf. Befehle rausschmeißen,
Registerzuordnung entscheiden, ...) wofür ich auch die Gleichungen für in und
out von Blöcken angeben sollte (und natürlich, dass es ne Rückwärtsanalyse ist).
Anschließend sollte ich noch sagen wie man das GLS löst -> iterativ, out[entry]
= leere Menge, weil die Mengen monoton wachsen kommt man zu na Lösung / nem
Fixpunkt. Er fragte dann noch wofür man Reaching Definitions braucht und was
das für ne Analyse ist, aber nicht mehr wie die Gleichungen genau aussehen.

Schlussendlich gings dann noch zu natürlichen Schleifen: Wie bestimmt man sie
(Dominatoren -> was ist ein Dominator?) und was ist dann eine natürliche
Schleife? Warum wollen wir, dass es nur einen Eintrittspunkt gibt -> wegen des
Vorziehens schleifeninvarianter Berechnungen. Er hat dann noch nein
Flussdiagramm gemalt. Ich hab vorher schon anhand dessen veranschaulicht, was
ein Dominator ist und sollte dann noch sagen warum das eine eine natürliche
Schleife ist und das andere nicht (die eine hatte mehrere Eintrittspunkte, die
andere nicht).

Viele Grüße,
Anselm

Ich musste die Phasen eines Compilers erklären. Dann kam ziemlich viel über attributierte Grammatiken und die verschiedenen Parser, etwa 10 Minuten.
Daher wurde Zwischencodeerzeugung übersprungen, wir gingen noch die Phasen der Optimierung durch (einfache Blöcke, lokale DAG-Optimierung, Datenflussgleichungen, in meinem Fall für verfügbare Ausdrücke). Zuletzt noch die beiden Methoden für globale Register-Allokation aus Kapitel 7 und die Frage, was Lebendigkeit ist.