Ud over regulære udtryk: En introduktion til at analysere kontekstfrie grammatikker

Et vigtigt og nyttigt værktøj, der allerede er en del af de fleste programmørers arsenaler, er det troværdige regulære udtryk . Men ud over det ligger kontekstfrie grammatikker. Dette er et simpelt koncept med et fancy navn.

Et regulært udtryk er en metode til at validere og finde mønstre i tekst. De slags mønstre (aka grammatik), der kan beskrives og detekteres ved hjælp af et regulært udtryk kaldes almindelige sprog . Regelmæssige sprog er de enkleste formelle sprog i Chomsky-hierarkiet .

Regulære udtryk er gode til at finde eller validere mange typer enkle mønstre, for eksempel telefonnumre, e-mail-adresser og URL'er. De kommer dog kort, når de anvendes på mønstre, der kan have en rekursiv struktur, såsom:

  • HTML / XML åbne / lukke tags
  • åbn / luk seler {/} på programmeringssprog
  • åbne / lukke parenteser i aritmetiske udtryk

For at analysere disse typer mønstre har vi brug for noget mere kraftfuldt. Vi kan gå til det næste niveau af formelle grammatikker kaldet kontekstfri grammatik (CFG).

Analyse af matematiske udtryk

At analysere sættet med alle matematiske udtryk ligger uden for kraften i et ægte regulært udtryk. Årsagen er, at disse kan indeholde vilkårligt dybe indlejrede par parenteser.

Overvej f.eks. Udtrykket: (2 + (3 * (7–4)))

Bemærk, at strukturen i det aritmetiske udtryk effektivt er et træ:

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

Træstrukturen, der genereres som et resultat af at køre en CFG-parser, kaldes et parse-træ .

Beskriver kontekstfrie grammatikker

Der er to populære metoder til at udtrykke CFG-grammatikker:

  1. Udvidet Bachus-Naur-form (EBNF) - beskriver en CFG i form af produktionsregler . Dette er regler, der, når de anvendes, kan generere alle mulige juridiske sætninger på sproget.
  2. Parsing Expression Grammar (PEG) - beskriver en CFG i form af anerkendelsesregler . Dette er regler, der kan bruges til at matche gyldige sætninger på sproget.

PEG-formalismen har den fordel i forhold til EBNF, at kortlægningen til en parser er utvetydig og let kan automatiseres.

Følgende er en simpel PEG løftet fra sin Wikipedia-side, der beskriver matematiske formler, der anvender de fire grundlæggende operationer til ikke-negative

heltal.

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

På almindelig engelsk kan vi læse dette som:

  • Expr er en Sum
  • Sumer Productefterfulgt af nul eller flere delmønstre, der består af et "+" eller "-" efterfulgt af enProduct
  • Producter Valueefterfulgt af nul eller flere delmønstre, der består af et "*" eller "/" efterfulgt af enValue
  • Valueer enten et eller flere medlemmer af tegnsættet {0, .. 9}, eller det er en åben parentes "(" efterfulgt af a Exprog en afsluttende parentes ")".

Parser-generatorer versus parsing-biblioteker

Forudsat at du ikke er den type person, der kan lide at genopfinde hjulet (ikke at der er noget galt med det), er der generelt to muligheder for at oprette en parser:

1. Brug en parsergenerator - et værktøj, der genererer kildekoden til en parser ud fra en abstrakt definition af parseren. Nogle populære eksempler i JavaScript inkluderer Jison, PEG.js, nearley og ANTLR.

2. Brug et parseringsbibliotek - et bibliotek, der tillader udtryk for analysereglerne som en API. Nogle eksempler i JavaScript inkluderer Myna, Parsimmon og Chevrotain.

Min præference er at bruge parsebiblioteker, fordi de er lettere at forstå, debugge, vedligeholde og tilpasse.

Skriv parsere i TypeScript / JavaScript ved hjælp af Myna Parsing Library

For nylig krævede et projekt, jeg arbejdede på (Heron-sproget), et analysebibliotek, der kunne køre i browseren. Jeg fandt kompleksiteten og omkostningerne ved eksisterende biblioteker for store. Da jeg havde tidligere erfaring med at skrive parsebiblioteker i C ++ og C #, besluttede jeg at skrive et parserbibliotek kaldet Myna ved hjælp af TypeScript.

Myna bruger flydende syntaks (metodekædning) for at gøre det let at definere en parser som et sæt regler (sub-parser), der ligner en PEG-grammatik.

Følgende eksempel er fra Myna GitHub repo:

Fra konkret syntaks træ (CST) til abstrakt syntaks træ (AST)

Når en parser behandler input, kan hver vellykket matchet regel (aka grammatikproduktion) knyttes til en node i parse-træet. Denne bogstavelige kortlægning af produktionsregler til noder i et træ er et konkret syntaks-træ (CST).

I nogle tilfælde er CST begrænset anvendelig, da den indeholder meget syntaktisk rod, for eksempel kommentarer i kildekoden, eller om en strengbogstav har dobbelt anførselstegn eller enkelt anførselstegn. Det kan indeholde resultater fra regler, der er oprettet for at gøre grammatikken lettere at bruge, men repræsenterer ikke den tilsigtede træstruktur til analyse.

Den enkleste ting at gøre er at kun oprette noder i outputtræet for specifikke regler og springe andre regler over. Denne forenklede version af parse-træet kaldes et abstrakt syntaks-træ (AST) . Der kan udføres flere passeringer på en AST for at omdanne den til alternative AST-repræsentationer for at forenkle senere behandlingstrin.

I Myna genereres en AST ved at oprette noder ud fra regler, der er mærket med astejendommen. Teknisk returnerer denne egenskab en ny regel, der har et internt egenskabssæt, der fortæller parseren at generere en parsenode i parsetræet.

Brug af det genererede Myna abstrakte syntaks træ

Her er et eksempel på brug af en Myna-defineret parser i "Node.JS" til at evaluere et aritmetisk udtryk:

Afsluttende ord

Hvis du er interesseret i at lære mere om at oprette og bruge parsers, uanset om Myna-biblioteket opfylder dine specifikke behov eller ej, opfordrer jeg dig til at tage lidt tid på at læse kildekoden til Myna parsing-biblioteket.

Myna blev skrevet i TypeScript (som har en velkendt syntaks for de fleste programmører), er indeholdt i en enkelt fil uden afhængigheder og er mindre end 1200 linjer inklusive detaljeret dokumentation.

Hvis du er interesseret i at se Myna anvendes til et mere komplekst scenario, skal du kigge på Chickadee-programmeringssproget. Dette implementeres udelukkende i TypeScript og afhænger kun af Myna-parseringsbiblioteket. Chickadee er et lille programmeringssprog designet specielt til at hjælpe folk med at lære om teknikker til implementering af programmeringssprog.

Hvis du kunne lide denne artikel, så lad mig det vide, og overvej at dele den med dine venner og kolleger.