Projekt kompilatora - analizator oddolny

Analiza oddolna rozpoczyna się od węzłów liści drzewa i działa w górę, aż dotrze do węzła głównego. Tutaj zaczynamy od zdania, a następnie stosujemy reguły produkcji w odwrotny sposób, aby dotrzeć do symbolu początku. Poniższy obraz przedstawia dostępne parsery oddolne.

Parsowanie Shift-Reduce

Analiza metodą Shift-Redukcja wykorzystuje dwa unikalne kroki do analizy oddolnej. Te kroki są znane jako krok przesunięcia i krok redukcji.

Shift step: Krok przesunięcia odnosi się do przesunięcia wskaźnika wejściowego do następnego symbolu wejściowego, który jest nazywany przesuniętym symbolem. Ten symbol jest kładziony na stosie. Przesunięty symbol jest traktowany jako pojedynczy węzeł drzewa parsowania.
Reduce step: Kiedy parser znajduje pełną regułę gramatyczną (RHS) i zastępuje ją (LHS), jest to znane jako krok redukcji. Dzieje się tak, gdy wierzchołek stosu zawiera uchwyt. Aby zmniejszyć, na stosie wykonywana jest funkcja POP, która wyskakuje z uchwytu i zastępuje go symbolem nieterminalowym LHS.

LR Parser

Parser LR jest parserem nierekurencyjnym, redukującym przesunięcie i oddolnym. Wykorzystuje szeroką klasę gramatyki bezkontekstowej, co czyni ją najbardziej wydajną techniką analizy składni. Parsery LR są również znane jako parsery LR (k), gdzie L oznacza skanowanie strumienia wejściowego od lewej do prawej; R oznacza konstrukcję wyprowadzenia położonego najbardziej na prawo w odwrotnej kolejności, a k oznacza liczbę symboli antycypowania do podejmowania decyzji.

Istnieją trzy powszechnie używane algorytmy do konstruowania parsera LR:

SLR (1) - Prosty parser LR:
- Działa na najmniejszej klasie gramatyki
- Niewielka liczba stanów, stąd bardzo mała tabela
- Prosta i szybka konstrukcja
LR (1) - Parser LR:
- Działa na pełnym zestawie gramatyki LR (1)
- Generuje dużą tabelę i dużą liczbę stanów
- Powolna konstrukcja
LALR (1) - Look-Ahead LR Parser:
- Działa na gramatyce o średniej wielkości
- Liczba stanów jest taka sama jak w lustrzance (1)

Algorytm analizy LR

Tutaj opisujemy szkieletowy algorytm parsera LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL kontra LR

LL	LR
Wykonuje wyprowadzenie skrajnie lewe.	Wykonuje prawe wyprowadzenie w odwrotnej kolejności.
Rozpoczyna się nieterminalem głównym na stosie.	Kończy się nieterminalem głównym na stosie.
Kończy się, gdy stos jest pusty.	Zaczyna się od pustego stosu.
Używa stosu do określenia tego, czego nadal można się spodziewać.	Używa stosu do oznaczania tego, co jest już widoczne.
Buduje drzewo analizy od góry do dołu.	Buduje drzewo parsowania od dołu do góry.
Ciągle zdejmuje nieterminal ze stosu i odkłada odpowiednią prawą stronę.	Próbuje rozpoznać prawą stronę stosu, wyskakuje i odkłada odpowiedni nieterminal.
Rozwija nieterminale.	Zmniejsza liczbę nie-terminali.
Odczytuje terminale, gdy zdejmuje jeden ze stosu.	Odczytuje terminale, wpychając je na stos.
Zamów przeglądanie drzewa parsowania w przedsprzedaży.	Przeglądanie drzewa parsowania po zamówieniu.