Diferența dintre gramatica ambiguă și lipsită de ambiguitate

principala diferență între gramatica ambiguă și lipsită de ambiguitate este aceea că gramatica ambiguă este o gramatică liberă pentru context pentru care există un șir care poate avea mai mult de o derivare la stânga, în timp ce o gramatică lipsită de ambiguitate este o gramatică fără context pentru care fiecare șir valid are o derivare unică la stânga. 

Gramatica se referă la regulile sintactice din limbile naturale. În 1956, oamenii de știință au introdus un model matematic de gramatică pentru scrierea limbajului calculatorului. Dacă este posibil să se deducă toate șirurile unei limbi utilizând o anumită gramatică, atunci se spune că limba este generată de acea gramatică. Context gramatica este un tip de gramatica. Această gramatică generează limbaj fără context. Gramatica liberă a contextului poate fi ambiguă sau lipsită de ambiguitate. Pentru un șir special, dacă există două sau mai multe derivații, se consideră că gramatica este ambiguă. Pentru un șir special, dacă există o singură derivare unică la stânga, se consideră că gramatica este o gramatică neechivocă.

Domenii cheie acoperite

1. Ce este gramatica ambiguă
     - Definiție, exemplu
2. Ce este gramatica neechivocă
     - Definiție, exemplu
3. Diferența dintre gramatica ambiguă și lipsită de ambiguitate
     - Compararea diferențelor cheie

Termeni cheie

Gramatica ambiguă, gramatica neechivocă

Ce este gramatica ambiguă

Se spune că o gramatică este ambiguă dacă există două sau mai multe derivări pentru un șir.

Figura 1: Gramatica ambiguă

Să presupunem că există o gramatică definită după cum urmează.

G = (S, a + b, +, *, P, S Regulile de producție sunt după cum urmează: S -> S + S | generați String a + a * b.

Luați în considerare, S -> S + S

Înlocuirea cu "a" pentru cea mai mare stânga S va da următoarele.

S-> a + S

Substituirea lui S * S pentru S este după cum urmează.

S-> a + S * S 

Înlocuirea cu "a" pentru cea mai mare stânga S va da rezultatul de mai jos.

S -> a + a * S

Înlocuirea cu "b" pentru S va da următoarea ieșire.

S -> a + a * b

Acesta este șirul necesar pentru generare.

Atunci când se utilizează regula de producție, se va da

S -> S * S

Aplicați S + S spre stânga cel mai mult S va da următoarele.

S -> S + S * S

Înlocuiți "a" pentru cea mai mare stânga S,

S -> a + S * S

Înlocuind "a" pentru cea mai mare stânga S,

S -> a + a * S

Înlocuirea cu "b" pentru S va da următoarea ieșire.

S -> a + a * b

Din nou, a generat șirul necesar. Prin urmare, există mai multe derivări pentru a genera șirul. Prin urmare, este o gramatică ambiguă.

Ce este gramatica neechivocă

Într-o gramatică ambiguă, un anumit șir are o derivare unică la stânga. Consultați următoarele reguli de producție.

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

Luați în considerare regula S -> L. Înlocuiți LS în loc de L.

S -> LS

Înlocuitorul S, pentru primul L.

S -> S S

Înlocuirea cu "a" pentru cea mai din stânga S va da rezultatul de mai jos.

S -> a S

Înlocuirea cu "a" pentru S va da următoarele.

S -> a a

Prin urmare, un șir are o derivare unică la stânga. Deci, este o gramatică neechivocă.

Diferența dintre gramatica ambiguă și lipsită de ambiguitate

Definiție

O gramatică ambiguă este o gramatică liberă pentru context pentru care există un șir care poate avea mai mult de o singură derivație din stânga sau parabolă. Gramatica lipsită de ambiguitate este o gramatică fără context pentru care fiecare șir valid are o derivare unică la stânga sau parabolă.

Numărul de derivații din stânga

În gramatica ambiguă, un șir poate avea două sau mai multe derivări stângi, dar, în gramatică neechivocă, o șir are o derivare unică la stânga.

Concluzie

Context gramatica liberă poate fi ambiguă sau lipsită de ambiguitate. Diferența dintre gramatica ambiguă și lipsită de ambiguitate este aceea că gramatica ambiguă este o gramatică liberă pentru context pentru care există un șir care poate avea mai mult de o derivare la stânga, în timp ce o gramatică neambiguă este o gramatică fără context pentru care fiecare șir valid are o derivare unică la stânga. 

Referinţă:

1. "Gramatica ambiguă". Wikipedia, Fundația Wikimedia, 17 iulie 2018, disponibil aici.
2. "Proiectarea compilatoarelor" Gramatica ambiguă. "GeeksforGeeks, 10 februarie 2018, disponibil aici.
3. "Gramatica ambiguă", Academia Neso, 29 martie 2017, disponibil aici.

Datorită fotografiei:

1. "Drepturile de stânga jaredwf" De Jaredwf în engleză Wikipedia - Transferat de la en.wikipedia la Commons de EdwardHades (Public Domain) prin Wikimedia Wikimedia