LALR

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 (ang.) 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[edytuj | edytuj kod]

Aby otrzymać parser LALR(k) dla gramatyki G należy:

  1. zbudować kanoniczną rodzinę zbiorów sytuacji LR(0) A dla gramatyki G;
  2. zbudować z niej automat charakterystyczny M rozpoznający prefiksy żywotne;
  3. zbudować kanoniczną rodzinę zbiorów sytuacji LR(k) B dla gramatyki G;
  4. każdy stan q w M zastąpić przez sumę wszystkich zbiorów q_1, q_2, \ldots, q_n gdzie q_i należy do rodziny B i zbiór rdzeni sytuacji z q_i jest równy q;
  5. 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[edytuj | edytuj kod]

  • LALR(k) ma tyle stanów co odpowiedni parser LR(0), lub SLR, czyli O\left(2^{|G|+k\log|T|+\log|G|}\right);
  • 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[edytuj | edytuj kod]

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 S\Rightarrow^+S

Właściwości klas gramatyk LALR(k) i LR(k)[edytuj | edytuj kod]

  • LALR(0)=LR(0)
  • LALR(k) jest podzbiorem właściwym LR(k) dla k≥1

Język[edytuj | edytuj kod]

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

Zastosowanie[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory : reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.