Analiza în jos

Analiza de sus în jos este una dintre metodele pentru a determina dacă un șir de intrare aparține unui limbaj formal descris de gramatica fără context LL(k) . Aceasta este o clasă de algoritmi de analiză gramaticală , în care regulile unei gramatici formale sunt extinse începând de la caracterul de început până când se obține secvența necesară de jetoane .

Ideea metodei

Pentru fiecare simbol non-terminal K , se construiește o funcție care, pentru orice cuvânt de intrare x , face 2 lucruri:

Găsește cel mai mare început z al unui cuvânt x care poate fi începutul unui cuvânt derivat din K
Determină dacă originea z este dedusă din K

O astfel de funcție trebuie să îndeplinească următoarele criterii:

citiți din fluxul de intrare încă neprocesat începutul maxim al lui A , care este începutul unui cuvânt ieșit din K
determinați dacă A este derivat din K sau pur și simplu începutul nederivabil al unui cuvânt care poate fi derivat din K

Dacă un astfel de început nu poate fi calculat (și se dovedește corectitudinea funcției pentru nonterminalul K ), atunci datele de intrare nu corespund limbajului, iar analizarea ar trebui oprită.

Analiza constă în apelarea funcțiilor descrise mai sus. Dacă există o regulă compusă pentru non-terminalul citit, atunci când este analizat, vor fi apelate și alte funcții pentru a analiza terminalele incluse în acesta. Un arbore de apeluri care începe de la funcția „sus” este echivalent cu un arbore de analiză.

Cea mai simplă și mai „umană” modalitate de a crea un parser folosind metoda de coborâre recursivă este programarea directă pentru fiecare regulă de inferență pentru non-terminale gramaticale.

Condiții de utilizare

Fie N un set finit de simboluri non-terminale într-o gramatică formală dată; Σ este un set finit de simboluri terminale, atunci metoda de coborâre recursivă este aplicabilă numai dacă fiecare regulă a acestei gramatici are următoarea formă:

sau , unde , și aceasta este singura regulă de ieșire pentru acest non-terminal $A\săgeată la dreapta\alpha$ $\alpha \subset (\Sigma \cup N)*$
sau pentru toti $A\rightarrow a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$ $i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$

Algoritmi de analiză de sus în jos

Analizator recursiv de coborâre ( en:Recursive descent parser )
Analizor LL ( en:LL parser )
Junk Parser ( en:Packrat parser )

Literatură

A. Shen . Programare: teoreme și probleme. Ed. a II-a, M.: MTsNMO, 2004
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilatoare: principii, tehnici și instrumente = Compilers: Principles, Techniques, and Tools. - Ed. a II-a. - M .: Williams , 2008. - ISBN 978-5-8459-1349-4 .
Robin Hunter. Concepte de bază ale compilatorului = Esența compilatorilor. - M . : „Williams” , 2002. - S. 256. - ISBN 5-8459-0360-2 .