Rechtsreduktion

Rechtsreduktion

Rechtsreduktion ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine umgedrehte Rechtsableitung.

Beim Bottom-Up-Parsing werden keine Ableitungen vom Startsymbol der Grammatik aus zur Eingabe berechnet, sondern Reduktionen von der Eingabe zum Startsymbol. Im Zusammenhang mit LR(k)-Parsing spricht man deshalb bei einer umgedrehten Rechtsableitung

\alpha \beta w \Leftarrow_r \alpha A w

auch von einer Rechtsreduktion, bei der nach der Regel A \rightarrow \beta reduziert wurde.

  • α repräsentiert den Parse-Stack unterhalb des Handles.
  • β ist das Handle.
  • w ist der noch nicht abgearbeitete Teil der Eingabe.

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Synthesealgorithmus-Normalform — Die Synthesealgorithmus Normalform beschreibt, wie aus einem Datenbankentwurf ein Relationenschema der dritten Normalform wird. Ein alternativer Algorithmus ist der Zerlegungsalgorithmus, welcher in die Boyce Codd Normalform (BCNF) transferiert.… …   Deutsch Wikipedia

  • LR Parser — Ein LR Parser ist ein Bottom Up Parser für LR Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. Inhaltsverzeichnis 1 Allgemeines 2 Aufbau… …   Deutsch Wikipedia

  • Linksableitung — Eine Rechtsableitung ist nach einer formalen Grammatik eine Ableitung eines Wortes w0 in wn, bei der in jedem Ableitungsschritt von wi in wi + 1 ( und i < n) stets das rechteste Nichtterminalsymbol von wi ersetzt wird. Eine Linksableitung ist… …   Deutsch Wikipedia

  • Ableitung (Informatik) — Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen. Unter einem Wort versteht man eine beliebige Zeichenkette, also eine endliche Folge von Symbolen. Eine… …   Deutsch Wikipedia

  • Kanonische Überdeckung — Die kanonische Überdeckung ist ein Konzept aus der relationalen Entwurfstheorie, die sich mit dem Entwurf der Schemata relationaler Datenbanken befasst. Am Anfang des Entwurfs eines relationalen Schemas steht die Informationsbedarfsanalyse, sie… …   Deutsch Wikipedia

  • LR(k) — In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k) Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR(k) Parsers bildet. Man nennt eine kontextfreie Grammatik LR(k) Grammatik, wenn jeder… …   Deutsch Wikipedia

  • LR-Parser — Im Compilerbau ist ein LR Parser ein Bottom Up Parser für LR Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Rechtsableitung — Eine Rechtsableitung (auch rechtskanonische Ableitung, engl: rightmost derivation) ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, bei der stets das am weitesten rechts stehende sogenannte Nichtterminalsymbol durch… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”