Vizualizare sursă pentru „Parsare top-down”

'''Parsarea top-down''' este o strategie de analiză de date necunoscute prin construirea unor structuri generale de arbori de parsare ipotetice și apoi deciderea dacă structurile fundamentale cunoscute sunt sau nu compatibile cu ipoteza. Această strategie apare și în [[Limbaj natural|limbajul natural]], și în [[limbaj de programare|limbajele de programare]].

==Aplicare în limbajele de programare==
Un [[compilator]] analizează datele de intrare dintr-un limbaj de programare pentru a construi [[Limbaj de asamblare|limbajul de asamblare]] sau o reprezentare internă prin potrivirea simbolurilor din intrare cu regulile de producție în forma Backus-Naur. Un [[parser LL]], numit și '''parser top-down''', aplică fiecare regulă de producție simbolurilor intrate, lucrând de la cel mai din stânga simbol generat de o regulă de producție și apoi continuând cu următoarea regulă de producție pentru fiecare neterminal întâlnit. În acest fel, parsarea începe din stânga rezultatului regulii de producție (partea dreaptă) și evaluează neterminalii începând cu stânga și, deci, coboară în arborele de parsare pentru fiecare neterminal nou înainte să continue cu următorul simbol pentru o regulă de producție.

De exemplu:

* <math>A \rightarrow aBC</math>
* <math>B \rightarrow c|cd</math>
* <math>C \rightarrow df|eg</math>

va începe cu <math>A \rightarrow aBC</math> și apoi va încerca să aleagă dintre <math>B \rightarrow c|cd</math>. După aceasta, va continua cu <math>C \rightarrow df|eg</math>. Așa cum este de așteptat, unele limbaje sunt mai ambigue decât altele. Pentru un lumbaj neambiguu, în care toate producțiile unui neterminal sunt cuvinte distincte: cuvântul generat de o producție nu începe cu același simbol cu care începe alt cuvânt generat de orice altă producție. Un limbaj neambiguu poate fi descris de către o [[gramatică]] LL(1), unde (1) semnifică faptul că parserul inspectează doar câte un simbol deodată. Pentru un limbaj ambiguu, un parser LL trebuie să inspecteze mai mult de un simbol, de exemplu LL(3).

Soluția obișnuită este utilizarea unui [[parser LR]] (cunoscut și ca parser bottom-up sau deplasare-reducere).

==Vezi și==
* [[Parsare bottom-up]]

[[Categorie:Algoritmi de parsare]]