Koostajad: erinevus LL (0) ja LR (0) parserite vahel. Kas on olemas selline asi nagu LL (0) parsijad?


Vastus 1:

See küsimus näib olevat keskendunud LL (0) parseritele, nii et määratlegem need. LL (0) parser sõelub vasakult paremale, kasutades 0 tokenit tootmise alguses, et otsustada, millist toodangut kasutada. Mida see 0 märki tähendab, tähendab see, et parser ei saa parsitavat teksti kasutada määramaks, millist toodangut rakendada. See tähendab, et parsija ei saa mingeid valikuid teha. Enne kui ta hakkab parsima täpselt selle märgise jada, peab ta teadma. Tokenide jada peab olema fikseeritud, mis tähendab, et parsija saab sõeluda ainult ühte jada. Seega võiks teil olla parser, mis aktsepteerib kirja "Tere maailm!" sellise grammatikaga:

eesmärk: "Tere" tühimärk "maailm" hüüumärk;

Pange tähele, et ainsad lubatud variatsioonid on see, kuidas lexer sobib märkidega.

(Loodan, et märge on ilmne - see on põhimõtteliselt see, mida kasutan Yacc ++-s. Tsiteeritud stringid on märgid, nagu ka kõik määratlemata identifikaatorid.)

Parser eeldab alati täpselt sama žetoonide jada. See ei pea sisaldama ainult ühte reeglit, nagu tegi meie esimene näide. See võib välja näha selline.

eesmärk: tere-osa tühiku lõpp-osa;

tere-osa: tere1;

tere1: "Tere";

lõpposa: maailmaosa viimane osa;

maailmaosa: "maailm";

viimane osa: "!";

Pange aga tähele, kuidas ühelgi reeglil pole ühtegi "või" (|) operaatorit ja mitteterminali kohta on ainult üks reegel. See võimaldab parseril teada, kuidas iga reeglit kokku sobitada, ilma et oleks vaja kasutada diskrimineerivaid märke (žetoonid, mis valivad, mida mööda parser läheb), mis muudab grammatika LL (0).

Kas on nüüd võimalik kasutada rekursiivset lavastust ja ikkagi LL (0) grammatikat? Vastus on "ei". Vaatame, mis juhtub, kui meil on rekursiivne reegel.

eesmärk: "x" eesmärk "y";

Pidage meeles, et ühe terminali kohta on meil lubatud ainult üks reegel ja mitte ühtegi operaatorit. Seega, kui jõuame eesmärgi rekursiivse kutsumiseni, peame minema meid teele, kus jõuame taas selle rekursiivse kutsumiseni, lõpmatu silmus. Tõestage endale, pole tähtis, kuidas me selle kutsumise pesame või kas rekursioon on kaudne. Selle tulemuseks on alati lõpmatu silmus.

Seega peab LL (0) grammatika parsima tokenide piiratud nimekirja, täpselt ühe piiratud nimekirja (iga kord sama loetelu).

Pange tähele erinevust LR (0) tähenduses. LR (k) parseril on lubatud diskrimineerimiseks kasutada mis tahes (nii palju kui talle meeldib) tokenid lavastuses, pluss kuni k tokenit kontekstist, kui lavastus väheneb, et teha kindlaks, kas see peaks vähendama. LR (0) juhul ei saa ta kasutada täiendavaid märke, et teha kindlaks, kas see peaks vähendama. See peab olema lihtsalt otsustatud, tuginedes vähendatud reegli märkidele. Siin on lihtne LR (0) grammatika:

eesmärk: "x" | "(" eesmärk ")";

See grammatika parsib "x", mis on ümbritsetud mõne arvu sulgudega. Pidage meeles, et selle määramiseks võib kasutada tähist "x" ja "(".) (LR (0) 0 ei piira reegli piires lubade kasutamist, nagu seda teeb 0 LL-is (0). Ainus, mida see piirab, on vähendamise otsustamisel märkide (kontekstis pärast reeglit mõnes mitteterminali kasutamises) kasutamine. Selle grammatika jaoks pole kontekstit vaja vähendada. Esimese variandina vähendab see nägemisel "x" teisel juhul vähendab see pärast ")" nägemist. Reeglis olevad märgid määravad täpselt, millal reegel peaks vähenema.


Vastus 2:

LL (0) parserid tähendavad, et nad töötlevad sümboolivoogu vasakult paremale, kasutades vasakpoolset tuletist ilma tulevikku vaatamata. Teoreetiliselt on LL (0) parserid võimalikud, kuid isegi kui need olemas on, ei näe ma neist palju kasu. LL (0) parserid peaksid ennustama, milliseid produktsioone rakendada, lähtudes praegusest mitteterminalist, millel on null tulevik. Sellistes grammatikates võib igal mitteterminalil olla seotud ainult üks lavastus ja rekursiooni ei tohiks olla.

LR (0) parserid tähendavad, et nad töötlevad tokeni voogu vasakult paremale, kasutades parempoolseimat tuletust, nullist ette vaadates. See tähendab, et nad ehitavad parsipuu alt üles, samas kui LL (0) parserid ehitavad parsipuu ülevalt alla.