Diferența dintre parsarea de sus în jos și de sus în sus

diferența cheie dintre parsarea de sus în jos și de jos în sus este că de sus în jos parsarea efectuează parsarea de la simbolul de așteptare la șirul de intrare în timp ce analiza de jos în jos efectuează parsarea de la șirul de intrare la simbolul de pornire. Mai mult, o altă diferență importantă între parsarea de sus în jos și de jos în sus este aceea că parsarea de sus în jos folosește cea mai mare derivare din stânga și parsarea de jos în jos folosește cea mai mare derivare.

Limbile de nivel înalt ajută la scrierea programelor de calculator. Ele sunt mai ușor de înțeles de către programator, dar nu de calculator. Prin urmare, programul de nivel înalt se convertește la codul mașinii. Sarcina compilatorului este de a converti codul sursă citit de om la codul mașinii care poate fi citit de mașină. Un program trece prin câțiva pași pentru a converti la codul mașinii. Acest întreg proces se numește Sistem de procesare a limbilor. Una dintre ele este compilația. Analizorul de sintaxă sau parserul este în compilator și efectuează sarcina de analiză.

CUPRINS

1. Prezentare generală și diferență cheie
2. Ce este parsarea de sus în jos
3. Ce este parsarea de jos în sus
4. Comparație de la o parte la alta - Top Down vs Bot Up Up parsing în formă tabulară
5. rezumat

Ce este parsarea de sus în jos?

Fiecare limbaj de programare are un set de reguli care să reprezinte limba. Analizorul de sintaxă sau parsează șirul de intrare și verifică dacă este în funcție de producțiile de gramatică. Cu alte cuvinte, gramatica ar trebui să producă șirul folosind un parabolă.

În parsarea de sus în jos, parsarea se întâmplă de la simbolul de pornire și va ajunge la șirul de introducere dat. Luați în considerare următoarele reguli de producție gramatică. Șirul de introducere (w) este cad.

S -> cAd

A -> ab / a

Parsa de analiză după parsarea de sus în jos este după cum urmează.

Figura 01: Arborele de parse 1 cu parsare de sus în jos

S produce c A d și A produce un b. Șirul este ocupat. Nu este șirul necesar. Deci, este necesar să facem backtracking, care este de a folosi celelalte alternative.

În mod similar, S produce c A d. Aplicarea celei de-a doua opțiuni pentru A va da a. Acum dă șirul necesar. Prin urmare, parser acceptă acest șir de intrare. Parsa de analiză după parsarea de sus în jos este după cum urmează.

Figura 02: Parse Tree 2 cu parsare de sus în jos

Când șirul de introducere (w) este abbcde

Luați în considerare următoarele reguli de producție gramatică.

S -> aABe

A -> Abc / b

B -> d

În parsarea de sus în jos,

S -> aABe (înlocuind A -> Abc)

S -> aAbcBe (Înlocuind A -> b)

S -> abbcBe (Înlocuind B -> d)

S -> abbcde

Înlocuirea începe cu prima variabilă din stânga și apoi cu următoarea poziție corectă și așa mai departe. Prin urmare, rezultă o metodă de derivație cea mai stângă. În plus, este important să decideți ce regulă de producție să alegeți atunci când există o variabilă.

Ce este parsarea de jos în sus?

În paranteze de sus în sus se întâmplă în alt mod. Parsarea se întâmplă de la șirul de intrare la simbolul de pornire. Luați în considerare următoarele reguli de producție gramatică și lăsați șirul de intrare să fie w ɛ cad

S -> cAd

A -> ab / a

Parsa de analiză după efectuarea analizei de jos în sus este după cum urmează.

Figura 03: pars copac cu partea de sus Up Parsing

Șirul dat este cad. A este generat de A. C, A și d se combină pentru a obține simbolul de pornire S.

Când șirul de introducere (w) este abbcde

Luați în considerare următoarele reguli de producție gramatică.

S -> aABe

A -> Abc / b

B -> d

În parsarea de jos în sus,

S -> aABe (substituind B -> d)

S -> aAde (înlocuind A -> Abc)

S -> aAbcde (Substring A -> b)

S -> abbcde

Înlocuirea începe cu cea mai mare variabilă prima și apoi se mută la următoarea poziție stânga și așa mai departe. Prin urmare, urmează o metodă de derivație st left mot.

Care este diferența dintre parsarea de sus în jos și de jos în sus?

Sistemul de parsare de sus în jos este o strategie de analiză care privește mai întâi la cel mai înalt nivel al arborelui de analiză și lucrează în jos pe arborele de parse folosind regulile unei gramatici formale. Procesarea parțială este o strategie de analiză care privește mai întâi la nivelul cel mai de jos al arborelui de analiză și execută arborele de parse folosind regulile unei gramatici formale. Parsarea are loc de la simbolul de pornire la șirul de intrare, în parsarea de sus în jos. Pe de altă parte, parsarea are loc de la șirul de introducere la simbolul de pornire, în parsarea de sus în jos.

În plus, decizia principală în parsarea de sus în jos este de a selecta ce regulă de producție să se utilizeze pentru a construi șirul, în timp ce decizia principală în parsarea în jos este să selectați când să utilizați o regulă de producție pentru a reduce șirul pentru a obține simbolul de pornire. Mai mult decât atât, parsarea de sus în jos folosește cele mai multe derivații din stânga și analiza de jos în jos utilizează cea mai mare derivare.

Rezumat - parsarea de sus în jos și sus

Diferența dintre parsarea de sus în jos și de jos în sus este că parsarea de sus în jos efectuează parsarea de la simbolul staring la șirul de intrare în timp ce analiza de jos în jos efectuează parsarea de la șirul de intrare la simbolul de pornire.

Referinţă:

1. "Prelegeri de proiectare a compilatorului 5 - Introducere în parser și LL (1) parsare." Compilar Design Lecture 5 - Introducere în parser și LL (1) Parsing, Prelegeri de poarta de Ravindrababu Ravula, 22 mai 2014. Disponibil aici