Programmiersprachen & Übersetzer

postpilzkopf

Trainee

Posts: 52

Date of registration: Apr 29th 2005

1

Wednesday, September 21st 2005, 1:08pm

Hallo Zusammen,
weiß jemand ob unsere Kenntnisse in ML und Prolog Klausurrelevant sind, da wir beides ja nicht so eingängig behandelt haben und eigentlich zum Rest der Vorlesung nicht richtig passt, sprich Grammatiken,Transitionsgrafen,Kellerautomaten...

i feel the fungus in me growing

Go to the top of the page

Ray-D

Alter Hase

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

2

Wednesday, September 21st 2005, 1:16pm

ich weiss nicht wie es dieses jahr ist, aber als ich vor zwei semestern psue schrieb gab es eine PROLOG-aufgabe. sie war sogar am stärksten gewichtet.

"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

Go to the top of the page

KingLifetec

Praktikant

Posts: 31

Date of registration: Feb 18th 2004

3

Friday, September 30th 2005, 12:37pm

Übung3

Ich hab mal eine Frage zu der Lösung der 3.Übung und zwar zur Aufgabe 2b.
Ich versteh nicht was das "=" da soll, darf man das so überhaupt schreiben? Außerdem wäre es doch sowieso falsch, weil da ja dann im Prinzip steht, dass k = m + n und nicht n = k + m.

Wer aufhört besser zu werden, hat aufgehört gut zu sein!

Go to the top of the page

postpilzkopf

Trainee

Posts: 52

Date of registration: Apr 29th 2005

4

Friday, September 30th 2005, 3:28pm

ue3-2b

ja erlaubt ist das schon, damit soll die menge der wörter angegeben werden die zunächst k nullen dann m einsen und dann k+m=n nullen hat. die lösung scheint das aber nicht zu liefern sondern eher die Produktion:
S->e|0S0|1S0

i feel the fungus in me growing

Go to the top of the page

EnteTaylor

Trainee

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

5

Friday, September 30th 2005, 3:40pm

RE: Übung3

Quoted

Original von KingLifetec
Ich hab mal eine Frage zu der Lösung der 3.Übung und zwar zur Aufgabe 2b.
Ich versteh nicht was das "=" da soll, darf man das so überhaupt schreiben? Außerdem wäre es doch sowieso falsch, weil da ja dann im Prinzip steht, dass k = m + n und nicht n = k + m.

Hm, verstehe ich genausowenig. Du meinst bestimmt das '=' Zeichen in den Produktionen von G2 nach S -> 0S. Die Grammatik in der Lösung beschreibt nach meiner Auffassung die Sprache
L={0^k 1^m 0^n | m=n, k,l,m >=0} (ganz anders, als in der Aufgabe). Vielleicht hat aber das '=' eine ganz besondere Bedeutung...
Vielleicht ist es aber auch ein Fehler.
Aber wie kommst du auf k=m+n?? Die Anzahl der 0en am Wortanfang hat (nach der Lösung) doch überhaupt nichts mit den 1en und 0en dahinter zu tun (es könnten auch Wörte wie z.B 0 1111 0000 gebildet werden).

In der Lösung von c steht auch so ein '='. Dort hat es aber (scheinbar) keine Bedeutung.

Meine Gedächtnisprotokolle: www.janwy.de

Go to the top of the page

KingLifetec

Praktikant

Posts: 31

Date of registration: Feb 18th 2004

6

Friday, September 30th 2005, 4:52pm

Ich komme darauf, weil ich das "=" so interpretiert habe, dass zuerst die k nullen kommen und das gleichheitszeichen bedeutet, dass die nachfolgenden zeichen gleich der k nullen ist.
Und da die nachfolgenden Zeichen die m einsen und die n nullen sind kommt bei mir k=m+n.
Aber ich finde diese Schreibweise mit dem "=" sowieso verwirrend.

Wer aufhört besser zu werden, hat aufgehört gut zu sein!

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

7

Friday, September 30th 2005, 5:11pm

Ich glaube, es ist hier nur ein Tippfehler. Die Produktionen sollten heißen:
S -> 0S0
S -> A
A -> 1A0
A -> epsilon

Dann kommt es glaube ich hin.

mfg
MAX

This post has been edited 1 times, last edit by "MAX" (Sep 30th 2005, 5:16pm)

Go to the top of the page

Sinan

Senior Schreiberling

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

8

Friday, September 30th 2005, 6:53pm

Übung 3, 2.b

man kann es einfach umschreiben, dann sieht es viel einfacher aus:
0^k 1^m 0^n
mit n=k+m entspricht
0^k 1^m 0^(k+m)
und das entspricht wiederrum
0^k 1^m 0^(m+k)
und entspricht
0^k 1^m 0^m 0^k

Die Produktion wird auch schöner und verständlicher:
S --> 0S0 | X
X --> 1X0 | epsilon

With great power comes great responsibility

Go to the top of the page

Sinan

Senior Schreiberling

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

9

Friday, September 30th 2005, 7:01pm

Quoted

Original von Ray-D
ich weiss nicht wie es dieses jahr ist, aber als ich vor zwei semestern psue schrieb gab es eine PROLOG-aufgabe. sie war sogar am stärksten gewichtet.

gab es auch theoretische Fragen, die man beantworten musste?
oder nur Aufgaben zu lösen?
Wurde dieses Semester etwas zum Thema gesagt?

With great power comes great responsibility

Go to the top of the page

postpilzkopf

Trainee

Posts: 52

Date of registration: Apr 29th 2005

10

Saturday, October 1st 2005, 5:59pm

parser tabelle

hallo. soll es eigentlich zu unseren Kompetenzen gehören eine Parser Tabelle für einen Bottom-Up Parser zu erstellen? wenn ja, kann mal einer kurz erläutern wie man das hinbekommt?

i feel the fungus in me growing

Go to the top of the page

Sinan

Senior Schreiberling

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

11

Saturday, October 1st 2005, 6:42pm

RE: parser tabelle

Quoted

Original von postpilzkopf
hallo. soll es eigentlich zu unseren Kompetenzen gehören eine Parser Tabelle für einen Bottom-Up Parser zu erstellen?
wenn ja, kann mal einer kurz erläutern wie man das hinbekommt?

Ich hoffe nicht. Ist eher unwahrscheinlich dass so eine Aufgabe in der Klausur vorkommt, einerseits weil wir das nicht geübt haben, andererseits weil das recht kompliziert ist.
Wie das geht, hatte Herr Specht in der 9.Übung am 20.06 kurz erläutert.
Na ja, so kurz war es vielleicht auch nicht, ich sehe vor mir einen voll komplizierten Graphen, von dem ich gerade nur Bahnhof verstehe, und das war nur der Anfang, zu Ende hatte er es nicht gebracht.

With great power comes great responsibility

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

12

Sunday, October 2nd 2005, 6:28pm

Frage

Frage zu Ü9A2:
Gibt es da einen Algorithmus, wie man solche Konflikte löst? Bestimmt(denke ich mal), aber in der Vorlesung wurde kein solcher Algorithmus vorgestellt, nur die Methode des scharfen Hinsehens??? Alleine aus der Tabelle kann ich auf den ersten Blick nicht erkennen, welche (Teil-)Ausdrücke betroffen sind. Erst durch mühseliges Ableiten wird man, wenn man Glück hat, auf so ein Ausdruck stoßen und dann die richtige Entscheidung treffen können. Wer weißt da mehr?
mfg
MAX

Go to the top of the page

cowhen

Muuuh!

Posts: 1,374

Date of registration: Dec 13th 2001

13

Sunday, October 2nd 2005, 8:59pm

RE: Frage

Quoted

Original von MAX
Frage zu Ü9A2:
Gibt es da einen Algorithmus, wie man solche Konflikte löst?
MAX

Sag mal worum es in der Aufgabe geht, etliche Leute dürften das Blatt nicht vorliegen haben...

plenty of time to relax when you are dead

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

14

Sunday, October 2nd 2005, 9:23pm

Reich auch ein Link?
Aufgabe 9

Lösung zur Aufgabe 9

Man muss im iLAM angemeldet sein.

Wie gesagt, ich erkenne die genaue Vorgehensweise nicht, außer scharfes Hinsehen und Ausprobieren.

Im Skript steht dazu nur: "Man muss dem Parser-Generator nur die Priorität und die Assoziativität der verwendeten Operatoren mitteilen. Dann löst der Generator die auftretenden shift/reduce-Konflikte entsprechend den gemachten Angaben" Dazu gibts noch ein Beispiel. Aber meine Frage ist genau: Wie der Generator das Problem algorithmisch löst?

Im Skript steht dazu nichts, es sei denn, ich bin blind.

mfg
MAX

Go to the top of the page

EnteTaylor

Trainee

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

15

Monday, October 3rd 2005, 11:55am

Ich glaube in der Lösung zu Aufgabe 1a, Übung 9 ist ein Fehler.

In den Konfigurationsübergängen heißt es da:

... -> ( 0E1+6(4E8+6T9,)*a$ ) -> ( 0E1+6(4E8+6E8,)*a$ ) ->...

Wird aber in Zustand 9 eine ) gelesen, dann muss Reduktion 1 (E -> E+T) angwendet werden. Die korrekte rechte Seite sollte also sein:

( 0E1+6(4E8 )

Damit kommt man auch zum Ziel ...-> ( 0E1,$ ) -> acc

Meine Gedächtnisprotokolle: www.janwy.de

This post has been edited 1 times, last edit by "EnteTaylor" (Oct 3rd 2005, 11:58am)

Go to the top of the page

EnteTaylor

Trainee

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

16

Monday, October 3rd 2005, 1:00pm

RE: Frage

Quoted

Original von MAX
Frage zu Ü9A2:
Gibt es da einen Algorithmus, wie man solche Konflikte löst? Bestimmt(denke ich mal), aber in der Vorlesung wurde kein solcher Algorithmus vorgestellt, nur die Methode des scharfen Hinsehens??? Alleine aus der Tabelle kann ich auf den ersten Blick nicht erkennen, welche (Teil-)Ausdrücke betroffen sind. Erst durch mühseliges Ableiten wird man, wenn man Glück hat, auf so ein Ausdruck stoßen und dann die richtige Entscheidung treffen können. Wer weißt da mehr?
mfg
MAX

Man kann sich zum Beispiel ein Wort nehmen, von dem man vermutet, dass dort Konflikte auftreten. So ein Wort kann man sich soweit ich weiß aber nur durch ausprobieren bzw. "scharfes hinsehen" mit einer gehörigen Portion "Gehirnschmalz" herleiten. Das liegt daran, dass man die Prioritäten für Grammatiken ja beliebig festlegen kann. So könnte man z.B. auch eine Grammatik "erfinden" in der die Regel Strich- vor Punktrechnung gilt.

Führt man dann die Konfigurationsübergänge des Wortes durch und gelangt an eine Stelle, bei der zwei unterschiedliche Aktionen möglich sind, dann entscheidet man sich gemäß der festgelegten Prioritäten für eine der beiden Aktionen. Wenn man Glück hat, kann man die Konflikte dann schon mit einem Wort lösen. Ein Beispiel gibt es auch im Skript S.69 (für arithmetische Ausdrücke, bei denen Punkt- vor Strichrechnung gilt).

Meine Gedächtnisprotokolle: www.janwy.de

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

17

Monday, October 3rd 2005, 1:12pm

@EnteTaylor: Genau so habe ich das auch verstanden. Das Problem ist, dass so ein Parser-Generator leider kein Gehirn hat und irgendwie das Problem algorithmisch lösen muss. Aber so wie ich sehe, sollen wir diese genaue Vorgehensweise für die Klausur gar nicht kennen und müssen, falls so eine Aufgabe kommt eben etwas Gehirnschmalz reinstecken.
mfg
MAX

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

18

Monday, October 3rd 2005, 1:17pm

Quoted

Ich glaube in der Lösung zu Aufgabe 1a, Übung 9 ist ein Fehler.

In den Konfigurationsübergängen heißt es da:

... -> ( 0E1+6(4E8+6T9,)*a$ ) -> ( 0E1+6(4E8+6E8,)*a$ ) ->...

Wird aber in Zustand 9 eine ) gelesen, dann muss Reduktion 1 (E -> E+T) angwendet werden. Die korrekte rechte Seite sollte also sein:

( 0E1+6(4E8 )

Damit kommt man auch zum Ziel ...-> ( 0E1,$ ) -> acc