Katso myös LL(1)
LL-jäsennin ( LL-jäsennin ) on tietojenkäsittelytieteen ylhäältä alas -jäsennin yhteydettömien kielioppien osajoukolle, joka tunnetaan nimellä LL-kielioppi . Kaikki yhteydettömät kieliopit eivät kuitenkaan ole LL-kielioppeja.
L-kirjaimet lausekkeessa "LL parser" tarkoittavat, että syötemerkkijono jäsennetään vasemmalta oikealle, ja samalla rakennetaan sen vasemmanpuoleisin johdannainen .
LL-jäsennintä kutsutaan LL(k)-jäsentimeksi, jos tämä jäsentäjä käyttää ennakointia k tokenille (tokenille) jäsennettäessä syöttövirtaa. Kielioppia, jonka LL(k)-jäsennin voi tunnistaa ilman paluuta, kutsutaan LL(k)-kieliopiksi. Kieltä, joka voidaan esittää LL(k)-kieliopina, kutsutaan LL(k)o-kieleksi. On olemassa LL(k+n)-kieliä, jotka eivät ole LL(k)-kieliä.
Seuraavassa kuvataan analysaattoria, joka perustuu taulukoiden rakenteeseen; vaihtoehto on rekursiivinen laskeva jäsentäjä, joka kirjoitetaan yleensä käsin (vaikka poikkeuksiakin on, kuten ANTLR- jäsenningeneraattori LL(*)-kielioppeille).
LL(1)-kieliopit ovat hyvin yleisiä, koska niitä vastaavat LL-jäsentimet katsovat virtaa vain yhden merkin eteenpäin päättäessään, mitä kielioppisääntöä sovelletaan. Suuria k-arvoja sisältäviin kielioppiin perustuvia kieliä on perinteisesti pidetty vaikeasti tunnistettavissa, vaikka yleisen käytön myötä LL(k)-kielioppeja, joissa on mielivaltainen k, tämä huomautus ei ole enää relevantti.
LL-jäsennintä kutsutaan LL(*)-jäsentimeksi, jos k:lle ei ole tiukkaa rajoitusta ja jäsentäjä tunnistaa kielen, jos merkit kuuluvat johonkin säännölliseen joukkoon (esimerkiksi käyttämällä deterministisiä äärellisiä automaatteja ).
LL-kielioppeihin perustuvan niin sanotun "eurooppalaisen koulukunnan" ja LR-kielioppeja suosivan "amerikkalaisen koulukunnan" välillä on ristiriitoja. Tällaiset ristiriidat johtuvat opetuksen perinteistä ja erilaisten menetelmien ja työkalujen kuvauksen yksityiskohdista tietyissä oppikirjoissa; vaikutteita myös N. Wirth of ETHZ , jonka tutkimuksessa kuvataan erilaisia menetelmiä LL(1)-selvittimien ja kääntäjien optimoimiseksi.
Jäsentäjä on suunniteltu ratkaisemaan ongelma, kuuluuko merkkijono tiettyyn kielioppiin, ja rakentamaan tulospuu, jos kuuluu.
Jäsentäjä koostuu:
Taulukon riveillä on kaupan aakkosten symbolit ja sarakkeissa - pääteaakkosten symbolit.
Kun jäsentäminen alkaa, pinossa on jo kaksi merkkiä:
[ S, $ ]Missä "$" on erityinen pääte, jota käytetään osoittamaan pinon loppua, ja "S" on kieliopin aksiooma. Jäsentäjä yrittää kielioppisääntöjen avulla korvata pinon aksiooman merkkijonolla, joka on samanlainen kuin syöttönauhan merkkijono, ja sitten lukea nauhan kokonaan tyhjentäen pinon.
Selvittääksesi, miten LL-jäsennin toimii, harkitse seuraavaa kielioppia:
Ja analysoidaan jäsentämistä merkkijonon esimerkissä:
(1+1)Tämän kieliopin jäsennystaulukko näyttää tältä:
| ( | ) | yksi | + | $ | |
| S | 2 | — | yksi | - | - |
| F | — | — | 3 | - | - |
Siellä on myös sarake erityistä terminaalia varten, jota merkitään $, jota käytetään osoittamaan tulovirran loppua. Soluissa olevat numerot (lihavoidut tekstit) osoittavat yllä mainittujen sääntöjen numeroita.
Jäsentäjä katsoo ensimmäistä merkkiä '(' syöttövirrasta, sillä hetkellä merkki 'S' on pinon päällä, jäsennystaulukon arvojen leikkauskohdassa on kieliopin sääntö Tässä esimerkissä tämä on sääntö numero 2, joka käskee korvaamaan pinossa merkin "S" merkkijonossa "(S + F)". Pinon tila tämän säännön soveltamisen jälkeen on:
[ (, S, +, F, ), $ ]Seuraavassa vaiheessa analysaattori lukee merkin '(' syöttövirrasta. Koska pinon yläosassa on samanlainen merkki '('), tämä merkki luetaan nauhalta ja poistetaan pinosta. pino tämän säännön soveltamisen jälkeen on:
[S, +, F, ), $]Seuraavaksi nauhalla on symboli '1' ja pinon 'S' yläosassa, näiden taulukon symbolien leikkauskohdassa, on sääntö 1. Tämän säännön soveltamisen jälkeen taulukon mukaan analysaattori soveltaa sääntö 3. Pinon tila sääntöjen soveltamisen jälkeen:
[ F, +, F, ), $ ] [ 1, +, F, ), $ ]Seuraavaksi jäsentäjä lukee '1' ja '+' syöttövirrasta ja, koska ne vastaavat kahta seuraavaa pinon elementtiä, myös poistaa ne pinosta. Tämän seurauksena pino näyttää tältä:
[ F, ), $ ]Seuraavissa kolmessa vaiheessa pinon merkki 'F' muutetaan 1:ksi, minkä jälkeen merkit '1' ja ')' luetaan nauhalta ja poistetaan pinosta. Tämän seurauksena symboli '$' tulee pinon päälle ja nauhalle, määritelmän mukaan tämä tarkoittaa onnistunutta ketjun jäsentämistä.
Tässä tapauksessa analysaattori raportoi onnistumisesta ja palauttaa luettelon säännöistä, joita sovellettiin päättelyprosessin aikana:
[2, 1, 3, 3]Nämä säännöt ovat todellakin vasemmanpuoleisia päätelmiä:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Kuten esimerkistä näkyy, jäsentäjä tekee kolme eri asiaa riippuen siitä, onko pinon yläosa ei-pääte, pääte vai $-erikoismerkki:
Näitä vaiheita toistetaan, kunnes pysähdys tapahtuu. Pysähdyksen jälkeen saamme joko virheilmoituksen tai viestin, että ketju tunnistettiin onnistuneesti.
Jäsennystaulukon täyttämiseksi on tarpeen määrittää, mikä kielioppisääntö jäsentimen tulee valita, jos ei-pääte A on pinon yläosassa ja merkki a on syöttövirrassa. On helppo nähdä, että tällaisen säännön on oltava muotoa A → w ja että w : tä vastaavassa kielessä on oltava vähintään yksi a :lla alkava rivi . Tätä tarkoitusta varten määritämme ensimmäisen joukon w , joka kirjoitetaan tähän Fi(w) :ksi joukoksi päätteitä, jotka löytyvät minkä tahansa w :n rivin alusta , ja ε, jos tyhjä rivi kuuluu myös riviin w . Kun annetaan kielioppi, jossa on säännöt A 1 → w 1 , …, A n → w n , jokaiselle säännölle voidaan laskea Fi(w i ) ja Fi(A i ) seuraavasti:
Valitettavasti ensimmäiset joukot eivät riitä jäsennystaulukon rakentamiseen. Tämä johtuu siitä, että säännön oikea puoli w voidaan lopulta heittää tyhjään merkkijonoon. Jäsentimen tulee siis käyttää myös sääntöä A → w , jos ε on Fi(w) :ssä ja syöttövirrassa merkki, joka voi seurata A: ta . Siksi on myös tarpeen rakentaa Seuraava joukko A (tässä kirjoitettu Fo(A) ), joka määritellään joukoksi terminaaleja a siten, että on merkkijono αAaβ , joka voidaan saada alkumerkistä. Seuraavien joukkojen laskeminen kieliopin ei-päätteille voidaan tehdä seuraavasti:
Nyt voit määrittää tarkalleen, mitkä säännöt sisältyvät jäsennystaulukkoon. Jos T[A, a] merkitsee merkintää taulukossa ei-päätteelle A ja terminaalille a , niin
T[A,a] sisältää säännön A → w silloin ja vain jos:
Jos taulukko sisältää enintään yhden säännön kussakin solussa, jäsentäjä voi yksiselitteisesti määrittää, mitä sääntöä on sovellettava kussakin jäsennysvaiheessa. Tässä tapauksessa kielioppia kutsutaan nimellä LL(1) kielioppi .
Jäsennystaulukon koolla on eksponentiaalinen monimutkaisuus k :n funktiona pahimmassa tapauksessa . Compiler Construction Toolkit (PCCTS, nykyään ANTLR ) julkaisun jälkeen noin vuonna 1992 kuitenkin osoitettiin, että useimpien ohjelmointikielien jäsennystaulukon koko ei yleensä kasva eksponentiaalisesti, koska se ei ole pahin. tapaus. Lisäksi joissain tapauksissa oli jopa mahdollista luoda LL( * )-analysaattoreita. Tästä huolimatta perinteiset jäsennysgeneraattorit, kuten yacc / GNU bison , käyttävät LALR( 1 ) jäsennystaulukoita rajoitetun LR-jäsentimen luomiseen .
Nykyaikaiset jäsennysgeneraattorit LL-kielioppeihin, joissa on monivälitteinen ennakointi, sisältävät:
| Muodolliset kielet ja viralliset kieliopit | |
|---|---|
| Yleiset käsitteet | |
| Tyyppi 0 | |
| Tyyppi 1 |
|
| Tyyppi 2 | |
| Tyyppi 3 |
|
| jäsentäminen | |