Diskussion:LR-Parser

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 1 Jahr von 95.91.246.112 in Abschnitt Beispiel
Zur Navigation springen Zur Suche springen

Beispiel

[Quelltext bearbeiten]

Das Beispiel braucht dringend eine Graphik des zugehörigen Zustandsautomaten. (nicht signierter Beitrag von Himmelsfisch (Diskussion | Beiträge) 10:56, 5. Aug. 2005‎)

Ich habe im zugehörigen Abschnitt erstmal auf SLR-Parser verlinkt, da dort die Schritte erklärt sind. Wir sollten vielleicht einen extra Artikel zu dieser Erstellung aufbauen, da sie allgemein ähnlich abläuft und nur die einzelnen Schritte für die einzelen LR-Typen ein wenig anders laufen.
Eine Grafik für diesen Typ und dieses Beispiel kann trotzdem nicht schaden. --JonnyJD 19:26, 6. Mär. 2007 (CET)Beantworten
Diese Seite existiert nicht mehr --95.91.246.112 13:06, 22. Apr. 2023 (CEST)Beantworten

Problem bei der Beschreibung

[Quelltext bearbeiten]

Es steht: Bei Programmstart liegt nur der Startzustand auf dem Stapel. Aber beim Programmstart sollte kein Symbol im Keller sein - das ist nur bei den LL Pasern so, da die bei der Wurzel beginnen und nicht bei den Blättern... (nicht signierter Beitrag von 212.186.68.140 (Diskussion) 00:24, 18. Jan. 2006)

Zwischen Zuständen, die bei LR-parsing auf den stapel gelegt werden und Symbolen aus den Produktionsregeln besteht anders als beim LL-Parsing kein einfacher und direkter Zusammenhang mehr, deshalb ist die Beschreibung schon korrekt. --Rtc 16:55, 20. Jan 2006 (CET)
Ich denke auch, dass der Stapel leer sein sollte. So steht's jedenfalls auch in der Literatur, und außerdem: Wenn das Startsymbol auf dem Speicher liegt, terminiert das Parsing-Verfahren, denn es können keine Reduktionen mehr durchgeführt werden! Was du, Rtc, meintest, sagt doch auch, dass wie statt des Startsymbols genauso gut $\epsilon$ angeben könnten, oder? (nicht signierter Beitrag von 94.221.117.146 (Diskussion) 19:22, 11. Sep. 2011 (CEST)) Beantworten
Nochmal für die IPs: Beim LR-Parser liegen keine Grammatiksymbole auf dem Stapel, sondern Zustände. (Allgemein liegen bei einem Shift-reduce-Parser (nur) Grammatiksymbole auf dem Stapel, und man kann einen LR-Parser so darstellen, dass bei ihm Zustände und Grammatiksymbole (abwechselnd) auf dem Stapel liegen. Aber beim LR-Parser sind diese Grammatiksymbole auf dem Stapel nicht nötig; die Zustände allein enthalten schon die ganze Information. Darum sind z.B. bei Aho/Sethi/Ullman keine Grammatiksymbole auf dem Stapel.) -- UKoch 15:10, 12. Jan. 2012 (CET)Beantworten

"...Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen..."

Müsste es nicht Rechtsableitung (entspricth linkskanononischer Reduktion) für LR Grammatiken heißen?--84.57.0.230 15:18, 30. Jan 2006 (CET)

Siehe Diskussion:LR(k)-Grammatik#Rechtableitung Eine umgekehrte Rechtsableitung wird Rechtsreduktion genannt. Und zwar weil immer das Handle auf dasjenige Nonterminal reduziert wird, das nach der Ersetzung weitesten rechts steht. Klar? --Rtc 00:52, 2. Apr 2006 (CEST)

Kurz und bündig

[Quelltext bearbeiten]

Lese Token ein und schaue auf den Syntaxtabelleneintrag von "Aktueller Zustand und Token". Gehe sodann auf den entsprechenden Zustand über und lege das Token auf den Stapel. Lautet der Eintrag auf reduzieren, dann hole die entsprechende Menge Tokens für die aktuelle Reduktion vom Stapel und gebe den Assemblercode aus oder baue am Baum. Dann lege das Symbol für die Reduktion oben auf den Stapel. Und immer so weiter, bis "Akzeptieren" kommt oder der Eintrag in der Tabelle fehlt. So entnehme ich es aus dem umständlichen Buch "Compilerbau". Man sollte über die Autoren mal eine Politsatire drehen. Wißt ihr auch, weshalb? Weil es um einen Haufen Kohle ging, das aber keiner rausbekommen sollte und weil die Studenten dennoch innovativ dazu beitragen sollten, ohne daß sie wirklich irgendwas dabei gebacken kriegten.

Wenn ich bla bla = (1=1 ); eintippe, gibt er nicht etwa "Assign to non lvalue" aus, sondern "parse error before bla". Weil ich den korrekten Shift-Reduce-Algorithmus kenne (nach der Operatorpriorität und -assoziativität mit zwei Tokenzeigern eingrenzen und im Assemblercode dem ersetzenden R-Wert das Resultat zuweisen, durch den ersetzt wird), hat es mich zunächst irritiert, daß er den ersten Fehler nicht in der Klammer fand. Aber nun bin ich so weit, daß ich kapiert habe, daß ja jederzeit im Code eine neue Variablendefinition oder -deklaration auftauchen könnte, etwa wenn man in C den Code-Block durch geschweifte Klammern eingrenzt. Deshalb brettert er vor dem "Schiebereduzieren" mit zwei Zeigen erstmal mit dem LR1-Algorithmus drüber, um Kontrollstrukturen, Variablendefinitionen und Type-Casts zu erkennen. So erkennt er auch die Syntaxfehler. Aber die konkrete Übersetzung der in den mit dem LR1-Algorithmus geparsten Ausdrücke macht er tatsächlich mit "Shift Reduce". Letzte Seite von Wolfgang Sommerguts "Programmieren in C" von 1997. Das sind die Schieberegeln. Alle Operatoren mit derselben Priorität vormerken und nach der Assoziativität auf den ersten schieben.

(nicht signierter Beitrag von 93.201.4.53 (Diskussion) 13:40, 8. Feb. 2016 (CET))Beantworten