Metoda ograniczonego kontekstu

Metoda ograniczonego kontekstu (ang. bounded-context parsing) lub BC(m,n) – analiza wstępująca działająca na zasadzie przesunięcie-redukcja (ang. shift-reduce), w której decyzja o akcji do wykonania podejmowana jest na podstawie m symboli z wierzchołka stosu i n kolejnych symboli z wejścia. Dawniej metoda ta (szczególnie BC(2,1)) była dosyć popularna, jednak została wyparta przez LALR(1).

Działanie

Parser BC(m,n) czyta strumień symboli terminalnych z wejścia, posiada stos, na którym może przechowywać zarówno symbole terminalne, jak i nieterminalne. W dwuwymiarowej tabeli parsingu indeksowanej słowami o długości m złożonych z symboli terminalnych i nieterminalnych oraz słowami o długości n z symboli terminalnych, zapisane są akcje, które analizator składniowy w danej konfiguracji ma wykonać. Parser wykonuje cztery rodzaje akcji:

  • Przesunięcie (ang. shift) – jeden terminal z wejścia jest przekładany na stos.
  • Redukcja według reguły A → X 1 X 2 … X n {\displaystyle A\rightarrow X_{1}X_{2}\ldots X_{n}} – n symboli z wierzchołka stosu (są to symbole X 1 X 2 … X n {\displaystyle X_{1}X_{2}\ldots X_{n}} ) jest zastępowanych przez A.
  • Akceptacja – wejście jest poprawnym słowem, koniec pracy.
  • Błąd – zgłaszany jest błąd.

Każdy kontekst musi jednoznacznie określać akcje, czyli każda komórka tabeli parsowania może zawierać najwyżej jedną akcję. Niektóre komórki mogą pozostać puste, gdyż niektóre konteksty mogą być nieosiągalne.

Parsery LR(k) mogą być traktowane jak efektywna implementacja BC(°,k), czyli parsera biorącego pod uwagę sytuacje na całym stosie i k pozostałych symboli z wejścia.

Bibliografia

  • Dick Grune, Ceriel Jacobs: Parsing Techiniques – A Practical Guide. Chichester, England: Ellis Horwood, 1990. ISBN 0-13-651431-6.