Kielioppi lausekkeen jäsentämiseen

Ilmaisujen jäsennyskielioppi (PB-grammar) on eräänlainen analyyttinen muodollinen kielioppi , joka kuvaa muodollista kieltä kielijonojen tunnistamista koskevien sääntöjen avulla. Lauseketta jäsentävä kielioppi on pohjimmiltaan rekursiivinen laskeva jäsentäjä puhtaasti kaavamaisessa muodossa, joka ilmaisee vain syntaksin ja on riippumaton jäsentimen tietystä toteutuksesta tai käytöstä. Lausekkeiden jäsennyskieliopit ovat samanlaisia kuin säännölliset lausekkeet ja yhteydettömät kieliopit (CFG) Backus-Naur-merkinnässä , mutta niillä on erilainen tulkinta.

Toisin kuin COP-kieliopit, PB-kieliopit eivät voi olla moniselitteisiä : jos merkkijono jäsennetään, on olemassa täsmälleen yksi jäsennyspuu. Tämä tekee RE-kieliopista sopivia tietokonekielille, mutta ei luonnollisille kielille.

Määritelmä

Muodollisesti lausekkeen jäsentävä kielioppi koostuu:

äärellinen joukko N ei-terminaalista symbolia ;
loppusymbolien äärellinen joukko Σ , joka ei leikkaa N :n kanssa ;
päättelysääntöjen äärellinen joukko P ;
lauseke e S , jota kutsutaan alkulausekkeeksi .

Jokainen päättelysääntö P:stä on muotoa A ← e, jossa A on ei-terminaalinen symboli ja e on jäsennyslauseke. Jäsennyslauseke on hierarkkinen lauseke, joka muistuttaa säännöllistä lauseketta , joka on rakennettu seuraavasti:

Atomijäsennyslauseke koostuu seuraavista:
- mikä tahansa päätemerkki,
- mikä tahansa muu kuin päätemerkki tai
- tyhjä merkkijono ε.
Kun jäsennyslausekkeet ovat e, e 1 ja e 2 , seuraavat lausekkeet luovat uusia jäsennyslausekkeita:
- Järjestys: e 1 e 2
- Tilattu valikoima: e 1 / e 2
- Nolla tai enemmän: e*
- Yksi tai useampi: e+
- Valinnainen: e?
- Ja predikaatti: &e
- EI predikaatti:!e

Pohjimmainen ero PB-kieliopin ja COP-kieliopin välillä on, että PB-kieliopin valintaoperaattori on järjestynyt . Jos ensimmäinen vaihtoehto toimii, kaikki seuraavat ohitetaan . Järjestetty valinta ei siis ole kommutatiivista, toisin kuin yhteydettömien kielioppien ja säännöllisten lausekkeiden kirjojen määritelmät. Järjestetty valinta on samanlainen kuin soft cut -operaattori joissakin loogisissa ohjelmointikielissä.

Tämän seurauksena, kun CFG muunnetaan suoraan RTG:ksi, kaikki epäselvyydet ratkaistaan deterministisesti yhden mahdollisen jäsennyspuun hyväksi. Valitsemalla huolellisesti kielioppivaihtoehtojen määrittelyjärjestyksen, ohjelmoija voi saada huomattavan hallinnan siihen, mikä jäsennyspuu valitaan.

Kuten Boolen yhteydettömät kieliopit, RE-kieliopissa on AND- ja NOT-predikaatit. Ne auttavat selventämään entisestään, jos vaihtoehtojen uudelleenjärjestäminen ei tuota haluttua jäsennyspuuta.

Jäsennyslausekkeiden tulkinta

Jokainen PB-kieliopin ei-pääte on olennaisesti jäsennysfunktio rekursiivisessa laskeutumisjäsennysosassa, ja vastaava jäsentäjälauseke on tämän funktion "koodi". Jokainen jäsennysfunktio ottaa syötteenä merkkijonon ja tuottaa yhden seuraavista tuloksista:

menestys, jolloin funktio voi valinnaisesti siirtää tai "niellä" yhtä tai useampaa syötemerkkijonoa
dippi, jossa syötettä ei kuluteta.

Ei-päätelaite voi menestyä ilman syöttöä, ja tämä tila eroaa epäonnistumisesta.

Yhdestä terminaalista koostuva atominen jäsennyslauseke onnistuu, jos syötemerkkijonon ensimmäinen merkki täsmää ja kuluttaa sen. Muuten tulos on epäonnistunut. Tyhjän merkkijonon atomilauseke onnistuu aina kulumatta. Ei-päätteisestä A: sta koostuva atomilauseke on rekursiivinen kutsu ei-päätteiselle funktiolle A.

Sekvenssioperaattori e 1 e 2 kutsuu ensin e 1 :tä ja jos e 1 onnistuu, kutsuu sitten e 2 :ta e 1 :n käyttämättä jääneestä merkkijonosta ja palauttaa tuloksen. Jos e 1 tai e 2 epäonnistuu, myös sekvenssioperaattori e 1 e 2 epäonnistuu .

Valintalauseke e 1 / e 2 kutsuu ensin e 1 :tä ja jos e 1 onnistuu, palauttaa tuloksensa. Muussa tapauksessa, jos e 1 epäonnistuu, select-käsky palauttaa syötemerkkijonon tilaan ennen e1:n kutsumista ja kutsuu e2 : ta palauttaen tuloksensa.

Nolla tai useampi, yksi tai useampi ja valinnaiset operaattorit kuluttavat vastaavasti nolla tai useampia, yhden tai useamman tai nollan tai yhden peräkkäisen esiintymän e -alilausekkeestaan . Toisin kuin CFG:t ja säännölliset lausekkeet, nämä operaattorit ovat aina ahneita ja kuluttavat niin monta syöttöesiintymää kuin mahdollista. (Säännölliset lausekkeet alkavat ahneesti, mutta epäonnistuvat sitten ja yrittävät löytää lyhyemmän sekvenssin.) Esimerkiksi lauseke a* kuluttaa aina kaikki käytettävissä olevat a:t, ja lauseke (a* a) epäonnistuu aina, koska a*:n ensimmäisen osan suorittamisen jälkeen toiselle ei ole enää a:ita.

Lopuksi AND-predikaatti ja EI-predikaatti toteuttavat syntaktisia predikaatteja. Lauseke & e kutsuu osalauseketta e ja palauttaa onnistumisen, jos e onnistuu ja epäonnistuminen muuten, mutta ei koskaan kuluta syötettä. Samoin ilmaisu ! e onnistuu, jos e epäonnistuu, ja epäonnistuu, jos e onnistuu, jälleen ilman syötettä. Koska lauseke e voi olla mielivaltaisen monimutkainen rakennelma, joka voidaan arvioida "ennakolta" kuluttamatta syötemerkkijonoa, nämä predikaatit tarjoavat tehokkaita syntaktisia valmistelu- ja yksiselitteisiä työkaluja.

Esimerkkejä

Seuraava RW-kielioppi tunnistaa matemaattiset kaavat neljällä operaatiolla ei-negatiivisille kokonaisluvuille.

Arvo ← [0-9]+ / '(' Laus ')' Tuotteen ← Arvo (('*' / '/') Arvo)* Summa ← Tuote (('+' / '-') Tuote)* Laus ← Sum

Yllä olevassa esimerkissä päätemerkit ovat tekstimerkkejä, joita edustavat kertalainausmerkit, kuten '('ja ')'. Alue [0-9]on lyhenne kymmenestä merkistä, jotka edustavat numeroita 0–9. (Tämä on sama syntaksi kuin säännöllisillä lausekkeilla). Ei-päätesymbolit ovat symboleja, joille on lähtösäännöt: Arvo , Tuote , Summa ja Laus .

Alla olevissa esimerkeissä ei ole lainausmerkkejä luettavuuden parantamiseksi. Pienet kirjaimet ovat päätemerkkejä ja isot kursiivit eivät ole päätemerkkejä. Oikeat PB-kieliopin jäsentimet vaativat lainausmerkkejä.

Jäsennyslauseke (a/b)* vastaa ja kuluttaa mielivaltaisen pituisia sekvenssejä a:sta ja b:stä. Sääntö S ← a S ? b kuvaa yksinkertaista yhteydetöntä kieltä . Seuraava RW-kielioppi kuvaa klassista, ei-kontekstitonta kieltä : $\{a^{n}b^{n}:n\geq 1\}$ $\{a^{n}b^{n}c^{n}:n\geq 1\}$

S ← &(A 'c') 'a'+ B !('a' / 'b' / 'c') A ← 'a' A? "b" B ← 'b' B? 'c'

Seuraava rekursiivinen sääntö vastaa standardia C if/then/else -lausetta siten, että valinnainen else-lohko vastaa aina sisintä if-lausetta. (Kontekstivapaassa kielioppissa tämä johtaisi klassiseen riippuvaiseen muuhun epäselvyyteen.)

S ← 'jos' C 'niin' S 'muuta' S / 'jos' C 'niin' S

Jäsennyslauseke foo &(bar) vastaa ja kuluttaa tekstiä "foo", mutta vain jos sitä seuraa teksti "bar". Jäsennyslauseke foo !(bar) kuluttaa tekstin "foo" vain, jos sitä ei seuraa "bar". Lauseke !(a+ b) a sisältää yhden merkin "a", mutta vain jos se ei ole ensimmäinen mielivaltaisen pituisessa sekvenssissä, jota seuraa b.

Seuraava rekursiivinen sääntö vastaa sisäkkäistä Pascal-kommenttia. Kommenttimerkit on suljettu lainausmerkein erottamaan ne RVG-operaattoreista.

Aloita ← '(*' Loppu ← '*)' C ← Alku N* Loppu N ← C / (!Aloita !Loppu Z) Z ← mikä tahansa yksittäinen merkki

RW-kieliopin jäsentimien toteutus

Mikä tahansa RH-kielioppi voidaan muuntaa suoraan jäsentimeksi rekursiivisen laskeutumisen avulla. Rajoittamattoman esijäsennyskyvyn vuoksi tuloksena oleva jäsentäjä voi toimia pahimmillaan eksponentiaalisessa ajassa.

Muistamalla välijäsennysvaiheiden tulokset ja varmistamalla, että kutakin jäsennysfunktiota kutsutaan korkeintaan kerran syötetietojen tietylle paikalle, on mahdollista muuntaa mikä tahansa PB-kielioppi packrat-jäsentimeksi , joka toimii aina lineaarisessa ajassa muistikustannusten huomattavan nousun kustannuksella.

Packrat-jäsennin on eräänlainen jäsentäjä, joka toimii samalla tavalla kuin rekursiivinen laskeutuminen, paitsi että jäsennettäessä se muistaa kaikkien toistensa rekursiivisten jäsennysfunktioiden kutsujen välitulokset. Tämän vuoksi packrat-jäsennin pystyy jäsentämään monia yhteydettömiä kielioppeja ja mitä tahansa PB-kielioppia (mukaan lukien jotkut, jotka luovat ei-kontekstittomia kieliä) lineaarisessa ajassa [1] .

On myös mahdollista rakentaa LL-jäsennin ja LR-jäsennin RW-kielioppeille, mutta kyky rajoittamattomaan esijäsentämiseen menetetään tässä tapauksessa.

Edut

REGRAMit ovat hyviä korvikkeita säännöllisille lausekkeille , koska ne ovat ehdottomasti tehokkaampia. Esimerkiksi säännöllinen lauseke ei pohjimmiltaan pysty löytämään vastaavia sulkupareja, koska se on ei-rekursiivinen, toisin kuin RE-kielioppi.

Mikä tahansa RH-kielioppi voidaan jäsentää lineaarisessa ajassa käyttämällä packrat-jäsennintä yllä kuvatulla tavalla.

COP-kielioppien edustamien kielten jäsentimet, kuten LR-jäsentimet, vaativat erityisen leksikaalisen analyysivaiheen, joka jakaa syötteen välilyöntien, välimerkkien ja niin edelleen mukaan. Tämä on välttämätöntä, koska nämä jäsentimet käyttävät esijäsennystä joidenkin CFG:iden käsittelemiseen lineaarisessa ajassa. RW-kieliopit eivät vaadi erillistä leksikaalista analyysivaihetta, ja sen säännöt voidaan laatia muiden kielioppisääntöjen kanssa.

Monet COP-kieliopit sisältävät merkittäviä epäselvyyksiä, vaikka niiden oletetaan kuvaavan yksiarvoisia kieliä. C:n, C++:n ja Javan "kiinni muu" -ongelma on yksi esimerkki tästä ilmiöstä. Nämä ongelmat ratkaistaan usein käyttämällä kieliopin ulkopuolista sääntöä. PB-kieliopissa näitä epäselvyyksiä ei koskaan esiinny priorisoinnin vuoksi.

Haitat

Muistin kulutus

PB-kieliopin jäsennyksen tekee yleensä packrat-jäsennys, joka muistaa ylimääräiset jäsennysvaiheet. Tällainen jäsentäminen edellyttää tietojen tallentamista suhteessa syötteen pituuteen, toisin kuin LR-jäsennysten jäsennyspuun syvyyteen. Tämä on merkittävä etu monilla alueilla: esimerkiksi ihmisen kirjoittamalla koodilla on yleensä lähes vakio sisäkkäisyydet ohjelman pituudesta riippumatta – tietyn määrän syvemmät lausekkeet yleensä muutetaan uudelleen.

Joidenkin kielioppien ja joidenkin syötteiden osalta jäsennyspuun syvyys voi olla verrannollinen syötteen pituuteen, joten arvioinnissa, jossa tätä mittaa ei oteta huomioon, packrat-jäsennin voi näyttää yhtä hyvältä kuin LR-jäsennin. Tämä on samanlainen tilanne kuin graafialgoritmeilla: Bellman-Fordilla ja Floyd-Warshallilla on yksi suoritusaika ( ), jos huomioidaan vain kärkien lukumäärä. Kuitenkin tarkempi analyysi, jossa otetaan huomioon reunojen määrä, näyttää Bellman-Ford-algoritmin suoritusajan , joka on vain neliöllinen syötteen kokoon nähden, ei kuutio. $O(|V|^{3})$ $O(|V|*|E|)$

Epäsuora vasen rekursio

Uudelleenkieliopit eivät voi sisältää vasemmanpuoleisia rekursiivisia sääntöjä, jotka kutsuvat itseään ilman rivin siirtoa. Esimerkiksi yllä kuvatussa aritmeettisessa kielioppissa haluaisin siirtää joitain sääntöjä niin, että tuotteen ja summan ensisijaisuus voidaan ilmaista yhdellä rivillä:

Arvo ← [0-9.]+ / '(' Laus ')' Tuote ← Expr (('*' / '/') Expr)* Summa ← Laus (('+' / '-') Laus)* Laus. ← Tuote / Summa / Arvo

Ongelma tässä on se, että saadaksesi osuman Expr :lle , sinun on tarkistettava, käynnistyykö tuote , ja tarkistaaksesi tuotteen , sinun on ensin tarkistettava Expr . Ja tämä on mahdotonta.

Vasemmanpuoleiset rekursiiviset säännöt voidaan kuitenkin aina kirjoittaa uudelleen vasemmanpuoleisen rekursion poistamiseksi. Esimerkiksi vasemmanpuoleinen rekursiivinen sääntö voi toistaa jonkin lausekkeen loputtomasti, kuten CF-kielioppisäännössä:

merkkijono ← merkkijono 'a' | 'a'

Tämä voidaan kirjoittaa uudelleen PB-kieliopissa käyttämällä +-operaattoria:

merkkijono-a ← 'a'+

Joillain muutoksilla on mahdollista saada tavallinen packrat-jäsennin tukemaan suoraa vasenta rekursiota [1] [2] [3] .

Epäsuorien vasen-rekursiivisten sääntöjen uudelleenkirjoitusprosessi on kuitenkin vaikeaa, varsinkin kun tapahtuu semanttisia toimintoja. Vaikka teoriassa on mahdollista, ei ole olemassa RW-jäsentimiä, jotka tukevat epäsuoraa vasenta rekursiota, kun taas kaikki GLR-jäsentimet tukevat.

Hienovaraisia kielioppivirheitä

Ilmaistakseen kieliopin PB-kielioppina sen tekijän on muutettava kaikki ei-deterministisen valinnan esiintymät järjestetyksi valinnaksi. Valitettavasti tämä prosessi on virhealtis ja johtaa usein kielioppiin, jotka jäsentävät osan syötteestä väärin.

Ilmaisukyky

Packrat-jäsentimet eivät voi jäsentää joitain yksiselitteisiä kielioppeja, kuten seuraavia [4] :

S ← 'x' S 'x' | 'x'

Kehitys

RE-kieliopit ovat uusia, eikä niitä käytetä laajasti. Säännölliset lausekkeet ja COP-kieliopit ovat sen sijaan olleet olemassa jo vuosikymmeniä, niitä jäsentävää koodia on parannettu ja optimoitu, ja ohjelmoijalla on kokemusta niiden käytöstä.

Linkit

Medeiros, Sergio; Jerusalemschy, Roberto (2008). "PEG:ien jäsennyskone". Proc. vuoden 2008 symposiumin dynaamisista kielistä . ACM . s. artikkeli #2. DOI : 10.1145/1408681.1408683 . ISBN 978-1-60558-270-2 . Käytöstä poistettu parametri |coauthors=( ohje )

Muistiinpanot

↑ 1 2 Ford, Bryan Packrat Jäsennys: Käytännöllinen lineaarinen aikaalgoritmi paluumatkalla . Massachusetts Institute of Technology (syyskuu 2002). Käyttöpäivä: 27. heinäkuuta 2007. Arkistoitu alkuperäisestä 2. huhtikuuta 2012. (määrätön)
↑ Alessandro Warth, James R. Douglass, Todd Millstein. Packratin jäsentimet voivat tukea vasenta rekursiota . - Viewpoints Research Institute, 2008. - Tammikuu.
↑ Ruedi Steinmann. Vasemman rekursion käsitteleminen Packrat -jäsentimissä (neopr.) . - 2009 - maaliskuu. Arkistoitu alkuperäisestä 6. heinäkuuta 2011. Arkistoitu kopio (linkki ei saatavilla) . Haettu 17. kesäkuuta 2009. Arkistoitu alkuperäisestä 6. heinäkuuta 2011. (määrätön)
↑ Bryan Ford. Toiminnallinen helmi: Packrat-jäsennys: yksinkertainen, tehokas, laiska, lineaarinen aika (englanniksi) : päiväkirja. – 2002.