Lásd még LL(1)
Az LL elemző ( LL parser ) egy felülről lefelé haladó elemző a számítástechnikában a környezetfüggetlen nyelvtanok egy részhalmazához , amely LL nyelvtanként ismert . Azonban nem minden környezetfüggetlen nyelvtan LL nyelvtan.
Az L betűk az "LL parser" kifejezésben azt jelentik, hogy a bemeneti karakterláncot balról jobbra elemezzük, és ezzel egyidejűleg a bal szélső származékát építjük fel.
Az LL elemzőt LL(k) elemzőnek nevezzük, ha ez az elemző előretekintést használ k tokenre (token) a bemeneti folyam elemzésekor. Az LL(k) elemző által visszalépés nélkül felismerhető nyelvtant LL(k) nyelvtannak nevezzük. Az LL(k)-nyelvtanként ábrázolható nyelvet LL(k)o-nyelvnek nevezzük. Vannak LL(k+n)-nyelvek, amelyek nem LL(k)-nyelvek.
Az alábbiakban az analizátort ismertetjük, amely táblázatok felépítésén alapul; alternatíva a rekurzív leszármazási elemző, amelyet általában kézzel írnak (bár vannak kivételek, például az ANTLR elemző generátor LL(*) nyelvtanokhoz).
Az LL(1) nyelvtanok nagyon elterjedtek, mert a hozzájuk tartozó LL elemzők csak egy karakterrel előre nézik az adatfolyamot, amikor eldöntik, melyik nyelvtani szabályt alkalmazzák. A nagy k-értékű nyelvtanokon alapuló nyelveket hagyományosan nehezen felismerhetőnek tartották, bár az LL(k) nyelvtanokat tetszőleges k-val támogató elemző generátorok elterjedt használata miatt ez a megjegyzés már nem releváns.
Az LL elemzőt LL(*) értelmezőnek nevezzük, ha nincs szigorú megkötés a k-ra, és az elemző fel tudja ismerni a nyelvet, ha a tokenek valamilyen szabályos halmazhoz tartoznak (például determinisztikus véges automaták használatával ).
Ellentmondások vannak az LL nyelvtanokra épülő, úgynevezett "európai nyelvkonstrukciós iskola" és az LR nyelvtanokat előnyben részesítő "amerikai iskola" között. Az ilyen ellentmondások hátterében a tanítás hagyományai és a különböző módszerek, eszközök konkrét tankönyvekben történő leírásának részletei állnak; szintén befolyásolta N. Wirth of ETHZ , akinek kutatásai különböző módszereket írnak le az LL(1) feloldók és fordítók optimalizálására.
Az értelmezőt arra tervezték, hogy megoldja azt a problémát, hogy egy karakterlánc egy adott nyelvtanhoz tartozik-e, és ha igen, akkor létrehoz egy kimeneti fát.
Az elemző a következőkből áll:
A táblázat soraiban a bolti ábécé szimbólumai, az oszlopokban pedig a terminál ábécé szimbólumai találhatók.
Az elemzés megkezdésekor a verem már két karaktert tartalmaz:
[ S, $ ]Ahol a „$” egy speciális terminál, amely a verem végét jelzi, az „S” pedig a nyelvtan axiómája. Az elemző a nyelvtani szabályok segítségével megpróbálja lecserélni a veremben lévő axiómát a bemeneti szalagon lévő karakterlánchoz hasonló karakterláncra, majd teljesen beolvassa a szalagot, kiürítve a veremet.
Az LL elemző működésének magyarázatához vegye figyelembe a következő nyelvtant:
És elemezzük az elemzést egy karakterlánc példáján:
(1+1)A nyelvtan elemző táblázata így néz ki:
| ( | ) | egy | + | $ | |
| S | 2 | — | egy | - | - |
| F | — | — | 3 | - | - |
Van egy oszlop is egy speciális terminál számára, amelyet $ jelöl, amely a bemeneti folyam végét jelzi. A cellákban lévő (félkövéren szedett) számok a fent jelzett szabályok számait jelzik.
Az elemző a bemeneti adatfolyam első "(" karakterét nézi, ebben a pillanatban az "S" karakter a verem tetején van, az értelmező táblában ezeknek az értékeknek a metszéspontjában van egy szabály a nyelvtanból Ebben a példában ez a 2-es szabály, amely a veremben az „S” karakter helyettesítésére utasítja az „(S + F)” karakterláncot. A verem állapota a szabály alkalmazása után:
[ (, S, +, F, ), $ ]A következő lépésben az elemző beolvassa a '(' karaktert a bemeneti adatfolyamból. Mivel a verem tetején van egy hasonló '(' karakter), ezt a karaktert a rendszer kiolvassa a szalagról és eltávolítja a veremből. a verem a szabály alkalmazása után a következő:
[S, +, F, ), $]A szalagon ezután az „1” szimbólum található, az „S” verem tetején, a táblázatban a szimbólumok metszéspontjában található az 1. szabály. A szabály alkalmazása után a táblázat szerint az analizátor alkalmazza. 3. szabály. A verem állapota a szabályok alkalmazása után:
[ F, +, F, ), $ ] [ 1, +, F, ), $ ]Ezután az elemző beolvassa az „1” és „+” jeleket a bemeneti adatfolyamból, és mivel ezek megfelelnek a verem következő két elemének, eltávolítja őket a veremből. Ennek eredményeként a verem így néz ki:
[ F, ), $ ]A következő három lépésben a verem 'F' karaktere '1'-re változik, majd az '1' és ')' karakterek beolvasásra kerülnek a szalagról, és eltávolításra kerülnek a veremből. Ennek eredményeként a '$' szimbólum a verem tetején és a szalagon lesz, a definíció szerint ez a lánc sikeres elemzését jelenti.
Ebben az esetben az elemző jelentést küld a sikerről, és visszaadja a következtetési folyamat során alkalmazott szabályok listáját:
[2, 1, 3, 3]Ezek a szabályok valóban a bal szélső következtetések:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Amint a példából látható, az elemző három különböző dolgot csinál attól függően, hogy a verem teteje nem terminál, terminál vagy $ speciális karakter:
Ezeket a lépéseket addig ismételjük, amíg meg nem áll. A leállás után vagy hibaüzenetet kapunk, vagy üzenetet arról, hogy a láncot sikeresen felismertük.
Az elemző tábla feltöltéséhez meg kell határozni, hogy az elemző melyik nyelvtani szabályt válassza, ha a nem terminál A a verem tetején, az a karakter pedig a bemeneti adatfolyamban van. Könnyen belátható, hogy egy ilyen szabálynak A → w alakúnak kell lennie, és a w -nek megfelelő nyelvnek legalább egy sorral kell kezdődnie . Ebből a célból definiáljuk a w első halmazát , amelyet itt Fi(w) -ként írunk le, mint azon terminálok halmazát, amelyek w bármely sorának elején találhatók , és ε, ha az üres sor is w -hez tartozik . Adott egy A 1 → w 1 , …, A n → w n szabályokkal rendelkező nyelvtan minden szabályhoz a következőképpen számítható ki Fi(w i ) és Fi(A i ) :
Sajnos az első készletek nem elegendőek egy elemző tábla elkészítéséhez. Ennek az az oka, hogy a szabály jobb oldala w végül az üres karakterláncba kerülhet. Így az elemzőnek is használnia kell az A → w szabályt , ha ε Fi(w) -ben van, és a bemeneti adatfolyamban egy olyan karakter, amely követheti A -t . Ezért szükség van egy Következő A halmaz létrehozására is (itt Fo(A) -ként írjuk ), amely terminálok halmazaként van definiálva úgy, hogy legyen egy αAaβ karakterlánc , amelyet a kezdőkarakterből kaphatunk. A következő halmazok kiszámítása a nyelvtan nem terminusaihoz a következőképpen végezhető el:
Most pontosan meghatározhatja, hogy mely szabályok legyenek az elemző táblában. Ha T[A, a] egy bejegyzést jelöl a táblázatban egy nem terminál A és egy a terminálhoz , akkor
T[A,a] akkor és csak akkor tartalmazza az A → w szabályt , ha:
Ha a táblázat minden cellában legfeljebb egy szabályt tartalmaz, akkor az elemző egyértelműen meg tudja határozni, hogy melyik szabályt kell alkalmazni az egyes elemzési lépésekben. Ebben az esetben a nyelvtant LL(1) nyelvtannak nevezzük .
Az elemző tábla mérete a legrosszabb esetben k függvényében exponenciális bonyolultságú . A Compiler Construction Toolkit (PCCTS, ma ANTLR néven ismert ) 1992 körüli megjelenése után azonban kiderült, hogy a legtöbb programozási nyelv elemzőtáblájának mérete nem szokott exponenciálisan növekedni, mivel nem ez a legrosszabb ügy. Emellett bizonyos esetekben még LL( * )-analizátorokat is lehetett készíteni. Ennek ellenére azonban a hagyományos értelmező generátorok, mint például a yacc / GNU bison , LALR( 1 ) elemző táblákat használnak egy korlátozott LR elemző létrehozásához .
A modern elemző generátorok az LL nyelvtanokhoz, több továbbítási várakozással, a következők:
| Formális nyelvek és formális nyelvtanok | |
|---|---|
| Általános fogalmak | |
| Típus 0 | |
| 1. típus |
|
| 2. típus | |
| 3. típus |
|
| elemzése | |