LALR
У рачунарству и информатици LALR парсер, што је скраћеница од енгл. термина “lookahed LR parser” је посебан облик LR парсера који може да изађе на крај са више контекстно слободних граматика него SLR парсер (скраћено од енгл. simple LR парсер). LALR парсер је врло популаран тип парсера зато што прави добар компромис између броја граматика за које је применљив и величине таблице синтаксне анализе коју захтева. Компилатори најчешће користе овај тип парсера, такви су на пример YACC и GNU bison.
Као и SLR, LALR таблица синтаксне анализе се добија поправком технике конструкције таблице LR(0) синтаксне анализе.
Разликују се следеће поткласе {LR} граматика:
- LR(0), ако су таблице анализе формиране без обзира на предувидни симбол, а у процесу анализе се не јављају конфликти;
- SLR(1), ако је конфликте који се јављају у LR(0) анализи могуће отклонити узимајући у обзир све скупове Следећи симбола граматике;
- LALR(1), ако је конфликте који су се појавили у SLR(1) анализи могуће отклонити ограничавањем скупова Следећи само на оне симболе који су неопходни да би се извршила акција свођења;
- (канонска) LR(1) ако је за решавање конфликта у LALR(1) анализи потребно једној реченичној форми доделити више стања аутомата;
Скуп Следећи(А) за задати незавршни симбол А садржи све завршне симболе који се могу појавити непосредно иза симбола А, без обзира на контекст. Природа коначног аутомата какав је конструисан за LR(0) ајтеме је таква да се не захтева познавање свих симбола који могу следити за неким симболом А. Довољно је познавати скуп оних завршних симбола који се могу појавити на улазу када се изврши свођење по неком А правилу. У таквом случају скуп релевантних предувидних симбола је подскуп скупа Следећи(А) који ћемо назвати Предувидни скуп.
Предувидни скуп за помоћни симбол А се конструише тако што се у коначном аутомату посматрају само они завршни симболи који се могу појавити иза А непосредно после акције свођења на А. У случају појаве конфликта пребацивање-свођење, за његово разрешавање су од значаја само оне секвенције у ајтемима које су облика:
•Аа
где је а неки завршни терминал. Анализом ових секвенција омогућава се да коначни аутомат може да препозна да ли је потребно извршити свођење или не.
Дакле, док SLR корсти скупове Следећи за одређивање акција свођења, LALR користи предувидне скупове. Како је за дати LR(0) ајтем I, скуп Следећи(I) у ствари унија свих Предувидних скупова за све LR(0) ајтеме са истом левом страном као I, и као такав независан од стања парсера и десне стране ајтема, па тиме не носи информације о контексту. Са друге стране скуп Предувидни у зависности од контекста омогућава финије разрешавање конфликата.
Конструкција LALR(1) се може извршити тако што се прво конструише SLR(1) аутомат коме се затим додају предувидни симболи. Они се додају тако што се идентификују симболи који прате један ајтем. У случају свођења, ти симболи имају улогу скупа Следећи у случају SLR(1) анализе. Оваква конструкција је ефикаснија од конструисања канонског LR(1) аутомата, а затим стапања његових стања.
Пример
уреди- Нека на улазу имамо ниску { a + b = c ; } EOF
- Почињемо постављајући стање 0 на врх стека.
- Ево како LALR парсер излази на крај са њом:
| стања на стеку | ајтеми | акција | преостали улаз |
| 0 | програм → • { наредбе EOF } | пребацивање | { a = b + c ; } EOF |
| 1 0 | програм → { • наредбе EOF }
наредбе → • наредба наредбе наредбе → • e наредба → • ID=израз наредба → • IF израз |
пребацивање | a = b + c ; } EOF |
| 4 1 0 | наредба → ID • = израз | пребацивање | = b + c ; } EOF |
| 8 4 1 0 | наредба → ID = • израз
израз → • израз + ID израз → • израз - ID израз → • ID |
-пребацивање- | b + c ; } EOF |
| 12 8 4 1 0 | израз → ID • | сведи по 8 | + c ; EOF |
| 11 8 4 1 0 | наредба → ID = израз •
израз → израз • + ID израз → израз • - ID |
пребацивање | + c ; } EOF |
| 15 11 8 4 1 0 | израз → израз + • ID | пребацивање | c ; } EOF |
| 18 15 11 8 4 1 0 | израз → израз + ID • | сведи по 6 | ; } EOF |
| 11 8 4 1 0 | наредба → ID = израз • ;
израз → израз • + ID израз → израз • - ID |
пребацивање | ; } EOF |
| 14 11 8 4 1 0 | наредба → ID = израз ; • | сведи по 4 | } EOF |
| 3 1 0 | наредбе → наредба • наредбе
наредбе → • наредба наредбе наредбе → e • наредба → • ID = израз наредба → • IF ( израз ) |
сведи по 3 | } EOF |
| 7 3 1 0 | наредбе → наредба наредбе • | сведи по 2 | } EOF |
| 2 1 0 | програм → { наредбе EOF • } | пребацивање | } EOF |
| 6 2 1 0 | програм → { наредбе • EOF } | прихвати | EOF |
LALR(1) граматике
уредиФормална дефиниција LALR(1) граматике не може се једноставно упаковати у скуп правила. Уместо формалне дефиниције, можемо рећи да је граматика LALR(1) ако постоји њој одговарајући LALR(1) парсер са одсуством конфликта, и обрнуто. LALR(1) је поткласа од LR(1) и наткласа од SLR(1). Граматика која није LR(1) дефинитивно није ни LALR(1), јер који год конфликт да је присутан за оригинални LR(1) парсер, биће присутан и за LALR(1) парсер. Граматика која је LR(1) може али не мора бити LALR(1) у зависности од тога да ли стапање производи конфликте или не. Граматика која је SLR(1) је дефинитивно и LALR(1). Граматика која није SLR(1) може и не мора бити LALR(1) у зависности од тога да ли прецизнији Предувидни скупови разрешавају SLR(1) конфликте.
LALR(1) парсер се показао као најчешћа варијанта фамилије LR парсера. Слабости SLR(1) и LR(0) парсера су у томе што су способни да изађу на крај са релативно малим скупом граматика. Експанзивне меморијске потребе LR(1) парсера учиниле су да је годинама био теоретски интересантан али постепено практично све приближнији. Предност LALR(1) парсера огледала се у томе што је понудио добар баланс између моћи скупова Предувида и величине таблице синтаксне анализе. Већина конструкција над програмским језицима може бити описана LALR(1) граматиком.
Литература
уреди- Витас, Душко М., „Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика )“, Математички факултет, Београд 2006.
- [1] LALR Parsing, written by Maggie Johnson and revised by Julie Zelenski and Keith Schwarz, July 11, 2012