Operatorgrammatik und Vorrangparser im Inhaltsverzeichnis
Eine Grammatik, die zum Definieren mathematischer Operatoren verwendet wird, wird als Operatorgrammatik oder Operatorpräzedenzgrammatik bezeichnet . Solche Grammatiken haben die Einschränkung, dass keine Produktion entweder eine leere rechte Seite (Nullproduktionen) oder zwei benachbarte Nichtterminale auf ihrer rechten Seite hat.
Beispiele –
Dies ist ein Beispiel für Operatorgrammatik:
E->E+E/E*E/id
Die unten angegebene Grammatik ist jedoch keine Operatorgrammatik, da zwei Nichtterminale nebeneinander liegen:
S->SAS/a A->bSb/b
Wir können es jedoch in eine Operatorgrammatik umwandeln:
S->SbSbS/SbS/a A->bSb/b
Operator-Präzedenz-Parser –
Ein Operator-Präzedenz-Parser ist ein Bottom-up-Parser, der eine Operatorgrammatik interpretiert. Dieser Parser wird nur für Operatorgrammatiken verwendet. Mehrdeutige Grammatiken sind in keinem Parser zulässig, außer im Parser mit Operatorvorrang.
Es gibt zwei Methoden, um zu bestimmen, welche Vorrangbeziehungen zwischen einem Terminalpaar gelten sollten:
- Verwenden Sie die herkömmliche Assoziativität und den Vorrang des Operators.
- Das zweite Verfahren zum Auswählen von Operator-Vorrang-Beziehungen besteht darin, zunächst eine eindeutige Grammatik für die Sprache zu konstruieren, eine Grammatik, die die richtige Assoziativität und Vorrang in ihren Analysebäumen widerspiegelt.
Dieser Parser stützt sich auf die folgenden drei Vorrangbeziehungen: ⋖, ≐, ⋗
a ⋖ b Dies bedeutet, dass a „Vorrang zu“ b gibt.
a ⋗ b Dies bedeutet, dass a „Vorrang vor“ b hat.
a ≐ b Dies bedeutet, dass a „den gleichen Vorrang hat wie“ b.
Abbildung – Operatorvorrangbeziehungstabelle für die Grammatik E->E+E/E*E/id
Es gibt keine Beziehung zwischen id und id, da id nicht verglichen wird und zwei Variablen nicht nebeneinander auftreten können. Es gibt auch einen Nachteil dieser Tabelle – wenn wir n Operatoren haben, dann ist die Größe der Tabelle n*n und die Komplexität 0(n 2 ). Um die Größe der Tabelle zu verringern, verwenden wir die Operatorfunktionstabelle .
Operatorvorrangparser speichern die Vorrangtabelle normalerweise nicht mit den Beziehungen; vielmehr werden sie auf besondere Weise implementiert. Operatorvorrangparser verwenden Vorrangfunktionen , die Terminalsymbole auf ganze Zahlen abbilden, und die Vorrangbeziehungen zwischen den Symbolen werden durch numerischen Vergleich implementiert. Die Analysetabelle kann durch zwei Vorrangfunktionen f und g codiert werden , die Terminalsymbole auf ganze Zahlen abbilden. Wir wählen f und g so, dass:
- f(a) < g(b), wenn a Vorrang vor b hat
- f(a) = g(b), wenn a und b den gleichen Vorrang haben
- f(a) > g(b), wenn a Vorrang vor b hat
Beispiel – Betrachten Sie die folgende Grammatik:
E -> E + E/E * E/( E )/id
Dies ist der gerichtete Graph, der die Vorrangfunktion darstellt:
Da der Graph keinen Zyklus enthält, können wir diese Funktionstabelle erstellen:
fid -> g* -> f+ ->g+ -> f$ gid -> f* -> g* ->f+ -> g+ ->f$
Die Größe der Tabelle ist 2n .
Ein Nachteil von Funktionstabellen besteht darin, dass wir zwar leere Einträge in der Beziehungstabelle haben, aber nicht leere Einträge in der Funktionstabelle. Leere Einträge werden auch als Fehler bezeichnet. Daher ist die Fehlererkennungsfähigkeit der Beziehungstabelle größer als die der Funktionstabelle.
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
// function f to exit from the loop
// if given condition is not true
void f()
{
printf("Not operator grammar");
exit(0);
}
void main()
{
char grm[20][20], c;
// Here using flag variable,
// considering grammar is not operator grammar
int i, n, j = 2, flag = 0;
// taking number of productions from user
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%s", grm[i]);
for (i = 0; i < n; i++) {
c = grm[i][2];
while (c != '\0') {
if (grm[i][3] == '+' || grm[i][3] == '-'
|| grm[i][3] == '*' || grm[i][3] == '/')
flag = 1;
else {
flag = 0;
f();
}
if (c == '$') {
flag = 0;
f();
}
c = grm[i][++j];
}
}
if (flag == 1)
printf("Operator grammar");
}
Input :3 A=A*A B=AA A=$ Output : Not operator grammar Input :2 A=A/A B=A+A Output : Operator grammar
$ist hier eine Nullproduktion, die auch in Operatorgrammatiken nicht erlaubt ist.
Vorteile -
- Es lässt sich leicht von Hand aufbauen.
- Es ist einfach, diese Art von Parsing zu implementieren.
Nachteile –
- Es ist schwierig, mit Token wie dem Minuszeichen (-) umzugehen, das zwei verschiedene Vorrang hat (je nachdem, ob es unär oder binär ist).
- Es ist nur auf eine kleine Klasse von Grammatiken anwendbar.
Lernen Sie alle GATE CS-Konzepte mit kostenlosen Live-Kursen auf unserem YouTube-Kanal kennen.