Sastavljači: Koja je razlika između LL (0) i LR (0) parsera. Postoji li tako nešto kao LL (0) parseri?


Odgovor 1:

Čini se da je ovo pitanje usredotočeno na LL (0) analizatore, pa ćemo ih definirati. LL (0) rastavljač, raščlanjava s lijeva na desno koristeći 0 tokena na početku proizvodnje kako bi odredio koju proizvodnju primijeniti. Što znači 0 tokena, to znači da rastavljač ne može upotrijebiti tekst koji je raščlanjen da bi odredio koji će se proizvod primijeniti. To znači da parser ne može odlučiti. Mora znati prije nego što počne točno analizirati slijed tokena koji će analizirati. Morate biti fiksirani redoslijed tokena, što znači da može biti samo jedan niz koji će parser rastaviti. Tako biste mogli imati parser koji prihvaća "Pozdrav svijetu!" s gramatikom poput ove:

cilj: uskličnik "Zdravo" bijeli prostor "svijet";

Imajte na umu da su jedino dopuštene varijacije na koji se način leksera podudara sa tokenima.

(Nadam se da je oznaka očita - u osnovi je ona koju koristim u Yacc ++. Citirani nizovi su tokeni, kao i svi identifikatori koji nisu definirani.)

Parser uvijek očekuje točno isti slijed tokena. To ne mora imati samo jedno pravilo, kao što je to učinio naš prvi primjer. Moglo bi izgledati ovako.

cilj: hello-dio bijeli prostor krajnji dio;

hello-dio: hello1;

zdravo1: "Pozdrav";

krajnji dio: svjetski dio zadnji dio;

svjetski dio: "svijet";

zadnji dio: "!";

No, primijetite kako nijedno od pravila nema nijednog "ili" (|) operatora, a postoji samo jedno pravilo za ne-terminal. To je ono što omogućuje raščlanjivaču da zna kako uskladiti svako pravilo bez korištenja diskriminirajućih tokena (tokena koji biraju kojim putem parser želi), što čini gramatiku LL (0).

Je li moguće koristiti rekurzivnu proizvodnju i još uvijek imati LL (0) gramatiku? Odgovor je "ne". Pogledajmo što se događa ako imamo rekurzivno pravilo.

cilj: "x" cilj "y";

Upamtite, dozvoljeno nam je samo jedno pravilo po non-terminalu i nema "ili" operatora. Prema tome, kad dođemo do rekurzivnog zazivanja cilja, moramo nas odvesti na put kojim ćemo opet doći do tog rekurzivnog poziva, beskonačne petlje. Dokažite sebi, nije važno na koji način gnjevimo taj poziv ili je li rekurekcija neizravna. Uvijek će rezultirati beskonačnom petljom.

Dakle, gramatika LL (0) mora raščlaniti konačan popis tokena, točno jedan konačan popis (isti popis svaki put).

Primjetite razliku u značenju LR (0). LR (k) raščlanjivaču je dozvoljeno koristiti bilo koje (koliko god želi) tokene unutar produkcije radi diskriminacije, plus do k tokena iz konteksta kad se proizvodnja smanji kako bi se utvrdilo treba li smanjiti. U slučaju LR (0), ne može koristiti nikakve dodatne tokene da bi utvrdio treba li smanjiti. Mora se jednostavno odlučiti na temelju žetona u pravilu koje se smanjuje. Evo jednostavne LR (0) gramatike:

cilj: "x" | "(" cilj ")";

Ova gramatika analizira "x" okruženu nekim brojem zagrade. Imajte na umu da se pomoću tokena "x" i "(" tokena) odlučuje koje će se pravilo primijeniti. 0 u LR (0) ne ograničava upotrebu tokena unutar pravila, kao što je to slučaj u LL (0). Jedino što ograničava je upotreba tokena (konteksta, nakon pravila u nekoj uporabi koja nije terminal) kada se odlučuje na smanjenje. Ova gramatika ne treba kontekst da bi je smanjila. Na prvu alternativu smanjuje se kada vidi "x", ono se smanjuje nakon što vidi ")". Tokeni unutar pravila određuju točno kada se pravilo treba smanjiti.


Odgovor 2:

LL (0) rastavljači znače da obrađuju tok Token s lijeva na desno, koristeći izvedbu s lijeve strane bez gledanja naprijed. Teoretski, LL (0) parseri su mogući, ali čak i ako postoje, ne vidim im puno koristi. LL (0) rastavljači bi trebali predvidjeti koje će proizvodnje primijeniti na temelju trenutnog ne-terminala s nultom gledanošću naprijed. U takvim gramatikama svaki non terminal može imati samo jednu proizvodnju koja je s njim povezana i ne bi trebalo biti nikakvih rekurzija.

LR (0) rastavljači znače da obrađuju tok Token s lijeva na desno, koristeći izvedbu s desne strane i nulto gledano naprijed. To znači da grade stablo raščlanjivanja odozdo prema gore, dok LL (0) rastavljači grade parse stablo od vrha do dna.