LALR – metoda wstępującej analizy składniowej, działająca na zasadzie przesunięcie-redukcja, jeden z rodzajów analizy typu LR (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ów formalnych oraz klasa gramatyk formalnych.
Parser LALR(k) – to parser działający metodą LALR. Algorytm parsingu jest taki sam jak w parserze LR, ale inaczej budowana jest jego tablica sterująca.
Skrót LALR(k) oznacza 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 gdzie należy do rodziny B i zbiór rdzeni sytuacji z 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 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
Właściwości klas gramatyk LALR(k) i LR(k) LALR(0)=LR(0) LALR(k) jest podzbiorem właściwym LR(k) dla k≥1
Język Język L jest klasy LALR(k), jeśli istnieje generująca go gramatyka LALR(k).
Zastosowanie Większość 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
Kategoria:Parsery