Unterschied zwischen mehrdeutiger und eindeutiger Grammatik - Unterschied Zwischen

Unterschied zwischen mehrdeutiger und eindeutiger Grammatik

Das Hauptunterschied zwischen mehrdeutiger und eindeutiger grammatik ist, dass die Mehrdeutige Grammatik ist eine kontextfreie Grammatik, für die es eine Zeichenfolge gibt, die mehr als eine Ableitung ganz links haben kann, während eine eindeutige Grammatik eine kontextfreie Grammatik ist, für die jede gültige Zeichenfolge eine eindeutige Ableitung ganz links hat.

Grammatik bezieht sich auf die syntaktischen Regeln in natürlichen Sprachen. Im Jahr 1956 führten Informatiker ein mathematisches Grammatikmodell für das Schreiben von Computersprache ein. Wenn es möglich ist, alle Zeichenfolgen einer Sprache mit einer bestimmten Grammatik abzuleiten, heißt es, dass die Sprache aus dieser Grammatik generiert wird. Kontextfreie Grammatik ist eine Art von Grammatik. Diese Grammatik erzeugt eine kontextfreie Sprache. Die kontextfreie Grammatik kann mehrdeutig oder eindeutig sein. Wenn für eine bestimmte Zeichenfolge zwei oder mehr Ableitungen vorhanden sind, wird diese Grammatik als mehrdeutig bezeichnet. Wenn es für eine bestimmte Zeichenfolge nur eine eindeutige Ableitung ganz links gibt, spricht man von einer eindeutigen Grammatik.

Wichtige Bereiche

1. Was ist mehrdeutige Grammatik?
- Definition, Beispiel
2. Was ist eindeutige Grammatik?
- Definition, Beispiel
3. Unterschied zwischen mehrdeutiger und eindeutiger Grammatik
- Vergleich der wichtigsten Unterschiede

Schlüsselbegriffe

Mehrdeutige Grammatik, eindeutige Grammatik


Was ist mehrdeutige Grammatik?

Eine Grammatik gilt als mehrdeutig, wenn es zwei oder mehr Ableitungen für eine Zeichenfolge 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. Nehmen Sie an, dass dies erforderlich ist generiere den String a + a * b.

Betrachten Sie, S -> S + S

Das Ersetzen von "a" für das linke linke S ergibt Folgendes:

S-> a + S

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

S-> a + S * S

Ersetzen Sie „a“ für das am weitesten links stehende S, um die folgende Ausgabe zu erhalten.

S -> a + a * S

Wenn Sie das S durch „b“ ersetzen, erhalten Sie folgende Ausgabe:

S -> a + a * b

Dies ist die zum Generieren erforderliche Zeichenfolge.

Bei Verwendung der anderen Produktionsregel wird es geben

S -> S * S

Wende S + S an der linken Seite an. S ergibt Folgendes:

S -> S + S * S

Ersetzen Sie „a“ durch die meisten linken S,

S -> a + S * S

Anstelle der äußersten linken S wird „a“

S -> a + a * S

Durch Ersetzen von „b“ für S erhält man folgende Ausgabe.

S -> a + a * b

Wieder wurde die erforderliche Zeichenfolge generiert. Daher gibt es mehr als eine Ableitung, um die Zeichenfolge zu generieren. Daher ist es 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. Substitute LS anstelle von L.

S -> LS

Ersatz S für erstes L.

S -> S S

Ersetzen Sie "a" für das äußerste linke S, um die folgende Ausgabe zu erhalten.

S -> a S

Ersetzen von „a“ für S ergibt Folgendes:

S -> a a

Daher hat eine Zeichenfolge eine eindeutige Ableitung ganz links. Es ist also eine eindeutige Grammatik.

Unterschied zwischen mehrdeutiger und eindeutiger Grammatik

Definition

Eine mehrdeutige Grammatik ist eine kontextfreie Grammatik, für die es eine Zeichenfolge gibt, die mehr als einen ganz linken Ableitungs- oder Analysebaum haben kann. Die eindeutige Grammatik ist eine kontextfreie Grammatik, für die jeder gültige String eine eindeutige Abzweigung oder einen Analysebaum ganz links hat.

Anzahl der Ableitungen ganz links

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

Fazit

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

Referenz:

1. "Mehrdeutige Grammatik". Wikipedia, Wikimedia Foundation, 17. Juli 2018,