De grootste verschil tussen ambigue en ondubbelzinnige grammatica is dat de ambigue grammatica is een contextvrije grammatica waarvoor een string bestaat die meer dan één meest linkse afleiding kan hebben, terwijl een ondubbelzinnige grammatica een contextvrije grammatica is waarvoor elke geldige string een unieke meest linkse afleiding heeft.

Grammatica verwijst naar de syntactische regels in natuurlijke talen. In 1956 introduceerden computerwetenschappers een wiskundig model van grammatica voor het schrijven van computertaal. Als het mogelijk is om alle strings van een taal af te leiden met behulp van een bepaalde grammatica, dan wordt gezegd dat de taal uit die grammatica wordt gegenereerd. Contextvrije grammatica is één type grammatica. Deze grammatica genereert contextvrije taal. De contextvrije grammatica kan dubbelzinnig of ondubbelzinnig zijn. Als er voor een bepaalde string twee of meer afleidingen zijn, wordt gezegd dat die grammatica dubbelzinnig is. Als er voor een bepaalde string een enige unieke meest linkse afleiding is, wordt gezegd dat die grammatica ondubbelzinnige grammatica is.

Dubbelzinnige grammatica, ondubbelzinnige grammatica

Wat is ambigue grammatica?

Een grammatica wordt ambigu genoemd als er twee of meer afleidingen voor een string bestaan.

Figuur 1: Dubbelzinnige grammatica

Neem aan dat er een grammatica is die als volgt is gedefinieerd.

G= ({S}, {a+b, +, *}, P, S}. De productieregels zijn als volgt: S -> S+S | S*S | a | b. Neem aan dat het nodig is om genereer de String a+ a*b.

Overweeg, S -> S+S

Het vervangen van 'a' voor de meeste linkse S geeft het volgende.

S-> een +S

Het substitueren van S*S voor S is als volgt.

S-> a + S*S

Als u 'a' vervangt door de meest linkse S, krijgt u de onderstaande uitvoer.

S -> a+ a*S

Het vervangen van 'b' voor de S geeft de volgende uitvoer.

S -> a + a * b

Dit is de vereiste tekenreeks om te genereren.

Bij gebruik van de andere productieregel geeft het:

S -> S* S

S+S toepassen op de meest linkse S geeft het volgende.

S -> S+S * S

Vervang 'a' voor meest linkse S,

S -> a + S*S

Vervanging van 'a' voor de meest linkse S,

S -> a + a * S

Het vervangen van 'b' voor S geeft de volgende uitvoer.

S -> a + a*b

Nogmaals, het genereerde de vereiste string. Daarom is er meer dan één afleiding om de string te genereren. Daarom is het een dubbelzinnige grammatica.

Wat is ondubbelzinnige grammatica?

In een dubbelzinnige grammatica heeft een bepaalde string een unieke meest linkse afleiding. Raadpleeg de volgende productieregels.

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

Overweeg de S -> L-regel. Vervang LS in plaats van L.

S -> LS

Vervang S, voor eerste L.

S -> S S

Als u 'a' vervangt door de meest linkse S, krijgt u de onderstaande uitvoer.

S -> een S

Als u 'a' vervangt door S, krijgt u het volgende.

S -> een a

Daarom heeft een string een unieke meest linkse afleiding. Het is dus een eenduidige grammatica.

Verschil tussen dubbelzinnige en ondubbelzinnige grammatica

Definitie

Een ambigue grammatica is een contextvrije grammatica waarvoor een string bestaat die meer dan één meest linkse afleiding of ontleden bomen kan hebben. Ondubbelzinnige grammatica is een contextvrije grammatica waarvoor elke geldige tekenreeks een unieke meest linkse afleiding of ontledingsboom heeft.

Aantal meest linkse afleidingen

In ambigue grammatica kan een string twee of meer meest linkse afleidingen hebben, maar in ondubbelzinnige grammatica heeft een string een unieke meest linkse afleiding.

Conclusie

Contextvrije grammatica kan dubbelzinnig of ondubbelzinnig zijn. Het verschil tussen ambigue en ondubbelzinnige grammatica is dat de ambigue grammatica een contextvrije grammatica is waarvoor een string bestaat die meer dan één meest linkse afleiding kan hebben, terwijl een ondubbelzinnige grammatica een contextvrije grammatica is waarvoor elke geldige string een unieke meest linkse afleiding heeft.

Verwijzing:

1. "Ambigue grammatica." Wikipedia, Wikimedia Foundation, 17 juli 2018, hier beschikbaar.2. "Compilerontwerp | Dubbelzinnige grammatica.” GeeksforGeeks, 10 februari 2018, hier beschikbaar.3. "Ambiguous Grammar", Neso Academy, 29 maart 2017, hier beschikbaar.

Afbeelding met dank aan:

1. "Leftmostderivations jaredwf" door Jaredwf op Engelse Wikipedia - Overgezet van en.wikipedia naar Commons door EdwardHades (Public Domain) via Commons Wikimedia