Säännöllisten lausekkeiden lisäksi: Johdanto kontekstittomien kieliopien jäsentämiseen

Tärkeä ja hyödyllinen työkalu, joka on jo osa useimpien ohjelmoijien arsenaaleja, on luotettava säännöllinen lauseke . Mutta sen ulkopuolella ovat kontekstittomat kieliopit. Tämä on yksinkertainen käsite, jolla on hieno nimi.

Säännöllinen lauseke on menetelmä tekstien kuvioiden vahvistamiseksi ja löytämiseksi. Sellaisia ​​kuvioita (alias kielioppeja), jotka voidaan kuvata ja havaita säännöllisen lausekkeen avulla, kutsutaan säännöllisiksi kieliksi . Säännölliset kielet ovat yksinkertaisimpia muodollisia kieliä Chomsky-hierarkiassa .

Säännölliset lausekkeet ovat hyviä etsimään tai vahvistamaan monenlaisia ​​yksinkertaisia ​​malleja, kuten puhelinnumeroita, sähköpostiosoitteita ja URL-osoitteita. Ne kuitenkin puuttuvat, kun niitä käytetään malleihin, joilla voi olla rekursiivinen rakenne, kuten:

  • HTML / XML avaa / sulje -tagit
  • avaa / sulje aaltosulkeet {/} ohjelmointikielillä
  • avaa / sulje sulkeet aritmeettisissa lausekkeissa

Tämän tyyppisten mallien jäsentämiseksi tarvitsemme jotain tehokkaampaa. Voimme siirtyä muodollisten kieliopien seuraavalle tasolle, nimeltään kontekstivapaat kieliopit (CFG).

Jäsennys matemaattisia lausekkeita

Kaikkien matemaattisten lausekkeiden jäsentäminen ylittää todellisen säännöllisen lausekkeen voiman. Syynä on, että nämä voivat sisältää mielivaltaisesti syviä sisäkkäisiä sulkeja.

Harkitse esimerkiksi lauseketta: (2 + (3 * (7–4)))

Huomaa, että aritmeettisen lausekkeen rakenne on käytännössä puu:

 + / \ 2 * / \ 3 - / \ 7 4

CFG-jäsentimen suorittamisen tuloksena syntynyttä puurakennetta kutsutaan jäsennyspuuksi .

Kontekstittomien kieliopien kuvaaminen

On olemassa kaksi suosittua tapaa ilmaista CFG-kielioppeja:

  1. Laajennettu Bachus-Naur-muoto (EBNF) - kuvaa CFG: tä tuotantosääntöjen suhteen . Nämä ovat sääntöjä, joita sovellettaessa voidaan luoda kaikki mahdolliset oikeudelliset lauseet kielelle.
  2. Parsing Expression Grammar (PEG) - kuvaa CFG: tä tunnistussääntöjen suhteen . Nämä ovat sääntöjä, joita voidaan käyttää vastaamaan kielen voimassa olevia lauseita.

PEG-muodollisuudella on se etu EBNF: ään nähden, että yhdistäminen jäsentimeen on yksiselitteinen ja se voidaan helposti automatisoida.

Seuraava on yksinkertainen PEG, joka on nostettu Wikipedia-sivulta ja kuvaa matemaattisia kaavoja, jotka soveltavat neljää perusoperaatiota ei-negatiivisiin

kokonaislukuja.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Selkeänä englanniksi voimme lukea tämän seuraavasti:

  • Expr on Sum
  • Sumon Productnolla tai useampia alimalleja, jotka koostuvat "+" tai "-", jota seuraa aProduct
  • Producton Valuenolla tai useampia alimalleja, jotka koostuvat "*" tai "/" ja jota seuraa aValue
  • Valueon joko yksi tai useampia merkistöjoukon {0, .. 9} jäseniä, tai se on avoin sulu "(" jota seuraa a Exprja lopullinen sulu ")".

Jäsennysgeneraattorit vs. kirjastojen jäsentäminen

Olettaen, että et ole sellainen henkilö, joka haluaa keksiä pyörän uudelleen (eikä siinä, että siinä olisi mitään vikaa), jäsentimen luomiseen on yleensä kaksi vaihtoehtoa:

1. Käytä jäsenningeneraattoria - työkalua, joka tuottaa jäsentimen lähdekoodin jäsentimen abstraktista määritelmästä. Joitakin suosittuja esimerkkejä JavaScriptistä ovat Jison, PEG.js, nearley ja ANTLR.

2. Käytä jäsentekirjastoa - kirjastoa, joka sallii jäsentämissääntöjen ilmaisun API: na. Joitakin esimerkkejä JavaScriptistä ovat Myna, Parsimmon ja Chevrotain.

Haluan käyttää jäsentäviä kirjastoja, koska ne on helpompi ymmärtää, korjata, ylläpitää ja mukauttaa.

Parsereiden kirjoittaminen TypeScript / JavaScriptiä käyttäen Myna-jäsentökirjastoa

Äskettäin projekti, jonka parissa työskentelin (Heronin kieli), vaati jäsentökirjastoa, joka voisi toimia selaimessa. Pidin olemassa olevien kirjastojen monimutkaisuutta ja yleiskustannuksia liian suurena. Annetaan Minulla oli aiempaa kokemusta kirjallisesti jäsentämiseen kirjastoissa C ++ ja C #, päätin kirjoittaa jäsennin kirjasto nimeltään Myna avulla kirjoituskoneella.

Myna käyttää sujuvaa syntaksia (metodiketjua) helpottaakseen jäsentimen määrittelemistä PEG-kielioppia muistuttavaksi sääntöjoukoksi (ali-jäsentäjäksi).

Seuraava esimerkki on Myna GitHub -reposta:

Konkreettisesta syntaksipuusta (CST) abstraktiin syntaksipuun (AST)

Kun jäsennin käsittelee syötteen, kukin onnistuneesti sovitettu sääntö (alias kieliopin tuotanto) voidaan yhdistää jäsentelypuun solmuun. Tämä kirjaimellinen tuotantosääntöjen kartoitus puun solmuihin on konkreettinen syntaksipuu (CST).

Joissakin tapauksissa CST: llä on rajoitettu käyttö, koska se sisältää paljon syntaktista sotkua, esimerkiksi kommentteja lähdekoodissa, vai onko merkkijono-kirjaimessa kaksois- tai yksittäisiä lainausmerkkejä. Se voi sisältää tuloksia säännöistä, jotka on luotu helpottamaan kieliopin käyttöä, mutta eivät edusta tarkoitettua puurakennetta analyysia varten.

Yksinkertaisin tehtävä on luoda solmuja lähtöpuuhun vain tiettyjä sääntöjä varten ja ohittaa muut säännöt. Tätä jäsennetyn puun yksinkertaistettua versiota kutsutaan abstraktiksi syntaksipuuksi (AST) . AST: lle voidaan suorittaa useita läpikulkuja sen muuntamiseksi vaihtoehtoisiksi AST-esityksiksi myöhempien prosessointivaiheiden yksinkertaistamiseksi.

Mynassa AST luodaan luomalla solmut astominaisuudella merkittyistä säännöistä . Teknisesti tämä ominaisuus palauttaa uuden säännön, jolla on sisäinen ominaisuusjoukko, joka käskee jäsentimen luomaan jäsennyssolmun jäsentelypuuhun.

Luodun Myna-abstraktin syntaksipuun käyttäminen

Tässä on esimerkki Myna-määritetyn jäsentimen käytöstä solmussa.JS aritmeettisen lausekkeen arvioimiseksi:

Viimeiset sanat

Jos olet kiinnostunut oppimaan lisää jäsentäjien luomisesta ja käytöstä riippumatta siitä, täyttääkö Myna-kirjasto erityistarpeesi, suosittelen, että otat vähän aikaa lukemaan Myna-jäsentökirjaston lähdekoodin.

Myna kirjoitettiin TypeScript-muodossa (jolla on tuttu syntaksi useimmille ohjelmoijille), se sisältyy yhteen tiedostoon ilman riippuvuuksia ja on alle 1200 riviä, mukaan lukien yksityiskohtaiset ohjeet.

Jos haluat nähdä Mynan sovellettavan monimutkaisempaan skenaarioon, tutustu Chickadee-ohjelmointikieleen. Tämä toteutetaan kokonaan TypeScriptissä ja riippuu vain Myna-jäsentökirjastosta. Chickadee on pieni ohjelmointikieli, joka on suunniteltu erityisesti auttamaan ihmisiä oppimaan ohjelmointikielten käyttöönottotekniikoista.

Jos pidit tästä artikkelista, ilmoita siitä minulle ja harkitse sen jakamista ystävien ja kollegoiden kanssa.