Parser LR

Parser LR (ang. Left to right, identifying the Rightmost production) – analizator składniowy dla gramatyk bezkontekstowych, który przetwarza wejście od lewej do prawej metodą wstępującą i produkuje prawostronne wyprowadzenie. Terminu parser LR(k), gdzie k jest liczbą naturalną lub zerem, używa się do oznaczenia analizatorów podejmujących decyzje na podstawie k podglądanych symboli na wejściu, użytych w podjęciu decyzji. Zwykle k jest równe 1 i jest często pomijane. Parser SLR i parser LALR również są typu LR, jednak pod pojęciem LR(k) zwykle mamy na myśli "kanoniczny parser LR(k)". W typowym użyciu "parser LR" oznacza konkretny parser zdolny rozpoznać konkretny język określony gramatyką bezkontekstową. Gramatyka bezkontekstowa nazywa się gramatyką LR(k), jeżeli istnieje dla niej parser LR(k). Mówimy że parser LR wykonuje analizę metodą wstępującą (ang. bottom-up), ponieważ próbuje wyprowadzić produkcję najwyższego poziomu poprzez analizowanie liści. Analizowanie typu LR przynosi następujące korzyści: * parsery LR są często używane przez kompilatory do uprzedniej analizy składniowej (syntaktycznej) kodu źródłowego (wyjątkiem jest C++); * parsery LR mogą być zaimplementowane bardzo wydajnie; * parsery LR wykrywają błędy składniowe (wejście nie zgadza się z gramatyką!) tak szybko jak to możliwe. Parsery LR są trudne do ręcznego zaprogramowania, dlatego są one zwykle konstruowane przez generator parserów. W zależności od tego jak jest generowana tabela parsingu, wyróżnia się następujące parsery LR: parser SLR (Simple LR ), LALR (Look-Ahead LR) i kanoniczny parser LR. Zbiory gramatyk określone przez te rodzaje parserów mają następującą własność: .