Az LR parser ( eng. LR parser ) egy elemző valamilyen programozási nyelven írt programok forráskódjaihoz, amely a bemeneti adatfolyamot balról ( L eft) jobbra olvassa, és előállítja a kontextusmentes nyelvtan jobb szélső ( Right ) produkcióját. . Használják az LR( k )-analyzer kifejezést is , ahol k azt fejezi ki, hogy a bemeneti adatfolyamban hány olvasatlan előnézeti karakter van, amely alapján az elemzés során döntéseket hoznak. Általában k értéke 1, és gyakran kihagyják.
Számos programozási nyelv szintaxisa meghatározható egy LR(1) vagy ahhoz közeli nyelvtan segítségével, ezért a fordítók gyakran használják az LR elemzőket a forráskód elemzésére.
Az elemzőre általában annak a nyelvnek a nevével kapcsolatban hivatkozunk, amelynek forráskódját elemzi, például a „C++ értelmező” a C++ forráskódot elemzi .
Az LR elemző előállítható környezetfüggetlen nyelvtanból egy parser generator nevű programmal , vagy megírhatja kézzel egy programozó. A környezetfüggetlen nyelvtan LR( k ) -nek minősül, ha van hozzá LR( k ) értelmező, amint azt az értelmező generátor határozza meg.
Az LR elemzőről azt mondják, hogy alulról felfelé értelmező , mert megpróbál következtetni a nyelvtan legfelső szintű előállítására úgy, hogy levelekből építi fel .
A determinisztikus kontextusmentes nyelv olyan nyelv, amelyre létezik valamilyen LR( k ) nyelvtan. Mindegyik LR( k ) nyelvtan automatikusan konvertálható LR( 1 ) nyelvtanrá ugyanarra a nyelvre, míg előfordulhat, hogy egyes nyelvekhez nem léteznek LR( 0 ) nyelvtanok. Az LR( 0 )-nyelvek a determinisztikus nyelvek saját részhalmazai.
Az LR elemző egy értelmező tábla által vezérelt algoritmuson alapul, amely az elemzett nyelv szintaxisát tartalmazó adatstruktúra. Tehát az LR értelmező kifejezés valójában az elemzők egy osztályára utal, amely szinte minden olyan programozási nyelvet képes elemezni, amelyhez az értelmező táblázat rendelkezésre áll. Az elemző táblát az értelmező generátor hozza létre.
Az LR-elemzés általánosítható egy környezetfüggetlen nyelv tetszőleges elemzéseként teljesítményveszteség nélkül, még az LR(k) nyelvtanok esetében is. Ennek az az oka, hogy a legtöbb programozási nyelv kifejezhető LR( k ) nyelvtannal, ahol k egy kis konstans (általában 1). Megjegyzendő, hogy a nem LR(k) nyelvtanok elemzése egy nagyságrenddel lassabb (a bemeneti adatfolyam méretét tekintve köbös, nem másodfokú).
Az LR-elemzés több nyelven alkalmazható, mint az LL-elemzés , és a hibajelentésben is jobb, ami azt jelenti, hogy a lehető legkorábban észleli azokat a szintaktikai hibákat, amelyekben a bemenet nem egyezik a nyelvtannal. Ezzel szemben az LL(k) (vagy még rosszabb, még az LL(*)) elemzők a visszagörgetés miatt késleltethetik a hiba észlelését a nyelvtan másik ágára, ami gyakran megnehezíti a hiba megtalálását a gyakori hosszú előtagok helyén.
Az LR értelmezőket nehéz kézzel létrehozni, és általában értelmező-generátor vagy fordító-fordító hozza létre . Az elemző tábla létrehozásának módjától függően ezeket az értelmezőket egyszerű LR elemzőknek (SLR), előretekintő LR elemzőknek (LALR) vagy kanonikus LR elemzőknek nevezhetjük . Az LALR elemzők lényegesen nagyobb felismerési képességgel rendelkeznek, mint az SLR elemzők . Ugyanakkor a tükörreflexes analízis táblázatai ugyanolyan méretűek, mint az LALR analízisé, így az SLR elemzést már nem használják. A kanonikus LR értelmezők valamivel nagyobb felismerési képességgel rendelkeznek, mint az LALR elemzők, de sokkal több táblamemóriát igényelnek, ezért ritkán használják őket. .
| Formális nyelvek és formális nyelvtanok | |
|---|---|
| Általános fogalmak | |
| Típus 0 | |
| 1. típus |
|
| 2. típus | |
| 3. típus |
|
| elemzése | |