Mostanában viszonylag sokat foglalkoztam parser generátorokkal, tulajdonképpen keresem a megfelelő eszközt.
Alapvetően kétféle értelmező algoritmuscsaláddal találkoztam eddig: az LL és az (LA)LR módszerekkel.
Úgy tűnik, szinte minden nagyobb, modern értelmező program (pl. antlr) LL nyelvtannal dolgozik, amit azért nem értek, mert az LL nyelvtan nem tűri a balrekurziót, ami viszont a legtöbb CF nyelvben megtalálható, külön macera kezelni.
Miért szeretik mégis annyira az LL értelmezőket? Eddig azt láttam, hogy a balrekurzió megszüntetéséhez teljesen át kell variálni a nyelvtant, ami nem a legkellemesebb dolog. Vagy én tudok valamit rosszul?
- 6384 megtekintés
Hozzászólások
Nem tudom, mit jelent a "CF nyelv".
Az LL-t azért szeretik, mert sokkal könnyebb a parser generator-t megcsinálni, és mert a balrekurzió (állítólag) túlértékelt. (Pontosan nem emlékszem, hol olvastam -- vagy a wikipedia-ban, vagy valahol az ANTLR dokumentációjában.)
(Én csináltam LR(1) parser generator-t, ahol magát a nyelvtant is C-ben, függvényhívásokkal állítod össze, aztán megcsináltatod belőle a parser példányokat, amelyekbe aztán (akár párhuzamosan) töltöd bele az adatot, és amelyek hívogatják a redukcióknak megfelelő callback-eket. Sajnos borzasztóan elméletire sikerült a projekt -- funkcionálisan rendben lévőnek tűnt, de iszonyatosan lassú lett. Ha véletlenül érdekelne a kód (ne érdekeljen! :)), az ún. "honlapomon" megtalálod "edp" néven.)
Vannak általánosabb algoritmusok, de azoknak a futásideje rosszabb (O(n^2), O(n^3)). Az LL / LR "lényegében" lineáris az input szöveg hosszával; nincs backtrack.
A részletek már kicsit (nagyon ;)) homályosak, úgyhogy elnézést, ha baromságot írnék, de:
- LL-nél egy adott ponton vagy egyértelműen tudsz új szabály illeszteni (top-down), vagy terminálist elfogyasztani, vagy error-t kapsz; nincs backtrack. A szabályillesztés lehet "téves" is (a hiba az inputnak csak egy későbbi pontján derül ki), de ettől még gyors.
- LR-nél egy adott ponton vagy hibát kapsz, vagy shiftelsz (amely után esetleg több redukció is tüzel sorozatban, ezért neveztem úgy, hogy "lényegében" lineáris).
("n * log n"-es baromság törölve)
Egy általánosabb algoritmus pl. az http://en.wikipedia.org/wiki/Early_parser , a cikkelyben találsz linkeket továbbiakra.
Lásd még a bevezető szöveget itt: http://en.wikipedia.org/wiki/LR_parser
- A hozzászóláshoz be kell jelentkezni
Hahó!
Csak kiegészítésként egy kis irodalom a fordítóprogramokról és fordítási módszerekről, illetve a formális nyelvekről.
(Biztos, hogy ilyen témában több, kiváló magyar nyelvű könyv vagy jegyzet létezik, de én ezeket ismerem.)
G.
P.S. CF-nyelv: Context Free (környezetfüggetlen, azaz a Chomsky-nyelvosztályok közül a 2-es típusúak közé tartozó).
============================================
"Share what you know. Learn what you don't."
- A hozzászóláshoz be kell jelentkezni
Igen, én is ezekből a könyvekből tanultam/vizsgáztam 10+ éve :) Az automatás jegyzethez hibákat is jelentettem be (elgépelések voltak, ha jól emlékszem), a fentebb említett edp-t pedig a Csörnyei-jegyzetet forgatva írtam.
(Ergo a "context free" rendben van; a CF rövidítést nem láttam még.)
Szerkesztés: szerintem nagyszerű, hogy az automatás PDF még mindig szabadon letölthető; köszönöm a linket!
- A hozzászóláshoz be kell jelentkezni
Annak idején LL parserekről tanultunk (BME villamosmérnök), és ott kínlódtunk sokat a balrekurzióval. Igazából csak akkor macerás, amikor két szabály keresztbehivatkozik egymásra.
Csak mondjuk egy nagyobb nyelv nyelvtanát balrekurzió mentesíteni...
Másik ide tartozó kérdés: hogyan oldják meg a hibás input esetén, hogy tovább megy az értelmezés? (Tippem: megkeresi a szabály végét és folytatja a szabály előtti állapotból).
De pl. ezt is úgy tanultuk, hogy az LR parser képes a hiba után folytatni az elemzést, az LL-ben meg nehézkes.
(CF: CFG-ként is találkozhatsz vele)
- A hozzászóláshoz be kell jelentkezni
Hobbi projektként - prototipizáláshoz - csináltam egy Early parser implementációt, ami CF nyelvtan definíció alapján tud forrást parzolni, amit aztán fába rendezve ad vissza. Java nyelven íródott, minimális munkám lenne a publikálással, de ha érdekelne megcsinálom.
- A hozzászóláshoz be kell jelentkezni
Esetleg érdekel, bár Dunát lehet rekeszteni a parserekkel, annak idején én is írtam egyet. Ami a vicc volt, hogy amennyire tudom, teljesen egyedi (és ebből következően nem is a legjobb) megvalósítású volt. Matematikai kifejezéseket értelmezett, amit aztán numerikusan integrált (természetesen jó lassan, mert semmilyen normális módszert nem ismertem akkoriban).
Most elsősorban parser generálót keresnék, aminek megadod a nyelvtant, és abból generál értelmezőt. A Boost::Spirit ebből a szempontból nagyon tetszik, mert tiszta C++ az egész. C++ operator overloading használatával majdhogynem tisztán beviheted az EBNF (pontosabban PEG) leírásodat, és C++-kódot kapsz.
- A hozzászóláshoz be kell jelentkezni
Nem tudom, hogy ezért szeretik-e az LL elemzőket jobban, mint az LR elemzőket, de az LR elemzők sokkal terjedelmesebbek, mint az LL elemzők, és emiatt a memóriaigényük nagyobb és a futásuk hosszabb. Valószínű ez manapság már kevésbé érdekes szempont, mint régen, amikor minden byte számított memóriafoglaláskor.
- A hozzászóláshoz be kell jelentkezni
Én nem szeretem az LL parsereket. A női melleket szeretem.
Viccet félretéve, az egyik nagy előnyük az, hogy viszonylag nagy pontossággal jósolható az LL parserek implementációjának memóriaigénye és futásideje is. Ez nagy előny.
- A hozzászóláshoz be kell jelentkezni