Gramatică ambiguă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 noiembrie 2014; verificările necesită 5 modificări .

În informatică , o gramatică ambiguă este o gramatică formală care poate genera un șir dat în mai multe moduri (adică există mai mult de un arbore de analiză pentru un șir). Se spune că o limbă este în esență ambiguă dacă poate fi generată numai de gramatici ambigue.

Gramaticile unor limbaje de programare sunt ambigue. La analizarea unor astfel de limbi, trebuie luate în considerare informațiile semantice pentru a selecta varianta corectă. De exemplu, în limbajul C următoarea intrare:

X y;

poate fi interpretat ca:

declararea unui identificator y de tip pointer -to- x, sau
o expresie în care xse înmulțește cu yși rezultatul este ignorat.

Pentru a alege între aceste interpretări, compilatorul trebuie să consulte tabelul de simboluri pentru a vedea dacă declarația xa fost un nume de tip tip într-un domeniu dat.

Exemplu

Gramatică fără context

A → A + A | A − A | A

este ambiguă, deoarece există două ieșiri din stânga pentru șirul a + a + a:

A	→A+A	A	→A+A
	→ a+A		→A+A+A
	→ a+A+A		→ a+A+A
	→ a+a+A		→ a+a+A
	→ a + a + a		→ a + a + a

De asemenea, gramatica este ambiguă deoarece există doi arbori de analiză pentru șirul a + a - a:

Cu toate acestea, limbajul pe care îl generează nu este în esență ambiguu, deoarece următoarea gramatică neambiguă generează aceeași limbă:

A → A + a | A − a | A

Recunoașterea gramaticii ambigue

Problema generală de a determina dacă o gramatică este ambiguă este algoritmic indecidabilă . Nu poate exista un algoritm care să determine ambiguitatea unei gramatici, deoarece problema de corespondență de nerezolvată a lui Post se reduce la o problemă de ambiguitate.

Există o dificultate evidentă în analizarea unei gramatici ambigue cu un parser determinist , dar analiza nedeterministă are ca rezultat o pierdere semnificativă a eficienței. Majoritatea constructelor care necesită parsare pot fi recunoscute prin gramaticile lipsite de ambiguitate. Unele gramatici ambigue pot fi convertite în gramatici neechivoce, dar nu există o procedură generală pentru această conversie, la fel cum nu există un algoritm pentru determinarea ambiguității unei gramatici. Generatoarele de compilatoare , cum ar fi YACC , sunt capabile să dezambiguizeze anumite tipuri, de exemplu, folosind constrângeri de precedență și asociativitate .

Limbi semnificativ ambigue

În timp ce unele limbi (seturi de șiruri generate de o gramatică) au atât gramatici clare, cât și ambigue, există limbi pentru care nu există o gramatică clară. Un exemplu de limbaj esențial ambiguu este unirea lui și . Este un limbaj fără context, ca o amalgamare a limbilor fără context, dar Introducerea în Teoria Automatelor... conține dovada că nu este posibilă analiza unică a șirurilor în submulțimea (fără context) care este intersecția celor două limbi. $\{a^{n}b^{m}c^{m}d^{n}|n,m>0\)$ $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\))$

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami