Narzędzia użytkownika

Narzędzia witryny


interpreter

To jest stara wersja strony!


Wzorzec projektowy interpreter

Wzorzec projektowy interpretera korzysta z reprezentacji gramatyki analizowanego języka formalnego w celu interpretacji wyrażeń w tym języku. Wykorzystywany jest, gdy możliwe jest zapisanie zadań (problemów) w prostym, sformalizowanym języku. Rozwiązanie problemu polega wtedy na odpowiedniej interpretacji wyrażenia tego języka.

Typowe możliwości wykorzystania:

  • interpretacja języków (programowania, matematycznych) w kompilatorach, interpreterach
  • dopasowywanie wzorców, np. opisanych za pomocą wyrażeń regularnych
  • inne, dające się formalnie opisać problemy, np. walidacja/interpretacja wyrażeń (pakietów) protokołów komunikacyjnych

Struktura

AbstractExpression

Klasa abstrakcyjna wyrażeń. Z nich składa się wyrażenie w analizowanym języku.

TerminalExpression

Wyrażenie (symbol) terminalne w danej gramatyce, czyli wyrażenie, które nie składa się z podwyrażeń. Przykładowo, dla gramatyki wyrażeń arytmetycznych liczby są terminalami.

NonterminalExpression

Wyrażenie składające się (dające się podzielić) na podwyrażenia (terminalne lub nie). Na przykład dla gramatyki wyrażeń arytmetycznych takim wyrażeniem jest „3 + 5”.

Context

Aktualny kontekst, który przechowuje stan, w którym znajduje się w danym momencie interpreter, co dla gramatyk kontekstowych pozwala m.in. decydować jak na danym etapie należy interpretować dalsze elementy ciągu wejściowego. Kontekst jest globalnym elementem interpretera. Na przykład analizując kolejne cyfry liczby dziesiętnej kontekst może reprezentować miejsce dziesiętne, np. dziesiątki, setki itd.

Client

Tworzy drzewo wyrażenia, reprezentujące konkretne zdanie wejściowe w języku zdefiniowanym przez gramatykę. Drzewo to jest budowane z konkretnych instancji wyrażeń terminalnych i nieterminalnych. Następnie wywołuje operację interpretacji na korzeniu tego drzewa.

Zagadnienia implementacyjne

Podstawowe kroki implementacji

  • Tworzenie klas wyrażeń - każde wyrażenie terminalne i nieterminalne jest reprezentowane przez inną klasę pochodną od typu Expression (a właściwie od typów NonterminalExpression i TerminalExpression). Na przykład dla języka wyrażeń arytmetycznych powstaną m.in. klasy WyrażenieSuma, WyrażenieRóżnica pochodne od NonterminalExpression i WyrażenieLiczba, pochodne od klasy TerminalExpression. Tworzenie klas dla wszystkich możliwych wyrażeń terminalnych może być kłopotliwe ze względu na ich ilość, np. dla wyrażeń arytmetycznych zamiast tworzenia oddzielnej klasy dla każdej możliwej liczby, można stworzyć jedną klasę Liczba, zawierającą jej wartość.
  • Tworzenie klasy kontekstu - w przypadku wyrażeń arytmetycznych powinien on przechowywać bieżącą (do tej pory obliczoną) wartość wyrażenia i zależności pomiędzy danym wyrażeniem, a jego sąsiadami.
  • Tworzenie drzewa zdania - nie jest zaliczane do zagadnienia wzorca interpretera, zazwyczaj realizowane przez zewnętrzny parser.
  • Definiowanie funkcji interpretującej - zazwyczaj jako metody klasy podstawowej AbstractExpression. Nie zawsze jest konieczne, aby była ona wirtualna (wystarczy, aby korzystała ona z innych metod wirtualnych w danej klasie - patrz przykład poniżej). Jeśli jednak zajdzie taka potrzeba, warto rozpatrzyć możliwość zastosowania wzorca Wizytatora.

Opcjonalne zagadnienia

  • Akcje domyślne - przydatne może być określenie domyślnego wyniku interpretacji w klasie podstawowej wyrażenia dla wyrażeń nie mających konkretnego efektu (np. tylko służących do rozwijania podwyrażeń i oddających dalszą kontrolę tym podwyrażeniom).
  • Wyrażenia współdzielone - możliwe jest wielokrotne użycie instancji danego wyrażenia (np. konkretnej liczby) dla wielu wyrażeń w celu oszczędności pamięci. Na przykład dla wyrażenia „2 + 5 - 2” można dwukrotnie skorzystać z klasy reprezentującej terminal „2”. Należy przy tym pamiętać, aby nie zapamiętywać stanu (kontekstu) w klasie wyrażenia, gdyż zazwyczaj jest on różny na różnych etapach interpretacji.
  • Wielowątkowość - jeśli możliwe jest rozwiązywanie podwyrażeń w oddzielnych wątkach.

Przydatność

Wzorzec interpretera działa najlepiej, gdy:

  • gramatyka jest stosunkowo prosta - dla skomplikowanych gramatyk hierarchia klas staje się duża i trudna w utrzymaniu.
  • efektywność nie jest cechą krytyczną
  • istotna jest możliwość łatwej zmiany i rozszerzania gramatyki - wystarczy dodać nowe klasy do hierarchii lub zmodyfikować istniejące

Przykład

interpreter.1228645156.txt.gz · ostatnio zmienione: 2008/12/07 11:19 przez posciak