Tekst źródłowy strony LALR

'''LALR''' – metoda [[analiza wstępująca|wstępującej]] [[analiza składniowa|analizy składniowej]], działająca na zasadzie [[metoda przesunięcie-redukcja|przesunięcie-redukcja]], jeden z rodzajów analizy typu ''LR'' ([[język angielski|ang.]] ''reads input from Left to right and produces a Rightmost derivation''), czyli „czyta wejście od lewej do prawej i wytwarza prawostronne wyprowadzenie”.

''LALR(k)'' – to klasa [[język formalny|języków formalnych]] oraz klasa [[gramatyka formalna|gramatyk formalnych]].

''Parser LALR(k)'' – to [[analizator składniowy|parser]] działający metodą LALR. [[Algorytm]] parsingu jest taki sam jak w [[parser LR|parserze LR]], ale inaczej budowana jest jego [[tabela parsingu|tablica sterująca]].

Skrót ''LALR(k)'' oznacza {{lang|en}} ''LookAhead (k), reads input from Left to right and produces a Rightmost derivation'', czyli „parser z podglądem ''k'', czytający od lewej do prawej i wytwarzający prawostronne wyprowadzenie”.

Parametr ''k'' oznacza długość podglądanych ciągów. ''LALR'' bez parametru zazwyczaj oznacza ogólnie metody LALR(k), lub LALR(1). Dokładne znaczenie przeważnie wynika z kontekstu.

== Konstrukcja ==
Aby otrzymać parser LALR(k) dla gramatyki ''G'' należy:
# zbudować kanoniczną rodzinę zbiorów sytuacji LR(0) ''A'' dla gramatyki ''G'';
# zbudować z niej automat charakterystyczny ''M'' rozpoznający prefiksy żywotne;
# zbudować kanoniczną rodzinę zbiorów sytuacji LR(k) ''B'' dla gramatyki ''G'';
# każdy stan ''q'' w ''M'' zastąpić przez sumę wszystkich zbiorów <math>q_1, q_2, \dots, q_n</math> gdzie <math>q_i</math> należy do rodziny ''B'' i zbiór rdzeni sytuacji z <math>q_i</math> jest równy ''q'';
# na podstawie tak zmodyfikowanego automatu, zbudować tablicę sterującą, lub zbiór reguł parsera, tak jak się to robi dla LR(''k'').

== Właściwości ==
* LALR(k) ma tyle stanów co odpowiedni parser LR(0), lub SLR, czyli <math>O\left(2^{|G|+k\log|T|+\log|G|}\right);</math>
* LALR(k), który rozpoznaje słowo, działa identycznie jak odpowiedni kanoniczny LR(k);
* LALR(k) może wykrywać błędne wejście nieco później niż parser kanoniczny.

== Gramatyka ==
Gramatyka ''G=(V,T,P,S)'' jest klasy LALR(k), jeśli zbudowany dla niej parser LALR(k) jest deterministyczny i niemożliwe jest wyprowadzenie <math>S\Rightarrow^+S</math>

=== Właściwości klas gramatyk LALR(k) i LR(k) ===
* LALR(0)=LR(0)
* LALR(k) jest [[Podzbiór|podzbiorem]] właściwym LR(k) dla k&ge;1

== Język ==
Język ''L'' jest klasy LALR(k), jeśli istnieje generująca go gramatyka LALR(k).

== Zastosowanie ==
Większość [[Język programowania|języków programowania]] należy do zbioru języków LALR(1). Zaletą tych języków jest to że są niemal równoważne z LR(1) (istnieje stosunkowo mało języków, które są LR(1), a nie są LALR(1)), ale można zbudować dla nich ogólny parser o wiele wydajniejszy (objętościowo) niż dla języków LR.

== Zobacz też ==
* [[generowanie parserów LR]]

== Bibliografia ==
* {{cytuj książkę |nazwisko = Aho |imię = Alfred V. |nazwisko2 = Sethi |imię2 = Ravi |nazwisko3 = Ullman |imię3 = Jeffrey D. |tytuł = Kompilatory. Reguły, metody i narzędzia |wydawca = WNT |miejsce = Warszawa |rok = 2002 |isbn = 83-204-2656-1}}

* {{cytuj książkę |nazwisko = sippu |imię = Seppo |nazwisko2 = Soisalon-Soininen |imię2 = Eljas |tytuł = Parsing Theory |wydawca = Springer-Verlag |miejsce = Berlin i inne |isbn = 3-540-51732-4 |id = {{ISBN|0-387-51732-4}}}}

[[Kategoria:Parsery]]