Podgląd

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Podgląd w rozmaitych algorytmach polega na wczytywaniu danych wejściowych "na zapas" przed podejmowaniem kosztownej obliczeniowo decycji.

Podgląd jest często stosowany w analizator składniowyach. Polega wówczas na wczytywaniu ustalonej liczby symboli terminalnych przed zadecydowaniem, której reguły parsowania użyć. Dotyczy to zwłaszcza parserów LL, LR i LALR. Często oznacza się go jawnie, dodając do nazwy algorytmu liczbę podglądanych symboli w nawiasach, np. LALR(1). Wiele języków programowania zdefiniowano w ten sposów, aby móc je analizować za pomocą parserów o ograniczonym pogdlądzie, zwykle równym jeden.

Zalety stosowania podglądu przy parsowaniu są następujące:

  • Ułatwia on podejmowanie przez parser właściwego działania w razie konfliktów, takich jak analiza konstrukcji if... else.
  • Eliminuje on wiele nadmiarowych stanów parsera, np. parser dla języka C ma około 10000 stanów bez podglądu i około 300 stanów przy podglądzie jednego symbolu terminalnego.