A reguláris kifejezéseken túl: Bevezetés a kontextusmentes nyelvtanok elemzésébe

Fontos és hasznos eszköz, amely már a legtöbb programozó arzenáljának része, a megbízható reguláris kifejezés . De ezen túl a kontextusmentes nyelvtanok rejlenek. Ez egy egyszerű koncepció fantázianévvel.

A reguláris kifejezés egy módszer a minták ellenőrzésére és megtalálására a szövegben. Azokat a mintákat (más néven nyelvtanokat), amelyeket szabályos kifejezéssel lehet leírni és felismerni, reguláris nyelveknek nevezzük . A normál nyelvek a Chomsky-hierarchia legegyszerűbb formális nyelvei .

A rendszeres kifejezések kiválóan alkalmasak sokféle egyszerű minta megtalálására vagy érvényesítésére, például telefonszámokra, e-mail címekre és URL-ekre. Ezek azonban elmaradnak, ha olyan mintákra alkalmazzák, amelyek rekurzív szerkezetűek lehetnek, például:

  • HTML / XML nyitó / záró címkék
  • zárójelek nyitása / zárása {/} a programozási nyelvekben
  • zárójelek nyitása / bezárása számtani kifejezésekben

Az ilyen típusú minták elemzéséhez valami erőteljesebbre van szükségünk. Áttérhetünk a hivatalos nyelvtanok következő szintjére, az úgynevezett kontextusmentes nyelvtanoknak (CFG).

Matematikai kifejezések elemzése

Az összes matematikai kifejezés halmazának elemzése meghaladja a valódi szabályos kifejezés erejét. Ennek oka az, hogy ezek tetszőlegesen mélyen beágyazott zárójeleket tartalmazhatnak.

Vegyük például a következő kifejezést: (2 + (3 * (7–4)))

Figyelje meg, hogy a számtani kifejezés szerkezete valóban fa:

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

A CFG elemző futtatása eredményeként létrehozott fa struktúrát elemző fának nevezzük .

Környezetmentes nyelvtanok leírása

Két népszerű módszer létezik a CFG nyelvtanok kifejezésére:

  1. Kiterjesztett Bachus-Naur forma (EBNF) - leírja a CFG-t a gyártási szabályok szempontjából . Ezek olyan szabályok, amelyek alkalmazásakor az összes lehetséges jogi kifejezést előállíthatják a nyelven.
  2. Parsing Expression Grammar (PEG) - leírja a CFG-t az elismerési szabályok szempontjából . Ezek olyan szabályok, amelyek felhasználhatók a nyelvben érvényes kifejezések egyeztetésére.

A PEG formalizmusnak az az előnye, hogy az elemzőhöz való hozzárendelés egyértelmű és könnyen automatizálható.

Az alábbiakban egy egyszerű PEG-t emeltünk ki a Wikipedia oldaláról, amely olyan matematikai képleteket ír le, amelyek az alapvető négy műveletet nem negatívra alkalmazzák.

egész számok.

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

Egyszerű angol nyelven ezt a következőképpen olvashatjuk:

  • Expr egy Sum
  • Sumegy Productamelyet nulla vagy több al-minták, amelyek egy „+” vagy „-” majd egyProduct
  • Productegy Valueamelyet nulla vagy több al-minták, amelyek egy „*” vagy „/” majd egyValue
  • Valuevagy a (z) {0, .. 9} karakterkészlet egy vagy több tagja, vagy ez egy nyitott zárójel "(" után Expregy záró zárójel ")".

Az elemző generátorok a könyvtárak elemzésével szemben

Feltételezve, hogy nem Ön az az ember, aki szereti újratalálni a kereket (nem mintha ezzel baj lenne), akkor egy elemző létrehozásának általában két lehetősége van:

1. Használjon elemzőgenerátort - olyan eszközt, amely az elemző forráskódját az elemző absztrakt definíciójából állítja elő. Néhány népszerű példa a JavaScript-ben: Jison, PEG.js, nearley és ANTLR.

2. Használjon elemző könyvtárat - olyan könyvtárat, amely API-ként lehetővé teszi az elemzési szabályok kifejezését. Néhány példa a JavaScript-re: Myna, Parsimmon és Chevrotain.

Előnyben részesítem az elemző könyvtárak használatát, mert könnyebben érthetőek, hibakereshetők, karbantarthatók és testreszabhatók.

Parsírok írása TypeScript / JavaScript-ben a Myna elemzési könyvtár segítségével

Nemrégiben egy olyan projekten, amin dolgoztam (a gém nyelv), szükség volt egy elemző könyvtárra, amely a böngészőben futtatható. Túl nagynak találtam a meglévő könyvtárak összetettségét és általános költségeit. Tekintettel arra, hogy korábbi tapasztalataim voltak a könyvtárak elemzésében C ++ és C # nyelven, úgy döntöttem, hogy írok egy Myna nevű elemző könyvtárat a TypeScript segítségével.

Myna folyékony szintaxist (metódusláncolást) használ annak érdekében, hogy megkönnyítse az elemző definiálását olyan szabálykészletként (al-elemző), amely hasonlít egy PEG nyelvtanra.

A következő példa a Myna GitHub repóból származik:

A konkrét szintaxisfától (CST) az absztrakt szintaxisfáig (AST)

Amikor egy elemző feldolgozza a bemenetet, minden sikeresen egyeztetett szabályt (más néven nyelvtani előállítást) leképezhetünk az elemzési fa egy csomópontjára. A termelési szabályok szó szerinti leképezése egy fa csomópontjaira egy konkrét szintaxisfa (CST).

Bizonyos esetekben a CST korlátozott felhasználású, mivel sok szintaktikai rendetlenséget tartalmaz, például megjegyzéseket a forráskódban, vagy azt, hogy egy karakterlánc literál tartalmaz-e kettős vagy egyes idézőjeleket. Tartalmazhat olyan szabályok eredményeit, amelyek a nyelvtan könnyebb használata érdekében készültek, de nem képviselik az elemzésre szánt fa struktúrát.

A legegyszerűbb az, ha csak a csomópontokat hozza létre a kimeneti fában meghatározott szabályokhoz, és más szabályokat kihagy. Az elemző fa ezen egyszerűsített változatát absztrakt szintaxisfának (AST) nevezzük . Lehetséges, hogy egy AST-n többször is végrehajtják az alternatív AST-ábrázolásokká történő átalakítást, a későbbi feldolgozási lépések egyszerűsítése érdekében.

A Myna alkalmazásban egy AST generálódik, ha csomópontokat hoz létre a asttulajdonsággal címkézett szabályokból . Technikailag ez a tulajdonság egy új szabályt ad vissza, amelynek van egy belső tulajdonságkészlete, amely megmondja az elemzőnek, hogy generáljon egy elemző csomópontot az elemző fában.

A létrehozott Myna absztrakt szintaxisfa felhasználásával

Íme egy példa egy Myna által definiált elemző használatára a „Node.JS” -ben egy aritmetikai kifejezés értékeléséhez:

Utolsó szavak

Ha többet szeretne megtudni a parserek létrehozásáról és használatáról, függetlenül attól, hogy a Myna könyvtár megfelel-e az Ön speciális igényeinek, javasoljuk, hogy szánjon egy kis időt a Myna elemző könyvtár forráskódjának átolvasására.

A Myna TypeScript-ben íródott (amely a legtöbb programozó számára ismert szintaxissal rendelkezik), egyetlen fájlban található, függetlenség nélkül, és kevesebb, mint 1200 sor, a részletes dokumentációt is beleértve.

Ha kíváncsi arra, hogy a Myna egy összetettebb forgatókönyvre vonatkozik, akkor nézze meg a Chickadee programozási nyelvet. Ez teljes egészében a TypeScript-ben valósul meg, és csak a Myna elemzési könyvtárától függ. A Chickadee egy apró programozási nyelv, amelyet kifejezetten arra terveztek, hogy segítsen az embereknek megismerni a programozási nyelvek bevezetésének technikáit.

Ha tetszett ez a cikk, kérem, tudassa velem, és fontolja meg megosztását barátaival és kollégáival.