The hlavný rozdiel medzi nejednoznačnou a jednoznačnou gramatikou je to, že nejednoznačná gramatika je bezkontextová gramatika, pre ktorú existuje reťazec, ktorý môže mať viac ako jednu deriváciu úplne vľavo, zatiaľ čo jednoznačná gramatika je bezkontextová gramatika, pre ktorú má každý platný reťazec jedinečnú deriváciu úplne vľavo.

Gramatika sa týka syntaktických pravidiel v prirodzených jazykoch. V roku 1956 predstavili počítačoví vedci matematický model gramatiky na písanie počítačového jazyka. Ak je možné odvodiť všetky reťazce jazyka pomocou určitej gramatiky, potom sa hovorí, že jazyk je generovaný z tejto gramatiky. Bezkontextová gramatika je jedným z typov gramatiky. Táto gramatika generuje bezkontextový jazyk. Gramatika bez kontextu môže byť nejednoznačná alebo jednoznačná. Ak pre konkrétny reťazec existujú dve alebo viac derivácií, táto gramatika je údajne nejednoznačná. Ak pre konkrétny reťazec existuje iba jedinečná derivácia úplne vľavo, hovorí sa, že gramatika je jednoznačná gramatika.

Nejasná gramatika, jednoznačná gramatika

Čo je nejednoznačná gramatika

Gramatika je údajne nejednoznačná, ak existujú dve alebo viac derivácií pre reťazec.

Obrázok 1: Nejasná gramatika

Predpokladajme, že existuje gramatika definovaná nasledovne.

G = ({S}, {a+b,+, *}, P, S}. Výrobné pravidlá sú nasledujúce. S -> S+S | S *S | a | b. Predpokladajme, že je potrebné vygenerujte reťazec a+ a*b.

Uvažujme, S -> S+S

Nahradením „a“ ľavou väčšinou S získate nasledujúce.

S-> a +S

Náhrada S*S za S je nasledovná.

S-> a + S*S

Nahradením „a“ za ľavú časť S získate nižšie uvedený výstup.

S -> a+ a*S

Nahradením „b“ za S získate nasledujúci výstup.

S -> a + a * b

Toto je požadovaný reťazec na vygenerovanie.

Pri použití druhého produkčného pravidla to dá

S -> S* S

Použiť S+S doľava, S poskytne nasledujúce.

S -> S+S * S

Náhrada za „a“ za väčšinu S,

S -> a + S*S

Náhradou „a“ za ľavú S,

S -> a + a * S

Nahradením „b“ za S získate nasledujúci výstup.

S -> a + a*b

Opäť vygenerovalo požadovaný reťazec. Preto existuje viac ako jedna derivácia na generovanie reťazca. Preto je to nejednoznačná gramatika.

Čo je to jednoznačná gramatika

V nejednoznačnej gramatike má určitý reťazec jedinečnú deriváciu úplne vľavo. Pozrite sa na nasledujúce výrobné pravidlá.

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

Zvážte pravidlo S -> L. Náhradník LS namiesto L.

S -> LS

Náhradník S, prvý L.

S -> S S

Nahradením „a“ za ľavú stranu S získate nižšie uvedený výstup.

S -> a S

Nahradením „a“ za S získate nasledujúce.

S -> a a

Preto má reťazec jedinečnú deriváciu úplne vľavo. Ide teda o jednoznačnú gramatiku.

Rozdiel medzi nejednoznačnou a jednoznačnou gramatikou

Definícia

Nejednoznačná gramatika je bezkontextová gramatika, pre ktorú existuje reťazec, ktorý môže mať viac ako jednu deriváciu alebo analýzu stromov úplne vľavo. Jednoznačná gramatika je bezkontextová gramatika, pre ktorú má každý platný reťazec jedinečný derivačný alebo syntaktický strom úplne vľavo.

Počet derivácií úplne vľavo

V nejednoznačnej gramatike môže reťazec mať dve alebo viac derivácií úplne vľavo, ale v jednoznačnej gramatike má reťazec jedinečnú deriváciu úplne vľavo.

Záver

Bezkontextová gramatika môže byť nejednoznačná alebo jednoznačná. Rozdiel medzi nejednoznačnou a jednoznačnou gramatikou je ten, že nejednoznačná gramatika je bezkontextová gramatika, pre ktorú existuje reťazec, ktorý môže mať viac ako jednu deriváciu úplne vľavo, zatiaľ čo jednoznačná gramatika je bezkontextová gramatika, pre ktorú má každý platný reťazec jedinečnú deriváciu úplne vľavo..

Referencia:

1. „Nejednoznačná gramatika“. Wikipedia, Wikimedia Foundation, 17. júla 2018, k dispozícii tu.2. „Návrh kompilátora | Nejasná gramatika. " GeeksforGeeks, 10. februára 2018, k dispozícii tu. „Ambiguous Grammar“, Neso Academy, 29. marca 2017, k dispozícii tu.

Obrázok so súhlasom:

1.