Sie sind nicht angemeldet.

NullAhnung

Erfahrener Schreiberling

  • »NullAhnung« ist weiblich
  • »NullAhnung« ist der Autor dieses Themas

Beiträge: 332

Registrierungsdatum: 28.04.2003

1

18.05.2004, 21:32

PuÜ Blatt 4

1. Hab ich das richtig verstanden: Ist First(X) die Menge aller Terminale, die auf X folgen können?
2. Wie ist das mit dem $ Zeichen? Kann das auch in einer Menge stehen in der auch andere Terminale stehen?
3. LL1-Bedingung: Bedeutet das, dass jedes Terminal in den Mengen nur einmal vorkommt? Also z.B. First(A)={*} First(B)={&,+}

Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11.12.2001

2

19.05.2004, 10:15

RE: PuÜ Blatt 4

Zitat

Original von NullAhnung
1. Hab ich das richtig verstanden: Ist First(X) die Menge aller Terminale, die auf X folgen können?


First(X) ist die Menge der Terminale, die bei den verschiedenen Produktionen aus dem Nicht-Terminal X an erster Stelle stehen können.
Follow(X) ist die Menge, die du meinst, alle Terminale und ggf. $, die auf das Nicht-Terminal folgen können.

Zitat

2. Wie ist das mit dem $ Zeichen? Kann das auch in einer Menge stehen in der auch andere Terminale stehen?


Natürlich bei den Follow Mengen, genau dann, wenn auf das Nicht-Terminal das Wortende folgen kann.

Zitat

3. LL1-Bedingung: Bedeutet das, dass jedes Terminal in den Mengen nur einmal vorkommt? Also z.B. First(A)={*} First(B)={&,+}


Die First Mengen "der rechten Seiten der Produktionen" müssen paarweise disjunkt sein, also eine leere Schnittmenge haben.
Weiter muss man die Followmenge des Nicht-Terminals mit berücksichtigen, wenn man aus ihm epsilon produzieren kann. Dann würde X "wegfallen" und das linkeste Zeichen an seiner Stelle ergibt sich aus den Zeichen der Follow Menge.

Es wird geprüft, ob die Wahl der Produktion bei einem gelesenen Zeichen eindeutig ist. Es dürfen also keine zwei Produktionsmöglichkeiten bestehen, bei denen an linkester Stelle das gleiche Zeichen auftaucht.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Informatik Minister« (19.05.2004, 10:18)


NullAhnung

Erfahrener Schreiberling

  • »NullAhnung« ist weiblich
  • »NullAhnung« ist der Autor dieses Themas

Beiträge: 332

Registrierungsdatum: 28.04.2003

3

21.05.2004, 17:26

Ist das schonmal richtig:

First(F) = {a, ( }
First(R) = {e, *}
First(A) = {e, +}
First(E) = {(, a} = First(D)

Follow(F) = *
Follow(E) = )
Follow(A) = $
Follow(R) = $
Follow(D) = +

Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11.12.2001

4

21.05.2004, 18:04

Habe den Übungszettel nicht, aber ich vermute schwer, dass zu den FollowMENGEN noch mehr Elemente gehören.
Dort sind alle Terminale und evtl. $ enthalten, die bei beliebigen Produktionen hinter dem betreffenden Nicht-Terminal stehen können.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

MAX

Senior Schreiberling

  • »MAX« ist männlich

Beiträge: 822

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

5

21.05.2004, 20:28

@Null Ahnung: Sowohl deine First als auch Follow Mengen sind falsch! Ein heißer Tipp!! Durch scharfes Hinsehen im Skript, hast du schon die Aufgabe 1!!! ;)
mfg
MAX

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »MAX« (21.05.2004, 20:30)


NullAhnung

Erfahrener Schreiberling

  • »NullAhnung« ist weiblich
  • »NullAhnung« ist der Autor dieses Themas

Beiträge: 332

Registrierungsdatum: 28.04.2003

6

22.05.2004, 15:23

Versteh nicht warum die falsch sein sollen. First sind die die vor den Nichtterminalen stehen können und Follow die die dahinter stehen oder nicht?
Vielleicht kann das ja mal jemand erklären.

migu

free rider

  • »migu« ist männlich

Beiträge: 2 643

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

Beruf: Developer

7

22.05.2004, 15:36

Zitat

Original von NullAhnung
Vielleicht kann das ja mal jemand erklären.


Der Informatik Minister hat's doch oben erklärt. :)
tar: Anlegen eines leeren Archivs wird feige verweigert.

MAX

Senior Schreiberling

  • »MAX« ist männlich

Beiträge: 822

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

8

22.05.2004, 18:43

Zitat


Versteh nicht warum die falsch sein sollen. First sind die die vor den Nichtterminalen stehen können und Follow die die dahinter stehen oder nicht?
Vielleicht kann das ja mal jemand erklären.

Im Skript steht die beste Erklärung!!! Besser kann man es nicht erklären!!! Um noch deutlicher zu werden, schaue dir das Beispiel 2.38 im Skript genauer an!!!
mfg
MAX

Arne

ThI

  • »Arne« ist männlich

Beiträge: 1 798

Registrierungsdatum: 07.10.2002

Wohnort: Hannover :)

Beruf: Lecturer ThI

9

23.05.2004, 22:41

@MAX: Also entweder ich verpeil hier gerade ganz übel was (könnte auch gut sein, da ganzen Tag mitm Auto unterwegs) oder ich weiß nicht, aber ich hab die selben First-Mengen wie Null Ahnung raus, wo Du meintest, die wären falsch. Biste Dir da sicher?
Einzig in der Formulierung ist es ein bissi anders, aber sonst eigntl identisch.
Die Follow Mengen habe ich hingegen auch anders

Btw noch mal was aus Adminsicht. Laut Forenregeln solltet Ihr davon absehen Lösungen für Übungsaufgaben hier zu posten, insofern diese noch aktuell sind.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

MAX

Senior Schreiberling

  • »MAX« ist männlich

Beiträge: 822

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

10

24.05.2004, 12:05

ups

Habe mich bei den First Mengen etwas verguckt. Sie sind tatsächlich richtig! Ich entschuldige mich dafür!
Zu Meiner Verteidigung: Ich habe zuerst ihre Mengen nicht genau angeschaut, sondern nur gezählt. Da es eigentlich nur drei unterschiedliche gibt und sie vier aufgeschrieben hat, obwohl zwei gleich sind, habe ich auch geschrieben, dass sie falsch sind. Es tut mir leid!!!
Die Follow Mengen von NullAhnung sind aber immer noch falsch!
mfg
MAX

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »MAX« (24.05.2004, 12:06)


mDev

Erfahrener Schreiberling

  • »mDev« ist männlich

Beiträge: 282

Registrierungsdatum: 10.10.2002

Wohnort: Hannover

Beruf: Wissenschaftlicher Mitarbeiter

11

24.05.2004, 14:45

wie gehe ich denn bei First mit den terminalsymbolen um, die werden schliesslich nicht abgeleitet?

ist in aufgabe 1 zB First(+)=First(D) oder First(*)=First(F) ?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »mDev« (24.05.2004, 15:32)


Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11.12.2001

12

24.05.2004, 15:37

Zitat

Original von mDev
wie gehe ich denn bei First mit den terminalsymbolen um, die werden schliesslich nicht abgeleitet?

ist in aufgabe 1 zB First(+)=First(D) oder First(*)=First(F) ?


FIRST(x) = x, wenn x ein Terminalzeichen ist.
Die stehen da und bleiben stehen, also können an ihrer Stelle auch nur sie selbst stehen, weil sie "terminal" sind...
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

MartinH

Zuhörer

  • »MartinH« ist männlich

Beiträge: 1

Registrierungsdatum: 23.05.2004

13

24.05.2004, 17:20

Wie ist denn Aufgabe 2 gemeint? Also man nimmt eine neue Grammatik (zum Beispiel die Produktion von E abändern, die ja die LL1-Bed verletzt) und prüft dann ob die LL1 Bedingung jetzt nicht mehr verletzt wird? Wofür gibts denn dann 13 Punkte?

Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11.12.2001

14

24.05.2004, 17:49

Zitat

Original von MartinH
Wie ist denn Aufgabe 2 gemeint? Also man nimmt eine neue Grammatik (zum Beispiel die Produktion von E abändern, die ja die LL1-Bed verletzt) und prüft dann ob die LL1 Bedingung jetzt nicht mehr verletzt wird? Wofür gibts denn dann 13 Punkte?


Achtgeben, dass die gegebene und die erzeugte Grammatik wirklich äquivalent sind, die Bedingung überprüfen und dann ist die Aufgabe fertig, wenn es eine ähnliche/die gleiche ist, wie vor einem Jahr.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

NullAhnung

Erfahrener Schreiberling

  • »NullAhnung« ist weiblich
  • »NullAhnung« ist der Autor dieses Themas

Beiträge: 332

Registrierungsdatum: 28.04.2003

15

24.05.2004, 19:18

Versuch ichs also nochmal mit diesen Mengen: Ich bin mir immer noch nicht sicher, ob ich das so richtig verstanden hab :(

Follow(E)= )
Follow(A)= $
Follow(R)= $, +
Follow(D)= +
Follow(F)= *, +, (

Arne

ThI

  • »Arne« ist männlich

Beiträge: 1 798

Registrierungsdatum: 07.10.2002

Wohnort: Hannover :)

Beruf: Lecturer ThI

16

24.05.2004, 19:44

Ist immer noch nicht richtig. Wende doch einfach den Algorithmus vom Skript Seite 48 oben an und zeichne den Follow-Graphen. Das geht viel einfacher.
Und bitte nicht immer Lösungen posten, da das Blatt ja noch abgegeben wird und sonst gegen die Forumsregeln verstöße.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

NullAhnung

Erfahrener Schreiberling

  • »NullAhnung« ist weiblich
  • »NullAhnung« ist der Autor dieses Themas

Beiträge: 332

Registrierungsdatum: 28.04.2003

17

24.05.2004, 21:08

Dieser Algorithmus klappt bei mir auch nicht.

MAX

Senior Schreiberling

  • »MAX« ist männlich

Beiträge: 822

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

18

24.05.2004, 21:14

Dann schaue dir das Beispiel 2.38 im Skript an! Dann hast du es! Ist es so schwer sich das anzuschauen?
mfg
MAX