Osim regularnih izraza: Uvod u raščlanjivanje gramatika bez konteksta

Važan i koristan alat koji je već dio arsenala većine programera je pouzdan regularni izraz . Ali izvan te leže gramatike bez konteksta. Ovo je jednostavan koncept s otmjenim imenom.

Regularni izraz metoda je provjere valjanosti i pronalaženja obrazaca u tekstu. Vrste uzoraka (tzv. Gramatike) koje se mogu opisati i otkriti pomoću regularnog izraza nazivaju se regularni jezici . Regularni jezici najjednostavniji su od formalnih jezika u homskoj hijerarhiji .

Regularni izrazi izvrsni su za pronalaženje ili provjeru valjanosti mnogih vrsta jednostavnih obrazaca, na primjer telefonskih brojeva, adresa e-pošte i URL-ova. Međutim, nedostaju kada se primijene na uzorke koji mogu imati rekurzivnu strukturu, kao što su:

  • HTML / XML oznake za otvaranje / zatvaranje
  • otvori / zatvori zagrade {/} u programskim jezicima
  • otvori / zatvori zagrade u aritmetičkim izrazima

Da bismo raščlanili ove vrste obrazaca, trebamo nešto snažnije. Možemo prijeći na sljedeću razinu formalnih gramatika koje se nazivaju kontekstualne gramatike (CFG).

Raščlanjivanje matematičkih izraza

Raščlanjivanje skupa svih matematičkih izraza izvan je snage istinskog regularnog izraza. Razlog je taj što oni mogu sadržavati proizvoljno duboko ugniježđene parove zagrada.

Na primjer, razmotrite izraz: (2 + (3 * (7–4)))

Primijetite da je struktura aritmetičkog izraza zapravo stablo:

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

Struktura stabla generirana kao rezultat izvođenja CFG parsera naziva se stablo raščlanjivanja .

Opisivanje gramatika bez konteksta

Postoje dvije popularne metode izražavanja CFG gramatika:

  1. Prošireni obrazac Bachus-Naur (EBNF) - opisuje CFG u smislu pravila proizvodnje . To su pravila koja, kada se primijene, mogu generirati sve moguće pravne fraze na jeziku.
  2. Gramatika izraza raščlanjivanja (PEG) - opisuje CFG u smislu pravila prepoznavanja . To su pravila koja se mogu koristiti za podudaranje valjanih fraza u jeziku.

PEG formalizam ima prednost u odnosu na EBNF što je preslikavanje u parser jednoznačno i može se lako automatizirati.

Slijedi jednostavan PEG podignut sa svoje stranice Wikipedije koji opisuje matematičke formule koje primjenjuju osnovne četiri operacije na nenegativne

cijeli brojevi.

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

Jednostavno, ovo možemo pročitati kao:

  • Expr je Sum
  • Sumje Productzatim nula ili više manjih uzoraka koji se sastoje od „+” ili „-”, nakon čega slijediProduct
  • Productje Valuezatim nula ili više manjih uzoraka koji se sastoje od a „*” ili „/”, nakon čega slijediValue
  • Valueje jedan ili više članova skupa znakova {0, .. 9}, ili je otvorena zagrada “(„ iza koje slijede a Expri zatvarajuća zagrada „)“.

Generatori raščlanjivača naspram raščlanjivanja knjižnica

Pod pretpostavkom da niste tip osobe koja voli izmišljati kotač (ne da nešto nije u redu s tim), općenito postoje dvije mogućnosti za stvaranje parsera:

1. Upotrijebite generator raščlanjivača - alat koji generira izvorni kod za raščlanjivač iz apstraktne definicije raščlanjivača. Neki popularni primjeri u JavaScript-u uključuju Jison, PEG.js, nearley i ANTLR.

2. Upotrijebite knjižnicu za raščlanjivanje - knjižnicu koja omogućuje izražavanje pravila raščlanjivanja kao API. Neki primjeri u JavaScript-u uključuju Myna, Parsimmon i Chevrotain.

Moja je želja koristiti knjižnice za raščlanjivanje jer ih je lakše razumjeti, ispraviti, ispraviti, održavati i prilagoditi.

Pisanje parsera u TypeScript / JavaScript pomoću Myna Parsing Library

Nedavno je projekt na kojem sam radio (jezik Heron) zahtijevao biblioteku za raščlanjivanje koja se može pokretati u pregledniku. Smatrao sam da su složenost i troškovi postojećih knjižnica preveliki. S obzirom na to da sam imao prethodno iskustvo u pisanju raščlanjivanja knjižnica na C ++ i C #, odlučio sam napisati parser biblioteku Myna koristeći TypeScript.

Myna koristi tečnu sintaksu (ulančavanje metoda) kako bi olakšala definiranje raščlanjivača kao skupa pravila (podrazbornik) koji nalikuju PEG gramatici.

Sljedeći je primjer iz Myna GitHub repo-a:

Od konkretnog stabla sintakse (CST) do apstraktnog stabla sintakse (AST)

Kada parser obradi ulaz, svako se uspješno podudarno pravilo (aka gramatička proizvodnja) može preslikati na čvor u stablu raščlanjivanja. Ovo doslovno mapiranje proizvodnih pravila na čvorove u stablu je konkretno stablo sintakse (CST).

U nekim je slučajevima CST ograničeno korišten jer sadrži puno sintaktičke nereda, na primjer komentare u izvornom kodu ili ima li literal niza dvostruke navodnike ili pojedinačne navodnike. Može sadržavati rezultate pravila koja su stvorena kako bi se gramatika olakšala za upotrebu, ali ne predstavljaju željenu strukturu stabla za analizu.

Najjednostavnije je napraviti čvorove u izlaznom stablu samo za određena pravila i preskočiti druga pravila. Ova pojednostavljena verzija stabla raščlanjivanja naziva se apstraktno stablo sintakse (AST) . Na AST-u može biti izvedeno više prolaza kako bi se transformirao u alternativne AST-ove prikaze kako bi se pojednostavili kasniji koraci obrade.

U Myni se AST generira stvaranjem čvorova iz pravila označenih sa astsvojstvom. Tehnički, ovo svojstvo vraća novo pravilo koje ima unutarnji skup svojstava koji poručuje rastavljaču da generira čvor za raščlanjivanje u stablu raščlanjivanja.

Korištenje generiranog Myna apstraktnog sintaksnog stabla

Evo primjera upotrebe Myna-definiranog parsera u "Node.JS" za procjenu aritmetičkog izraza:

Završne riječi

Ako ste zainteresirani da saznate više o stvaranju i korištenju parsera, bez obzira ispunjava li Myna biblioteka vaše specifične potrebe, savjetujem vam da odvojite malo vremena za čitanje izvornog koda Myna biblioteke za raščlanjivanje.

Myna je napisana na TypeScript-u (koji ima poznatu sintaksu za većinu programera), sadržana je u jednoj datoteci bez ovisnosti i manja je od 1200 redaka, uključujući detaljnu dokumentaciju.

Ako ste zainteresirani za primjenu Myne na složenijem scenariju, pogledajte programski jezik Chickadee. To je u potpunosti implementirano u TypeScript i ovisi samo o Myna knjižnici za raščlanjivanje. Chickadee je maleni programski jezik dizajniran posebno da pomogne ljudima da nauče o tehnikama implementacije programskih jezika.

Ako vam se svidio ovaj članak, javite mi i razmislite o tome da ga podijelite sa svojim prijateljima i kolegama.