Nyelvtan egy kifejezés elemzése

A kifejezés-elemző nyelvtan (PB-grammar) az analitikus formális nyelvtan egy olyan típusa, amely a formális nyelvet a nyelvi karakterláncok felismerésének szabályai alapján írja le. Egy kifejezést elemző nyelvtan lényegében egy rekurzív leszálló elemző , pusztán sematikus formában, amely csak a szintaxist fejezi ki, és független az értelmező konkrét megvalósításától vagy használatától. A kifejezéselemző nyelvtanok hasonlóak a reguláris kifejezésekhez és a kontextusmentes nyelvtanokhoz (CFG) a Backus-Naur jelölésben , de eltérő értelmezésük van.

A COP nyelvtanokkal ellentétben a PB nyelvtanok nem lehetnek kétértelműek : ha egy karakterláncot elemzünk, akkor pontosan egy értelmezőfa létezik. Ezáltal a RE-grammatika alkalmas számítógépes nyelvekre, de nem természetes nyelvekre.

Definíció

Formálisan a kifejezést elemző nyelvtan a következőkből áll:

Minden P-ből származó következtetési szabály A ← e alakú, ahol A egy nem terminális szimbólum, és e egy elemzési kifejezés. Az elemző kifejezés egy hierarchikus kifejezés, amely hasonló egy reguláris kifejezéshez , amely így épül fel:

  1. Az atomi elemzési kifejezés a következőkből áll:
    • bármilyen terminál karakter,
    • bármely nem terminális szimbólum, vagy
    • üres string ε.
  2. Adott az e, e 1 és e 2 elemzési kifejezések, a következő utasítások új elemzési kifejezéseket generálnak:
    • Sorrend: e 1 e 2
    • Rendezett választék: e 1 / e 2
    • Nulla vagy több: e*
    • Egy vagy több: e+
    • Nem kötelező: e?
    • És állítmány: &e
    • NEM állítmány: !e

Az alapvető különbség a PB-nyelvtan és a COP-nyelvtan között az, hogy a PB-nyelvtan választási operátora rendezett . Ha az első alternatíva működik, akkor az összes következőt figyelmen kívül hagyja . Így a rendezett választás nem kommutatív, ellentétben a kontextusmentes nyelvtanok és reguláris kifejezések könyvi definícióival. A rendezett kiválasztás hasonló a soft cut operátorhoz néhány logikai programozási nyelvben.

Következésképpen, amikor egy CFG-t közvetlenül RTG-vé alakítunk, minden kétértelműség determinisztikusan feloldódik az egyik lehetséges elemzési fa javára. A nyelvtani alternatívák megadásának sorrendjének gondos megválasztásával a programozó jelentős mértékben szabályozhatja, hogy melyik értelmezőfát válassza.

A logikai kontextusmentes nyelvtanokhoz hasonlóan a RE nyelvtanoknak is vannak ÉS és NEM predikátumai. Segítenek további egyértelművé tételben, ha az alternatívák átrendezése nem tudja létrehozni a kívánt elemzőfát.

Elemző kifejezések értelmezése

A PB-nyelvtan minden nem terminálja lényegében egy értelmező függvény egy rekurzív leszármazott elemzőben, és a megfelelő értelmező kifejezés ennek a függvénynek a "kódja". Minden elemző függvény egy karakterláncot vesz be bemenetként, és a következő eredmények egyikét adja:

A nem terminál sikeres lehet anélkül, hogy elnyelné a bemenetet, és ez az állapot különbözik a meghibásodástól.

Az egyetlen terminálból álló atomi elemzési kifejezés sikeres, ha a bemeneti karakterlánc első karaktere egyezik és felhasználja azt. Ellenkező esetben az eredmény sikertelen. Egy üres karakterláncból származó atomi kifejezés mindig sikerül anélkül, hogy elfogyna. A nem terminális A -ból álló atomi kifejezés az A nem terminális függvény rekurzív hívása .

Az e 1 e 2 szekvencia operátor először meghívja az e 1 -et, majd ha e 1 sikeres, akkor az e 1 által fel nem használt sztring részének hívja az e 2-t, és visszaadja az eredményt. Ha e 1 vagy e 2 meghiúsul, akkor az e 1 e 2 sorozatoperátor is meghiúsul .

Az e 1 / e 2 kiválasztási utasítás először meghívja az e 1 -et , és ha az e 1 sikeres, visszaadja az eredményét. Ellenkező esetben, ha az e 1 meghiúsul, a select utasítás visszaállítja a bemeneti karakterláncot az e 1 hívása előtti állapotba, és meghívja az e 2 -t, visszaadva az eredményt.

A nulla vagy több, az egy vagy több és az opcionális operátorok nulla vagy több, egy vagy több, vagy nulla vagy egy egymást követő előfordulását veszik fel e részkifejezésükből . A CFG-kkel és a reguláris kifejezésekkel ellentétben ezek az operátorok mindig mohók, és annyi bemeneti példányt fogyasztanak, amennyit csak tudnak. (A reguláris kifejezések mohón indulnak, de aztán visszaesnek, és megpróbálnak rövidebb sorozatot találni.) Például az a* kifejezés mindig felhasználja az összes elérhető a-t, és az (a* a) kifejezés mindig sikertelen lesz, mert az a* első részének végrehajtása után nem marad a második számára.

Végül az ÉS-predikátum és a NOT-predikátum szintaktikai predikátumokat valósít meg. Az & e kifejezés az e részkifejezést hívja , és sikert ad vissza, ha e sikeres, máskülönben kudarcot, de soha nem használ inputot. Hasonlóképpen a kifejezés ! e sikeres, ha e sikertelen, és sikertelen, ha e sikeres, ismét anélkül, hogy elnyelné a bemenetet. Mivel az e kifejezés tetszőlegesen összetett konstrukció lehet, amely "előre" kiértékelhető a bemeneti karakterlánc felhasználása nélkül, ezek a predikátumok hatékony szintaktikai előkészítő és egyértelműsítő eszközöket biztosítanak.

Példák

A következő RW nyelvtan a matematikai képleteket négy művelettel ismeri fel nem negatív egész számokon.

Érték ← [0-9]+ / '(' Kif ')' Termék ← Érték (('*' / '/') Érték)* Összeg ← Termék (('+' / '-') Termék)* Kifejezés ← Összeg

A fenti példában a terminálkarakterek egy idézőjeles karakterekkel jelzett szövegkarakterek, például '('és ')'. A tartomány [0-9]a 0 és 9 közötti számokat képviselő tíz karakter rövidítése. (Ez ugyanaz, mint a reguláris kifejezések szintaxisa). A nem terminális szimbólumok olyan szimbólumok, amelyekhez vannak kimeneti szabályok: Érték , Termék , Összeg és Kifejezés .

Az alábbi példák nem tartalmaznak idézőjeleket az olvashatóság javítása érdekében. A kisbetűk terminális karakterek, a nagy dőlt betűk pedig nem terminálisok. A valódi PB-nyelvtani elemzők idézőjeleket igényelnek.

Az elemzési kifejezés (a/b)* egyezik és felhasználja az a és b tetszőleges hosszúságú sorozatait. Szabály S ← a S ? b egy egyszerű környezetfüggetlen nyelvet ír le . A következő RW nyelvtan egy klasszikus, nem kontextusmentes nyelvet ír le :

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

A következő rekurzív szabály megfelel egy szabványos C if/then/else utasításnak úgy, hogy az opcionális else blokk mindig megegyezik a legbelső if-vel. (Egy kontextusmentes nyelvtanban ez a klasszikus „kilógó más” kétértelműséghez vezetne.)

S ← 'ha' C 'akkor' S 'más' S / 'ha' C 'akkor' S

A foo &(bar) elemző kifejezés megegyezik a "foo" szöveggel és felhasználja azt, de csak akkor, ha azt a "bar" szöveg követi. A foo !(bar) elemző kifejezés csak akkor használja fel a "foo" szöveget, ha nem követi a "bar". Az !(a+ b) a kifejezés egyetlen "a" karaktert tartalmaz, de csak akkor, ha nem az első egy tetszőleges hosszúságú a sorozatban, amelyet b követ.

A következő rekurzív szabály egy beágyazott Pascal megjegyzésnek felel meg. A megjegyzés karakterek idézőjelek közé vannak zárva, hogy megkülönböztessék őket az RVG operátoroktól.

Kezdje ← '(*' vége ← '*)' C ← Kezdete N* Vége N ← C / (!Kezdje !Vége Z) Z ← tetszőleges karakter

RW-grammatikai elemzők megvalósítása

Bármely RH nyelvtan rekurzív leszármazással közvetlenül átalakítható elemzővé. A korlátlan előelemzési képesség miatt az eredményül kapott értelmező legrosszabb esetben exponenciális időn belül futhat.

Emlékezve a közbenső elemzési lépések eredményére, és megbizonyosodva arról, hogy minden elemző függvényt legfeljebb egyszer hívnak meg a bemeneti adatok adott pozíciójához, lehetséges bármilyen PB nyelvtan átalakítani egy packrat elemzővé , amely mindig lineáris időben fut a memóriaköltségek jelentős növekedésének rovására.

A packrat elemző egyfajta értelmező, amely a rekurzív leszármazáshoz hasonló módon működik, azzal a különbséggel, hogy elemzéskor megjegyzi a kölcsönösen rekurzív elemző függvények hívásainak köztes eredményeit. Emiatt a packrat elemző képes számos kontextusmentes nyelvtant és bármilyen PB nyelvtant elemezni (beleértve azokat is, amelyek nem kontextusmentes nyelveket generálnak) lineáris időben [1] .

Az RW nyelvtanokhoz LL és LR értelmezőt is lehet építeni, de ebben az esetben elvész a korlátlan előelemző képesség.

Előnyök

A REGRAM-ok jó helyettesítői a reguláris kifejezéseknek , mert szigorúan erősebbek. Például egy reguláris kifejezés alapvetően nem találja a megfelelő zárójelpárokat, mert nem rekurzív, ellentétben a RE nyelvtannal.

Bármely RH nyelvtan lineáris időben elemezhető a packrat elemzővel a fent leírtak szerint.

A COP-nyelvtanok által képviselt nyelvek értelmezői, például az LR-elemzők speciális lexikális elemzési lépést igényelnek, amely felosztja a bemenetet szóközök, írásjelek stb. szerint. Erre azért van szükség, mert ezek az elemzők előelemzést használnak egyes CFG-k lineáris időben történő feldolgozásához. Az RW nyelvtanok nem igényelnek külön lexikális elemzési lépést, ennek szabályait más nyelvtani szabályokkal együtt lehet lefektetni.

Sok COP nyelvtan jelentős kétértelműséget tartalmaz, még akkor is, ha egyértékű nyelveket kellene leírnia. Ennek a jelenségnek az egyik példája a C, C++ és Java „lógás másik” problémája. Ezeket a problémákat gyakran a nyelvtanon kívüli szabály alkalmazásával oldják meg. A PB nyelvtanban ezek a kétértelműségek soha nem merülnek fel a prioritás miatt.

Hátrányok

Memóriafogyasztás

A PB nyelvtan elemzését általában egy packrat elemző végzi, amely megjegyzi a további elemzési lépéseket. Az ilyen elemzéshez az adatokat a bemenet hosszával arányosan kell tárolni, szemben az LR elemzők elemzési fa mélységével. Ez számos területen jelentős előnyt jelent: például az ember által írt kódok általában közel állandó beágyazási mélységgel rendelkeznek, függetlenül a program hosszától – a bizonyos mennyiségnél mélyebb kifejezéseket általában újrafaktorálják.

Egyes nyelvtanok és egyes bemenetek esetében az elemző fa mélysége arányos lehet a bemenet hosszával, így egy olyan kiértékelésnél, amely nem veszi figyelembe ezt a mértéket, a packrat elemző ugyanolyan jónak tűnhet, mint egy LR elemző. Ez hasonló a gráfalgoritmusok helyzetéhez: Bellman-Ford és Floyd-Warshall végrehajtási ideje ( ), ha csak a csúcsok számát vesszük figyelembe. Egy pontosabb, az élek számát figyelembe vevő elemzés azonban megmutatja a Bellman-Ford algoritmus végrehajtási idejét , amely a bemenet méretéhez képest csak másodfokú, nem köbös.

Közvetett bal oldali rekurzió

A RE-grammatika nem tartalmazhat balra rekurzív szabályokat, amelyek soremelés nélkül hívják magukat. Például a fent leírt számtani nyelvtanban szeretnék néhány szabályt áthelyezni, hogy a szorzat és az összeg elsőbbsége egy sorban kifejezhető legyen:

Érték ← [0-9.]+ / '(' Kif ')' Termék ← Expr (('*' / '/') Expr)* Összeg ← Kif (('+' / '-') Kif)* Expr ← Termék / Összeg / Érték

A probléma itt az, hogy ahhoz, hogy az Expr találatot kapja , ellenőriznie kell, hogy a termék aktiválódik-e , és a Termék ellenőrzéséhez először az Expr -t kell bejelölnie . Ez pedig lehetetlen.

A bal oldali rekurzív szabályok azonban mindig átírhatók a bal oldali rekurzió kiküszöbölésére. Például egy bal oldali rekurzív szabály korlátlanul megismételhet néhány kifejezést, mint a CF-grammatikai szabályban:

string-of-a ← string-of-a 'a' | 'a'

Ez átírható egy PB nyelvtanban a + operátor segítségével:

string-of-a ← 'a'+

Néhány módosítással lehetővé válik, hogy egy normál packrat elemző támogassa a közvetlen bal oldali rekurziót [1] [2] [3] .

Az indirekt bal-rekurzív szabályok átírásának folyamata azonban nehéz, különösen, ha szemantikai műveletekre kerül sor. Bár elméletileg lehetséges, nincs olyan RW elemző, amely támogatja a közvetett bal oldali rekurziót, míg az összes GLR elemző támogatja.

Finom nyelvtani hibák

Ahhoz, hogy egy nyelvtant PB nyelvtanként fejezzen ki, a szerzőjének a nem-determinisztikus választás összes példányát rendezett választássá kell alakítania. Sajnos ez a folyamat hibás, és gyakran olyan nyelvtanokat eredményez, amelyek hibásan elemzik a bemenet egy részét.

Kifejezőség

A Packrat elemzők nem tudnak néhány egyértelmű nyelvtant elemezni, mint például a következők [4] :

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

Fejlesztés

A RE nyelvtanok újak, és nem használják széles körben. A reguláris kifejezések és a COP nyelvtanok viszont már évtizedek óta léteznek, az ezeket elemző kódot továbbfejlesztették és optimalizálták, a programozóknak van tapasztalatuk a használatukban.

Linkek

Jegyzetek

  1. ↑ 1 2 Ford, Bryan Packrat elemzése: gyakorlati lineáris idő algoritmus visszakövetéssel . Massachusetts Institute of Technology (2002. szeptember). Hozzáférés dátuma: 2007. július 27. Az eredetiből archiválva : 2012. április 2.
  2. ↑ Alessandro Warth, James R. Douglass, Todd Millstein. A Packrat elemzők támogatják a bal oldali  rekurziót . - Nézőpontok Kutatóintézet, 2008. - január.
  3. ↑ Ruedi Steinmann. Bal oldali rekurzió kezelése Packrat elemzőben  (neopr.) . - 2009. - március. Archiválva az eredetiből 2011. július 6-án. Archivált másolat (nem elérhető link) . Letöltve: 2009. június 17. Az eredetiből archiválva : 2011. július 6.. 
  4. ↑ Bryan Ford. Funkcionális gyöngy: Packrat elemzés: egyszerű, erőteljes, lusta, lineáris idő  (angolul)  : napló. – 2002.