LL(1)
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3.7.2020 tarkistetusta
versiosta . tarkastukset vaativat
5 muokkausta .
LL(1) - LL -jäsennys , ylhäältä alas -jäsennysalgoritmi . Numero 1 kertoo, että jäsennyspolun määrittämiseen tarvitaan vain yksi merkki .
Helppo kirjoittaa käsin ilman automaattisia generaattoreita. Käytetään koodin jäsentämiseen useilla ohjelmointikielillä , kuten Pascal ja Python (ennen 3.8 [1] ).
Se on erittäin nopea suoritus ja siinä on tyypillinen virheilmoitus, kuten "sellaista ja sellaista hahmoa odotettiin."
Sääntöoppaan merkit
Jokaiselle kieliopin ei -päätteelle A luodaan joukko päätteitä First(A), joka määritellään seuraavasti:
- jos kieliopin sääntö on A vasemmalla ja oikealla, joka alkaa terminaalilla, niin kyseinen pääte on kohdassa First(A)
- jos kieliopin sääntö on A vasemmalla ja oikealla puolella, joka alkaa ei-päätteellä (merkitty B), niin First(B) sisältyy tiukasti kohtaan First(A)
- First(A) ei sisällä muita päätteitä
Kullekin säännölle luodaan ohjemerkkijoukko, joka määritellään seuraavasti:
- jos säännön oikea puoli alkaa terminaalilla, ohjemerkkien joukko koostuu tästä yhdestä terminaalista
- muuten oikea puoli alkaa ei-päätteellä A, jolloin alkumerkkien joukko on First(A)
Näitä määritelmiä on mahdollista yleistää tapaukseen, jossa muodon säännöt ovat olemassa A → null.
On selvää, että First(A) on kaikkien sääntöjen johtavan symbolijoukkojen liitto, jossa A on vasemmalla puolella.
Kielioppi on LL(1) jäsennettävä , jos jollakin sääntöparilla, jolla on sama vasen puoli, ohjemerkkien joukko ei leikkaa.
Sen selvittämiseksi, jäsentääkö kielioppi LL(1) vai ei yleensä, on kätevää käyttää LL(1)-kielioppien kriteeriä [2] .
Analysaattorin kuvaus
Pinoa käytetään, jossa terminaalien ja ei-päätteiden lukumäärä, tulo- (päätteet) ja lähtö (sääntömäärät) -virrat sijaitsevat.
Ensin E, kieliopin aloitussymboli, työnnetään pinoon.
Sitten jokaiselle uudelle merkille syöttövirrasta sen loppuun:
- jos pinon yläosassa on pääte ja se vastaa tulovirran symbolia, niin a) ponnahtaa pääte pinosta ja b) kuluttaa tulovirran symboli.
- jos pinon yläosassa on pääte, joka ei vastaa syötevirran symbolia, tämä on syntaksivirhe "sellaista ja sellaista symbolia odotettiin" (pinossa oleva).
- muussa tapauksessa pinon yläosassa on ei-pääte, merkitsemme sitä A:lla. Kaikki säännöt, joilla se on vasemmalla puolella, etsitään, jokaiselle säännölle etsitään ohjaussymbolijoukkoja syötteen symbolin löytämiseksi virta; se ei voi esiintyä siellä useammin kuin kerran, muuten kielioppi ei ole LL(1) jäsennettävä.
- jos symboli löytyy, sovelletaan tätä sääntöä: säännön numero tulostetaan ulostulovirtaan, yksi symboli pompataan pinosta (tämä on A) ja sen sijaan työnnetään koko säännön oikea puoli sisään, oikean puolen vasemmanpuoleisin symboli on viimeinen. Syöttövirran merkkiä ei kuluteta.
- muuten symbolia ei löytynyt ollenkaan. Sitten, jos on muodon sääntö A → null , niin A työnnetään pinon yläosasta. Syöttövirran merkkiä ei kuluteta.
- Muussa tapauksessa kyseessä on syntaksivirhe, sanoma voidaan tulostaa muodossa "yksi oli odotettavissa" ja sen jälkeen luettelo joukosta First(A) (kielen tärkeimmille ei-päätteille, esim. terminaalin "lauseke", voit muotoilla virheen ei-päätenimillä).
Kielet
Katso myös
Muistiinpanot
- ↑ PEP 617 - Uusi PEG-jäsennin CPythonille | peps.python.org . peps.python.org . Haettu 15. heinäkuuta 2022. Arkistoitu alkuperäisestä 15. heinäkuuta 2022. (määrätön)
- ↑ Kozlov Sergei Valerievich, Svetlakov Aleksei Vladimirovich. Tietoja LL(1)-KIETOISTA, NIIDEN ALGORITMEISTA JA NIIDEN ANALYYSIMENETELMISTÄ OHJELMOINTIIN // International Journal of Open Information Technologies. - 2022. - Osa 10 , no. 3 . - S. 30-38 . — ISSN 2307-8162 . Arkistoitu alkuperäisestä 18. toukokuuta 2022.
Kirjallisuus
- Grune, D. ja van Reeuwijk, K. ja Bal, HE ja Jacobs, CJH ja Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 s. — ISBN 9781461446996 .
- Mogensen, T. Æ. Johdatus kääntäjäsuunnitteluun. - Springer, 2011. - 225 s. — ISBN 9780857298294 .
- Mozgovoy, M. Algoritmit, kielet, automaatit ja kääntäjät: käytännön lähestymistapa. - Jones & Bartlett Learning, 2009. - 345 s. — ISBN 9780763782948 .
- Kozlov S. V., Svetlakov A. V. Tietoja LL(1)-kieliopeista, niiden algoritmeista ja niiden analysointimenetelmistä ohjelmoinnin alalla — International Journal of Open Information Technologies. - 2022. - T. 10. - Nro 3. - S. 30-38. — URL-osoite: https://cyberleninka.ru/article/n/o-ll-1-grammatikah-algoritmah-na-nih-i-metodah-ih-analiza-v-programmirovanii .
Linkit