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 limbajul natural, și în limbajele de programare.
Aplicare în limbajele de programare
modificareUn compilator analizează datele de intrare dintr-un limbaj de programare pentru a construi 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:
va începe cu și apoi va încerca să aleagă dintre . După aceasta, va continua cu . 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).