Die Hauptunterschied zwischen mehrdeutiger und eindeutiger Grammatik ist, dass die mehrdeutige Grammatik ist eine kontextfreie Grammatik, für die eine Zeichenkette existiert, die mehr als eine ganz links liegende Ableitung haben kann, während eine eindeutige Grammatik eine kontextfreie Grammatik ist, für die jede gültige Zeichenkette eine eindeutige ganz links liegende Ableitung hat.

Grammatik bezieht sich auf die syntaktischen Regeln in natürlichen Sprachen. 1956 führten Informatiker ein mathematisches Grammatikmodell zum Schreiben von Computersprache ein. Wenn es möglich ist, alle Zeichenketten einer Sprache unter Verwendung einer bestimmten Grammatik abzuleiten, dann sagt man, dass die Sprache aus dieser Grammatik generiert wird. Kontextfreie Grammatik ist eine Art von Grammatik. Diese Grammatik erzeugt kontextfreie Sprache. Die kontextfreie Grammatik kann mehrdeutig oder eindeutig sein. Wenn es für eine bestimmte Zeichenfolge zwei oder mehr Ableitungen gibt, wird diese Grammatik als mehrdeutig bezeichnet. Wenn es für eine bestimmte Zeichenfolge nur eine eindeutige Ableitung ganz links gibt, wird diese Grammatik als eindeutige Grammatik bezeichnet.

Mehrdeutige Grammatik, Eindeutige Grammatik

Was ist mehrdeutige Grammatik?

Eine Grammatik heißt mehrdeutig, wenn es zwei oder mehr Ableitungen für einen String gibt.

Abbildung 1: Mehrdeutige Grammatik

Angenommen, es gibt eine Grammatik, die wie folgt definiert ist.

G= ({S}, {a+b, +, *}, P, S}. Die Produktionsregeln lauten wie folgt: S -> S+S | S*S | a | b. Angenommen, es gilt erzeuge den String a+ a*b.

Betrachten Sie, S -> S+S

Das Ersetzen von 'a' für das am weitesten links stehende S ergibt Folgendes.

S-> ein +S

Das Ersetzen von S*S für S ist wie folgt.

S-> a + S*S

Das Ersetzen von 'a' für das am weitesten links stehende S ergibt die folgende Ausgabe.

S -> a+ a*S

Das Ersetzen von 'b' für das S ergibt die folgende Ausgabe.

S -> a + a * b

Dies ist die erforderliche Zeichenfolge zum Generieren.

Bei Verwendung der anderen Produktionsregel ergibt sich

S -> S* S

Wenden Sie S+S ganz links an. S ergibt Folgendes.

S -> S+S * S

Ersetzen Sie 'a' für das am weitesten links stehende S,

S -> a + S*S

Einsetzen von 'a' für das am weitesten links stehende S,

S -> a + a * S

Das Ersetzen von 'b' für S ergibt die folgende Ausgabe.

S -> a + a*b

Auch hier wurde die erforderliche Zeichenfolge generiert. Daher gibt es mehr als eine Ableitung, um die Zeichenfolge zu generieren. Daher handelt es sich um eine mehrdeutige Grammatik.

Was ist eindeutige Grammatik?

In einer mehrdeutigen Grammatik hat eine bestimmte Zeichenfolge eine eindeutige Ableitung ganz links. Beachten Sie die folgenden Produktionsregeln.

S -> L | a, L -> LS | S

Betrachten Sie die S -> L-Regel. Ersetzen Sie LS anstelle von L.

S -> LS

Ersetze S für das erste L.

S -> S S

Wenn Sie das S ganz links durch „a“ ersetzen, erhalten Sie die folgende Ausgabe.

S -> ein S

Das Ersetzen von „a“ für S ergibt Folgendes.

S -> ein a

Daher hat eine Zeichenfolge eine eindeutige Ableitung ganz links. Es handelt sich also um eine eindeutige Grammatik.

Unterschied zwischen mehrdeutiger und eindeutiger Grammatik

Definition

Eine mehrdeutige Grammatik ist eine kontextfreie Grammatik, für die ein String existiert, der mehr als eine ganz links liegende Ableitung oder Parse-Bäume haben kann. Eindeutige Grammatik ist eine kontextfreie Grammatik, für die jede gültige Zeichenfolge eine eindeutige Ableitung ganz links oder einen Analysebaum hat.

Anzahl der Ableitungen ganz links

In einer mehrdeutigen Grammatik kann eine Zeichenfolge zwei oder mehr ganz links liegende Ableitungen haben, aber in einer eindeutigen Grammatik hat eine Zeichenfolge eine eindeutige ganz links liegende Ableitung.

Abschluss

Kontextfreie Grammatik kann mehrdeutig oder eindeutig sein. Der Unterschied zwischen mehrdeutiger und eindeutiger Grammatik besteht darin, dass die mehrdeutige Grammatik eine kontextfreie Grammatik ist, für die es eine Zeichenfolge gibt, die mehr als eine ganz links liegende Ableitung haben kann, während eine eindeutige Grammatik eine kontextfreie Grammatik ist, für die jede gültige Zeichenfolge eine eindeutige Ableitung ganz links hat.

Referenz:

1. „Mehrdeutige Grammatik“. Wikipedia, Wikimedia Foundation, 17. Juli 2018, hier verfügbar.2. „Compiler-Design | Mehrdeutige Grammatik.“ GeeksforGeeks, 10. Februar 2018, hier verfügbar.3. „Ambiguous Grammar“, Neso Academy, 29. März 2017, hier verfügbar.

Bild mit freundlicher Genehmigung:

1. „Leftmostderivations jaredwf“ Von Jaredwf in der englischen Wikipedia – Von en.wikipedia nach Commons von EdwardHades (Public Domain) über Commons Wikimedia übertragen