Lefelé irányuló elemzés

A felülről lefelé történő elemzés az egyik módszer annak meghatározására, hogy egy bemeneti karakterlánc valamelyik formális nyelvhez tartozik-e, amelyet az LL(k) környezetfüggetlen nyelvtan ír le . Ez a nyelvtani elemző algoritmusok egy osztálya , ahol a formális nyelvtan szabályait a kezdőkaraktertől kezdve kiterjesztjük a szükséges tokensorozat eléréséig .

Módszerötlet

Minden nem terminális K szimbólumhoz egy függvény épül, amely bármely x bemeneti szóra két dolgot tesz:

Megkeresi egy x szó legnagyobb z kezdőpontját, amely egy K -ből származó szó eleje lehet
Meghatározza, hogy a z eredet kikövetkeztethető-e K -ből

Egy ilyen funkciónak meg kell felelnie a következő kritériumoknak:

olvassa ki a még feldolgozatlan bemeneti adatfolyamból A maximális elejét , ami a K -ből kiadott szó eleje
határozzuk meg, hogy A K-ből származtatható-e, vagy egyszerűen egy K - ből származtatható szó nem származékos eleje

Ha egy ilyen kezdet nem számítható ki (és a nemterminális K függvény helyessége bebizonyosodik), akkor a bemeneti adatok nem felelnek meg a nyelvnek, és az elemzést le kell állítani.

Az elemzés a fent leírt függvények meghívásából áll. Ha van összetett szabály az olvasási nem terminálhoz, akkor annak elemzésekor más függvények is meghívásra kerülnek a benne foglalt terminálok elemzésére. A "felső" függvénytől induló hívásfa egyenértékű az elemzőfával.

A rekurzív leszármazási módszerrel az elemző létrehozásának legegyszerűbb és „leghumánusabb” módja az egyes következtetési szabályok közvetlen programozása a nyelvtani nem terminálokhoz.

Felhasználási feltételek

Legyen N nem terminális szimbólumok véges halmaza egy adott formális nyelvtanban; Σ terminális szimbólumok véges halmaza, akkor a rekurzív leszármazási módszer csak akkor alkalmazható, ha a nyelvtan minden szabályának a következő alakja van:

vagy , ahol , és ez az egyetlen kimeneti szabály ehhez a nem terminálhoz $A\jobbra nyíl\alfa$ $\alpha \subset (\Sigma \cup N)*$
vagy mindenkinek $A\jobbra nyíl a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$ $i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$

Felülről lefelé irányuló elemzési algoritmusok

Rekurzív leszálló elemző ( en:Recursive decent parser )
LL elemző ( en:LL elemző )
Junk Parser ( en:Packrat parser )

Irodalom

A. Shen . Programozás: tételek és feladatok. 2. kiadás, M.: MTsNMO, 2004
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Fordítók: alapelvek, technikák és eszközök = Compilers: Principles, Techniques and Tools. - 2. kiadás - M .: Williams , 2008. - ISBN 978-5-8459-1349-4 .
Robin Hunter. Alapvető fordítói fogalmak = A fordítók lényege. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .