Produktion

Zur Produktion wird von einem Nicht-Terminal-Symbol, das auch als Startsymbol bezeichnet wird, ausgegangen. Dieses Startsymbol, das die linke Seite einer definierten Grammatik-Regel beschreibt, wird anhand dieser Regeln durch eine passende Folge der rechten Seite ersetzt. Es entsteht somit eine Folge von Terminal- und Nicht-Terminal-Symbolen. Ein Resultatstext, nur bestehend aus reinen Terminal-Symbolen, kann dann durch Anwendung der Regeln aus dem Startsymbol sukzessive produziert werden. Die angegebenen Regeln werden daher auch als Produktionsregeln bezeichnet. Bei dem angewendeten Verfahren spricht man von der sog. Rechtsherleitung.

Beispiel zur Anwendung der natürlichen Grammatik zur Produktion:

Ein beliebiges Nicht-Terminal-Symbol wird als sog. Startsymbol definiert. Aufgrund der Regeln können dann gültige Texte produziert werden. Nimmt man [C] als Startsymbol an, so lassen sich obige Regeln wie folgt anwenden:

Man erkennt, dass durch die wiederholte Anwendung der Regel R2 ein beliebig langer Text entstehen kann. Ein Text der Form [aaaaabcc] kann also durch sukzessive Anwendung der Regeln aus dem Startsymbol [C] produziert werden. Alle Texte, die anhand der Regeln produziert werden können, sind gültig im Sinne der Grammatik. Gültige Texte wären in diesem Beispiel demnach [abcc], [aabcc], [aaabcc] usw., wohingegen der Text [bcbca] ungültig ist.

Beispiel zur Anwendung einer formalen Grammatik zur Produktion:

Hier wird in endlich vielen Schritten eine mathematisch eindeutige Lösung produziert.

Reduktion

Die Reduktion beschreibt die Umkehrung der Produktion. Die rechte Seite der Grammatik-Regel wird dabei schrittweise durch die linke Seite der Regel ersetzt, bis das Resultat aus genau einem Nicht-Terminal-Symbol (Startsymbol) erreicht ist. Eine solche Regel wird deshalb auch als Reduktionsregel bezeichnet. Eine Abfolge von Anwendungen dieser Regel wird als Ableitung bezeichnet, wobei die Eingabe von links nach rechts abgearbeitet wird. Man spricht von einer sog. Rechtsableitung. Dieser Weg beschreibt gerade den Ablauf während eines Übersetzungsvorgangs in Computersystemen. Der sog. Parser (siehe unten) eines Compilers (bzw. Interpreters) wendet dabei eine formale Grammatik auf einen konkreten (kontextbehafteten) Zeichenstrom an und reduziert diesen zu einem einzelnen finalen Nicht-Terminal-Symbol (Expression). Die Parser-Verarbeitung in einer realen Rechnerumgebung bedient sich dabei eines Speicher-Stacks, auf den die Symbole nacheinander abgelegt und in ein Nicht-Terminal (E) umgewandelt werden. Aus diesem Grund müssen die Symbole der Reihe nach auf den Stack geschoben (shift) werden. Erkannte rhs-Token (Terminale) werden ?reduziert“ zu lhs-Symbolen (Nicht-Terminale). Dieser Prozeß wird so lange fortgesetzt, bis soviel des gesamten Eingabestroms auf dem Stack liegt, dass die Reduktion final ein Nicht-Terminal-Symbol (E) erzeugen kann. Dann wird das Symbol von Stack gelöscht und ein neuer Teil des Eingabestroms kann untersucht werden.

Beispiel eines Shift-Reduce-Parsers: (Anwendung der o.g. formalen Grammatik)

Im nachfolgenden Beispiel wird die Funktion eines sog. Shift-Reduce-Parsers dargestellt. Dabei werden die Symbole des Eingabestroms von rechts auf den Stack geschoben (per Shift-Left-Operation). Shift-Operationen gelten dabei für alle Symbole, d.h. auch für mathematische Operatoren (+,*). Die Multiplikation der Nicht-Terminale (E*E) wird hier zuerst reduziert, da für die Multiplikation in dieser Grammatik eine höhere Wertigkeit angenommen wird (Punkt-vor-Strich-Rechnung).

Konflikte

Anstelle des Arbeitsschritts (shift *) in Punkt 6 könnte theoretisch auch eine Reduktion (R1, E + E -> E) erfolgen. Allerdings würde dies die Grammatikregeln für Punkt-vor-Strich-Rechnung verletzten, da die Addition dann eine höhere Wertigkeit besäße. Dieser Konflikt wird auch als Shift-Reduce-Konflikt bezeichnet. Die Grammatik im obigen Beispiel ist also doppeldeutig. Daher muß die Wertigkeit der Operatoren (Operator-Präzedenz) explizit festgelegt werden. Weiterhin sind ggf. Doppeldeutigkeiten bei der Reduktion zu vermeiden. Eine Grammatik der Form

beinhaltet einen sog. Reduce-Reduce-Konflikt. Liegt ein Token (id) auf dem Stack, könnte es nach obiger Grammatik sowohl zu (T) als auch zu (E) reduziert werden. Diese Konflikte sollten beim Entwurf der Grammatik explizit ausgeschlossen werden. Ist dies nicht der Fall, so beheben Parser-Generatoren wie Yacc diese durch standardisierte Wertigkeiten. So wird bei einem Shift-Reduce-Konflikt immer die Shift-Operation ausgeführt und bei einem Reduce-Reduce-Konflikt immer die in der Grammatik zuerst genannte Operation durchgeführt (d.h. im obigen Beispiel E:id). Außerdem werden Warnungen ausgegeben, sofern ein Konflikt erkannt wird.

• Einleitung
• Semantik und Grammatik
• Produktion, Reduktion, Konflikte
• Compiler/Interpreter
• Scanner, Parser, CodeGenerator
• Lex und Yacc
• Lex, Yacc und C++
• Vorbereitungen
• Der Scanner
• Die Grammatik
• Der Syntaxbaum
• Der Interpreter
• Flex und Bison
• Beispielcode