AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Lookahead-Parser und Reduktionsregeln

Ein Thema von Desmulator · begonnen am 28. Jun 2014 · letzter Beitrag vom 29. Jun 2014
 
Benutzerbild von Desmulator
Desmulator

Registriert seit: 3. Mai 2007
Ort: Bonn
169 Beiträge
 
#6

AW: Lookahead-Parser und Reduktionsregeln

  Alt 29. Jun 2014, 18:38
Was für Grammatiken willst du denn überhaupt parsen? Kontextfreie? In dem Fall wäre es wohl vernünftig, die Definition erst mal in Chomsky-Normalform Greibach-Normalform zu bringen.
Wirklich viele Gedanken habe ich mir über die Grammatik nicht gemacht. Momentan gehe ich davon aus, dass ich in EBNF-kodierte Grammatik erhalte und anhand dieser will ich eine Eingabe bearbeiten. Also zum einen überprüfen ob die Eingabe eine gültige Syntax hat und auf der anderen, diese Eingabe eben als Baum darstellen.

Mir ist nicht klar, was du mit „keine Tabellen“ meinst.
Eine "Aktions- und Goto-Tabelle".

Habe mir heute nochmal Gedanken gemacht und bin dabei auf zwei "Lösungen" gekommen:
1. Die zuletzt benutze Regel wird vorranig vor allen anderen Regeln angewandt. Also in dem Fall würde ich, statt noch der ersten Reduktion von B zu A nicht versuchen direkt eine weitere Regel anzuwenden, sondern mit Lookahead versuchen die Reduktion von A erneut zu benutzen.
Das ganze scheint mir aber sehr unsauber und irgendwie eher eine Symptombekämpfung als eine richtige Lösung.

2. Ich ermittle vor der Reduktion alle möglichen Reduktionen und merke mir diese. Dann wende ich eine dieser an. Sollte als Folge dieser Reduktion irgendwann ein Fehler auftreten, so springe ich zurück und versuche die nächste Reduktion. Dies setzte ich dann jeweils rekursiv so fort.
Würde bestimmt funktionieren, aber hat einen ziemlich großen aufwand, wenn man davon aus geht, dass in den meisten Fällen die Regeln eben nicht eindeutig sind.

Zitat:
Was soll die Umwandlung in eine Normalform bringen? Die Grammatik (sofern das obige Beispiel nicht nur ein Ausschnitt ist) erzeugt die leere Sprache (es fehlt zumindest eine Regel wie B ← <Number>) und sie hat 2 Satzsymbole. Das müßte vor weiteren Diskussionen erst mal geregelt werden.
Zitat:
B ← "0"|...|"9"
A ← AB | B
C ← A + A | C + A
Die obigen Regeln waren nur als Beispiel gedacht um das Problem anschaulich zu beschreiben.
Lars
There are 10 kinds of people in the world:
those who get binary, and those who don’t.

Geändert von Desmulator (29. Jun 2014 um 18:42 Uhr)
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:21 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz