Generator parserów

Generator parserów – program generujący analizator składniowy (parser) języka formalnego na podstawie jego opisu, najczęściej w postaci gramatyki. W modelu wzorcowym, generator otrzymuje opis języka w postaci gramatyki, generuje kod źródłowy, który po skompilowaniu daje parser, który z kolei otrzymuje na wejściu symbole leksykalne z leksera i produkuje drzewo wyprowadzenia lub rozpoznaje błędy składniowe.

Generator może pozwalać na dodatkowe informacje w opisie języka np.

  • łączność i pierwszeństwo operatorów – co pozwala używać prostszych i naturalniejszych gramatyk.
  • akcje semantyczne, czyli akcje jakie ma podejmować parser po rozpoznaniu pewnego fragmentu wejścia. Pozwala to generować kompilatory, translatory i interpretery, co przekształca generator parserów w generator kompilatorów (ang. compiler-compiler, compiler generator).

Rodzaje

Istnieją różne rodzaje parserów. Dany generator potrafi generować tylko niektóre typy parserów, zazwyczaj jeden, lub kilka podobnych. Popularniejsze typy generowanych parserów to np.: LALR, LR, GLR, LL. W zależności od typu parsera, akceptowane są odpowiednie klasy gramatyk.

Generatory można również podzielić ze względu na język programowania w którym jest generowany kod parsera. Niektóre generatory potrafią produkować kod w kilku (zazwyczaj podobnych) językach. Istnieją generatory, które tworzą kod będący jednocześnie analizatorem składniowym i leksykalnym.

Generatory parserów

Zobacz też