Fachrat Informatik - Forum

Also abgegeben werden muss erst nächste Woche laut Übungszettel .... aber ist ne gute Frage

Die Übungen finden statt, wurde in der letzten Übung gesagt.

Ich habe ein Problem beim Bottom-Up-Parsing, wenn es darum geht, shift/reduce und reduce/reduce Konflikte aufzulösen, bzw. in der Parsing-Tabelle zu entscheiden, welches von den beiden man benutzen will/muss/soll.
Im Skript wird angegeben, dass man den Terminalsymbolen Prioritäten gibt und es danach entscheidet.
Aber wie wende ich das konkret an, irgendwie blicke ich da nicht mehr durch.

Wenn man einen nicht eindeutigen Zustand in der Parsingtabelle hat, muss man beim parsen gucken, von welchem zustand man in diesen Zustand kommt.
Z.B
zu parsen :
(1) A+A*A
Prioritäten: "*" > "+"

(2) A*A*A
Prioritäten: "*" > "+"


Der kritische Zustand in der Parsingtabelle tritt auf, wenn du das 2. A liest, dann weiß der Parser nicht, ob shiften oder reduce. Im ersten Fall soll geshiftet werden, da * eine höhere Prio haben soll als + ( also Punkt-vor-Strich-Rechnung). Jetzt musst man aus der Parsingtabelle ablesen, was man vor dem Aktuellen A gelesen hat.
Wenns ein + war --> shiften,
wenns ein * war --> reduce/shiften(kommt drauf an ob * links oder rechtsassoziativ sein soll (variiert nach aufgabe!!))
Ablesen tut man das aus der TAbelle anhand der Zustände.

Einigermaßen klar? Sonst muss ich mal doch noch ne Bsp-Tabelle rauskramen, daran kann mans besser erklären..

Danke erstmal für deine Mühe,

Leider ist es mir noch nicht so wirklich klar, wenn du das Beispiel aus dem Skript evtl. erläutern könntest, wäre nicht schlecht.

Edit : besser spät als nie, aber ich hab es jetzt verstanden, jedenfalls hab ich alle übungen durchgerechnet und es hat gepasst. Dann darf es jetzt auch in der Klausur drankkommen, ist mein zweiter Anlauf, damals war aber noch Herr Specht Übungsleiter, mal gucken, ob sich im Klausuraufbau viel geändert hat.

Ergebnisse sind da : http://www-psue.informatik.uni-hannover.…/PSUEWS0708.pdf

1,7 ist die beste Note??
Ich überlege das Fach ja auch im Sommer zu machen, aber wenn ich mir so die Noten anschaue, mit 86,X % bekommt man gerade mal eine 1,7!! Und mach braucht 95% für ne 1.0!! Ganz schön happig!
Kann man das Fach empfehlen? Weil hab schon von einigen gehört, dass sie trotz sehr vielem Lernen eine schlechte Note geschrieben haben.

Also ich kann es nicht unbedingt empfehlen. Es geht halt nicht um Verständnis sondern nur Aufgaeben kloppen auf Speeeed und korrekt. Letzlich dann einiges Glück dabei, enwteder du leitest in 35 Schritten ein Wort KORREKT ab oder machst halt einen kleinen Fehler was dann bad luck ist.

Falls dich das ganze interessiert kann ich eher Compilerkosntruktion II empfehlen, das fand ich deutlich einfacher (eben das genaue Gegenteil: man muss die Sachen verstanden haben, da mündlich)

Ist jetzt aber nur meine Meinung, habe generell Probleme mit Klausuren wo es primär auf "Fingerfertigkeit" ankommt

Hm, also wenn du die aktuellen Noten meinst, da haben ja nicht so viele mitgeschrieben, bei den "richtigen" Terminen (also im SoSe, wo auch die Veranstaltung liegt) gibt es in der Regel nicht nur eine 1.0.
Dazu kommt, dass man durch Hausübungen die Note auch noch aufbessern kann (sofern sich da nichts geändert hat).

Zur Vorlesung: Wenn du nach dem Schwierigkeitsgrad einer Vorlesung urteilen willst .... also mal ganz davon abgesehen, dass man das nicht machen sollte ... würde ich sagen: Mittelschwer und Studentenabhängig.
Meine Erfahrung: Wenn man im Semester die Hausübungen macht, und zwar gründlich, auch wenn es mal zwei Stunden dauert, und ich meine selbstständig machen, dann hat man bei der Klausur null Probleme. Hinzu kommen noch die Punkte aus den Hausübungen. Wenn man erst zur Klausur lernt, dann wird es in der Tat sehr schwer, weil es hier wirklich um das praktische Anwenden der erlernten Techniken geht, und nicht darum, die theoretische Funktionsweise zu erklären.
Also, wenn du dich für die Thematik interessiert, und/oder du später mal Compiler Konstruktion hören willst, würde ich dir die Vorlesung als Fingerübung empfehlen.

Und zur Klausur: Ich habe schon öfters mal gehört, dass viele Studenten meinten, es ginge in der Klausur um Geschwindigkeit. Von anderen hört man, dass sie ne halbe Stunde vorher fertig waren..

Und noch was: Wenn du in theoretischer Informatik Spaß an Automaten hattest, wirst du diese Vorlesung auch mögen. Wenn du vorher keinen Spaß an Automaten hattest, kann es durchaus sein, dass du nach der Vorlesung Spaß dran hast

Diese Klausur ist mir ein Rätsel. Das Thema ist im Grunde ganz interessant und die Übungen gingen mir leicht von der Hand. Die Klausuraufgaben orientieren sich an den Übungsaufgaben und so hatte ich während/nach der Klausur auch ein ganz gutes Gefühl. Trotzdem hab ich sie nur gerade so bestanden.
Die Form ist sehr wichtig und sowas wie Folgerichtig gibt's nicht. Wenn man beim Ableiten eines Wortes am Anfang irgendwo einen Buchstaben vergisst, gehen die Punkte nur so fliegen.

Quoted from "XAX"

Die Form ist sehr wichtig

Stimmt, denn erstens ist es ein Formales Fach und zweitens war das Skript erlaubt, wodurch man alle Notationen problemlos hätte Nachschlagen können.

Quoted from "XAX"

sowas wie Folgerichtig gibt's nicht. Wenn man beim Ableiten eines Wortes am Anfang irgendwo einen Buchstaben vergisst, gehen die Punkte nur so fliegen.

Folgerichtig gab es sehr wohl. Und Punkte "flogen" nur da, wo es durch den Fehler im folgenden sehr viel einfacher wurde. (z.B. musste man durch den Fehler 10 Ableitungsschritte weniger machen, so bekam man darauf auch Abzüge.)

Hmmm, ist ja ziemlich gespalten die Meinung zu dem Fach.
Na mal schauen

Also, ich hab das auch schon ein paar mal korrigiert, und kann dir versichern, dass die Korrektoren in der Regel alles andere als penibel sind. Und bei den diejährigen Korrektoren glaube ich auch nicht, dass sich da etwas geändert hat
Also an denen liegt es in der Regel nicht

Quoted from "Dot"

Kann man das Fach empfehlen? Weil hab schon von einigen gehört, dass sie trotz sehr vielem Lernen eine schlechte Note geschrieben haben.

Allein wegen des grundlegenden Inhalts ist die Vorlesung unbedingt zu empfehlen - siehe auch drei Posts hier: A-Fächer: Eure Meinungen
Was die Klausur angeht: Wenn man die (teilweise umfangreichen) Übungsaufgaben macht, sollte das wirklich nicht so schwer sein. In der Prüfung vor einem Semester gab es auch 1,0en.

Hallo, ich habe eine Frage zum aktuellen Übungsblatt, Aufgabe 2.
Es soll ein regulärer Ausdruck entwickelt werden, der alle syntaktisch korrekten URLs ohne den IPv6 Standard akzeptiert.
Angegeben sind zwei Links, einmal zur Wikipedia über URLs und einmal zum rfc3986 Standard.
http://de.wikipedia.org/wiki/Uniform_Resource_Locator
http://tools.ietf.org/html/rfc3986
Müssen wirklich alle Möglichkeiten, die im Standard angegeben sind, abgetippt werden?
Das scheint mir sehr viel Tipparbeit zu sein... Oder ist das wohl irgendwie anders gemeint?

Quoted from "retr0virus"

Müssen wirklich alle Möglichkeiten, die im Standard angegeben sind, abgetippt werden?
Das scheint mir sehr viel Tipparbeit zu sein... Oder ist das wohl irgendwie anders gemeint?

Da die Aufgabe 3 Punkte gibt, wird da wohl schon ein bisschen was verlangt sein. Wahrscheinlich lässt sich der Aufwand einschränken, wenn man bestimmte Terme mit Namen versieht (siehe Hinweis zum Skript).

Zumal in rfc3986 ja schon fast eine ähnliche Schreibweise verwendet wird...

Hallo,
habe zum neuen Übungsblatt wieder eine Frage:
A2: Es soll ein nichtdeterministischer Transitionsgraph ohne Epsilon-Übergänge erzeugt werden.
Es muss dazu ja jeder Knoten entfernt werden, zu dem nur Epsilon-Übergänge führen.
Bedeutet das, auch wenn der Knoten andere Übergänge besitzt, die aber nur von ihm selbst auf sich führen,
dann wird er auch entfernt? So genau ist das meiner Meinung nach in der Regel nicht beschrieben.
Dort wird nur allgemein von einem Übergang zum Knoten gesprochen, aber nicht explizit von einem Übergang
von einem anderen Knoten aus... Rein logisch betrachtet kann der Knoten ja außer von Epsilon Übergängen nicht
erreicht werden (aber wenn er erstmal erreicht wäre, gäbe es Übergänge auf ihn, wodurch er theoretisch nicht
entfernt werden dürfte...).

Meine Frage nun: Kann ein Knoten, der zwar auf sich selbst Übergänge hat, von außerhalb aber nur Epsilon-
Übergänge, nach der Regel aus der Vorlesung entfernt werden, oder nicht?

Also im Skript steht der Satz

Quoted from "Skript von Professor Parchmann"

T' enthält alle Knoten aus K, auf die wenigstens ein
Übergangspfeil zeigt, der nicht mit epsilon markiert ist, sowie den
Startknoten von T. Die Menge dieser Knoten werde mit K'
bezeichnet.

Ich würde sagen, das ist recht eindeutig: Da ja auf deinen fraglichen Zustand ein Pfeil zeigt der nicht mit epsilon beschriftet ist (auch wenn er vom Zustand selbst ausgeht) muss er wohl enthalten sein. Möglicherweise ließe sich das noch optimieren, aber nach dem Algoithmus der Vorlesung ist es ziemlich klar denke ich.

Ich habe zum neuen Übungsblatt eine Frage.
Bei mir kommt es trotz Anwendung der Entfernung der Präfixe und der Entfernung der Linksrekursionen dazu,
dass die LL(1) Bedingung nicht erfüllt wird.
Nehmen wir folgende Grammatik (nicht aus der Aufgabe, aber mit gleicher Aussage):
A -> Ba | b | epsilon
B -> b | e | epsilon

Wie zu sehen ist, ist First(Ba) geschnitten mit First(b) nicht die leere Menge( = erste Bedingung für LL(1)) , sondern { b }.
Was kann man in so einem Fall tun?
Wenn ich das Skript richtig verstehe, gibt es ja keine Regel, die so ein Problem auflöst.
Oder habe ich etwas wichtiges übersehen?
Die Entfernung der gemeinsamen Präfixe beeinflusst ja nur die direkten Produktionen, aber nicht die "tiefen" Präfixe - oder ist
die Angabe im Skript, dass kein gamma_i das Präfix alpha haben soll so zu verstehen, dass jedes First(gamma_i) = alpha ebenfalls
ersetzt wird? Nur wie wird das dann mit den weiteren Produktionen gehandhabt?
Man kann ja schlecht aus dem B -> b | e | epsilon einfach das b rausnehmen?! Oder würde dann bei allen "tieferen" Nichtterminalen
das gemeinsame Präfix durch epsilon ersetzt?

Meiner Meinung nach wird der Fall von der Regel nicht abgedeckt, kann mich natürlich auch irren, bitte dann aber um Aufklärung.