ELI - system budowy translatorów

Daniel Rychcik
muflon@mat.uni.torun.pl
26-11-2001

1. Ideologia

ELI jest zestawem narzędzi służących do uproszczonej budowy programów przetwarzających tekst na podstawie specyfikacji problemu przy jak najmniejszym nakładzie sił poświęconych na kwestie implementacyjna. Łączy on funkcjonalność programów takich jak lex i yacc, dodając jednak mechanizmy pozwalające w wygodny sposób pisać mechanizmy implementujące właściwe działanie np. kompilatora, które to fragmenty w yacc musiały być pisane w większości ręcznie

ELI nie jest narzędziem ograniczonym tylko do generowania translatorów - może być stosowany w dowolnej sytuacji wymagającej przetwarzania tekstu, w której zasady owego przetwarzania się często zmieniają, a jednocześnie wymagana jest wysoka wydajność

2. Wiadomości podstawowe

2.1. Fazy przetwarzania tekstu

W dowolnym programie typu ELI proces przetwarzania tekstu można podzielić na kilka faz. Zawsze występują co najmniej trzy z nich:

W typowym modelu konstrukcji translatorów za pierwszą z tych faz odpowiada analizator generowany przez lex, za drugą - parser generowany przez yacc, natomiast trzecia faza odpowiada fragmentom kodu w C, o które programista musi rozbudować specyfikację gramatyki opisaną przez plik wejściowy yacc.

Co gorsza, te trzy etapy są w takiej sytuacji zupełnie oddzielone - nie ma możliwości wykorzystania informacji dostępnej w trakcie rozpoznawania słów do analizy gramatycznej. ELI rozwiązuje ten problem wykonując wszystkie fazy w ramach jednego programu. Co więcej fazę analizy gramatycznej rozpatruje się z regułu przed analizą leksykalną!

W rzeczywistości ELI traktuje proces przetwarzania tekstu jako bardziej złożony proces, dzieląc go na więcej części, z których nie wszystkie są obowiązkowe. Jako przykład można podać tzw. overload resolution - wybór właściwej wersji operatora przeciążonego. W ogólnym przypadku ten etap nie występuje, jest on specyficzny dla programów przetwarzających języki programowania (i to dość konkretne)

2.2. Podstawowe konstrukcje ELI

2.2.1. Analiza gramatyczna

Przykład:

  Position: Latitude Longtitude .
  Latitude: NS Coordinate .
  Longitude: EW Coordinate .
  NS: 'N' / 'S' .
  EW: 'E' / 'W' .
  Coordinate: Integer Float .

Podana gramatyka ma 8 symboli: Position, Latitude, Longitude, NS, EW, Coordinate, Integer, Float, cztery literały: 'N', 'S', 'E', 'W' i osiem reguł (x: y / z . to skrót dla dwóch reguł postaci x: y . i x: z .).

Symbole, które nie są zdefiniowane przez gramatykę nazywamy końcowymi (terminal symbols), natomiast symbole zdefiniowane przez reguły to symbole pośrednie (nonterminal symbols).

Symbole które są "najwyższego poziomu" (nie ma do nich odwołań w innych definicjach) nazywamy axiomami (axiom).

2.2.2. Analiza leksykalna

Pod tym pojęciem w ELI rozumiany jest proces przetwarzania tekstu i usunięcia z niego wszystkich nieznaczących (non-significant) symboli pozostawiając pozostałe fragmenty w niezmienionej postaci. Symbol definiujemy jako znaczący jeżeli jest w odpowiedniej gramatyce symbolem końcowym albo literałem.

W tym miejscu widać przewagę ELI nad kombinacją lex+yacc. Informacja leksykalna o literałach jest bowiem uzyskiwana bezpośrednio z gramatyki! Użytkownik musi podać wzorce tylko dla symboli końcowych. Ich postać jest typowa i opiera się o wyrażenia regularne. Oto przykład:

  Integer:  $[0-9]+
  Float:    $[0-9]+"."[0-9]+

(Są to mocno uproszczone definicje liczb na potrzeby powyższej gramatyki)

2.2.3. Semantyka

Opis gramatyki w połączeniu z opisem symboli końcowych pozwala nam na zbudowanie drzewa odpowiadającego dowolnemu pojęciu zgodnego z gramatyką (typowo wykonujemy to dla axiomów - odpowiadają one programom w danym języku, lub specyfikacji problemu w innej formie). Jednak samo takie drzewo nic nam nie daje - z reguły chcemy dodać w tym momencie jakieś akcje które mają zostać wykonane, jeżeli program wynikowy w trakcie analizy dojdzie do danego miejsca w drzewie. Oto przykład takiej definicji w składni ELI:

  SYMBOL set_body COMPUTE
    SYNT.Size=CONSTITUENTS set_element.Sym WITH (int, ADD, ARGTOONE, ZERO);
  END;

Opisuje ona akcję, jaka ma zostać wykonana, jeżeli w trakcie analizy napotkany zostanie węzeł typu set_body - konstrukcja ta będzie dokładniej wyjaśniona później.

2.2.4. Generowanie tekstu wynikowego

Ostatnią fazą przetwarzania jest zamiana drzewa i dodatkowych informacji zebranych w poprzednim etapie na plik wyjściowy o żądanej składni. W ELI wykorzystywany jest mechanizm wzorców (templates), którego działanie polega na tym, że tworzymy szablony w których wszystkie elementy zmienne zastępujemy specjalnymi symbolami. Oto przykład:

  StringList:
    "char **array_named_"$1"[] = {\n"
    $2/* Ciąg łańcuchów znaków oddzielonych przecinkami*/ "};\n\n"

Zdefiniowano wzorzec elementu StringList, który jest parametryzowany przez: nazwę tablicy ($1) oraz jej zawartość ($2). ELI dostarcza mechanizmy, które pozwalają "wypełnić" taki wzorzec obiektami uzyskanymi np. przy przetwarzaniu drzewa.

2.3. Znaczenie rozszerzeń plików

Jak widać ELI operuje na kilku formatach plików - przyjęto ich rozróżnianie na podstawie rozszerzenia nazwy. Oto kilka ważniejszych przykładów:

2.4. Podstawowe komendy

Po uruchomieniu systemu ELI otrzymujemy prompt postaci ->. Aby rozpocząć pracę należy zatem znać co najmniej dwie podstawowekomendy:

3. Przykład działania

3.1. Problem

Zdefiniowany jest następujący problem: przetworzyć ciąg list następującej postaci:

  colors{red blue green}
  bugs{ant spider fly moth bee}
  verbs{crawl walk run fly}
na odpowiadający jej program w języku C o postaci:
  int number_of_sets=3;

  char *name_of_set[] = {
   "colors",
   "bugs",
   "verbs"};

  int size_of_set[] = {
   3,
   5,
   4};

  char *set_of_colors[] = {
   "red",
   "blue",
   "green"};

  char *set_of_bugs[] = {
   "ant",
   "spider",
   "fly",
   "moth",
   "bee"};

  char *set_of_verbs[] = {
   "crawl",
   "walk",
   "run",
   "fly"};

  char **values_of_set[] = {
   set_of_colors,
   set_of_bugs,
   set_of_verbs};
dbając o to, żeby w żadnym z sets nie powtórzyła się dwukrotnie ta sama wartość.

Cztery niżej opisane pliki są ujęte we wspólnym pliku sets.spec, który zawiera ich nazwy oraz biblioteki, które mają zostać włączone w procesie kompilacji.

3.2. Opis gramatyki wejściowej (sets.con)

Jak już wcześniej wspomniano, podaje się tutaj zależności logiczne, konstrukcję gramatyki, a nie np. konstrukcję słowa, chociaż elastyczność języka pozwala również i na to. Oto zawartość pliku:

  text: set_defs .
  set_defs: set_def / set_defs set_def .
  set_def: set_name '{' set_body '}' .
  set_name: word .
  set_body: elements .
  elements: set_element / elements set_element .
  set_element: word .

Zasada konstrukcji reguł jest taka sama jak w poprzednim przykładzie (p.2.2.1.)

3.3. Opis symboli wejściowych (word.gla)

Oprócz zdefiniowania "słowa", które jest jedynym symbolem terminalnym gramatyki, wstawiamy dodatkowo dyrektywę wbudowaną, która powoduje, że ignorowane są komentarze w stylu języka C:

  word:   $[a-zA-Z]+      [mkidn]
          C_COMMENT

3.4. Jednoznaczność elementów list (symbol.lido)

Na tym etapie mamy już formalnie zdefiniowaną gramatykę. Możemy jednak dodawać nowe akcje do wykonania dla dowolnego elementu języka (czyli tak naprawdę dla dowolnego węzła drzewa).

Jak pamiętamy, na język narzucone jest wymaganie, aby elementy na listach nie powtarzały się. W Eli zawarty jest gotowy moduł potrafiący sprawdzać tego typu warunki. Aby go włączyć musimy do pliku .spec dołączyć następujące linie

  $/Name/AlgScope.gnrc :inst
  $/Prop/Unique.gnrc :inst

(Pierwszy z tych modułów jest potrzebny po to, aby określić zakres w jakim sprawdzamy jednoznaczność). 

  ATTR Sym: int;

  SYMBOL Entity INHERITS IdDefScope, Unique COMPUTE
    SYNT.Sym=TERM;
    IF(NOT(THIS.Unique),
      message(ERROR,"Multiply-defined word", 0, COORDREF));
  END;

  SYMBOL text INHERITS RootScope, RangeUnique END;
  SYMBOL set_body INHERITS RangeScope END;
  SYMBOL set_name INHERITS Entity END;
  SYMBOL set_element INHERITS Entity END;

3.5. Generowanie testu wynikowego (code.fw)

Przy ostatnim etapie przetwarzania obowiązuje (opisany w p.2.2.4.) rozdział "wyglądu" kodu wynikowego od jego "zawartości". Aby używać opisanych tam narzędzi należy w pliku .specs załadować moduł LeafPtg:

  $/Output/LeafPtg.gnrs :inst

Obydwie te części są jednak zawarte w tym samym pliku. Może on również zawierać informacje dodatkowe, takie jak np. tekstowy opis specyfikacji - patrz p.7.). 

  @O@<code.ptg@>@{
  ...
  @}

  @O@<code.lido@>@{
  ...
  @}

3.5.1. Definicja formatu (code.ptg)

  Table:
    "int number_of_sets = " $/*integer*/ ";\n\n"
    "char *name_of_set[] = {\n"
    $/*list of set names*/ "};\n\n"
    "int size_of_set[] = {\n"
    $/*list of set sizes*/ "};\n\n"
    $/*list of sets*/
    "char **values_of_set[] = {\n"
    $/*list of set representations*/ "};\n"

  Set:
    "char *set_of_" $/*set name*/ "[] = {\n"
    $/*list of set elements*/ "};\n\n"

  List:
    $ ",\n" $

  Quoted:
    "\"" $ "\""

  Name:
    "set_of_" $

Plik ten określa format tłumaczenia poszczególnych elementów języka źródłowego na język docelowy. Jak widać, nie podano tutaj numerów parametrów wzorców (np. $1). Wynika to ze szczególnej własności Eli: jeżeli parametry są używane jednokrotnie we wzorcu, to otrzymują automatycznie numery od 1 wzwyż.

3.5.2. Definicja sposobu wypełniania wzorca (code.lido)

Tak jak plik .ptg określa wygląd tekstu wynikowego, plik .lido określa, co i na jakich zasadach wstawiane jest w miejsce parametrów w szablonach: 

  ATTR Ptg: PTGNode;
  SYMBOL Entity INHERITS IdPtg END;

  SYMBOL text COMPUTE
    IF(NoErrors,
      PTGOut(
        PTGTable(
          PTGNumb(CONSTITUENTS set_name.Sym WITH (int, ADD, ARGTOONE, ZERO)),
          CONSTITUENTS set_name.Ptg WITH (PTGNode, PTGList, PTGQuoted, PTGNULL),
          CONSTITUENTS set_body.Size WITH (PTGNode, PTGList, PTGNumb, PTGNULL),
          CONSTITUENTS set_def.Ptg WITH (PTGNode, PTGSeq, IDENTICAL, PTGNULL),
          CONSTITUENTS set_name.Ptg WITH (PTGNode, PTGList, PTGName, PTGNULL))));
  END;

  ATTR Size: int;
  SYMBOL set_body COMPUTE
    SYNT.Size=CONSTITUENTS set_element.Sym WITH (int, ADD, ARGTOONE, ZERO);
  END;

  SYMBOL set_def COMPUTE
    SYNT.Ptg=
      PTGSet(
        CONSTITUENT set_name.Ptg,
        CONSTITUENTS set_element.Ptg WITH (PTGNode, PTGList, PTGQuoted, PTGNULL));
  END;

4. Linia komend

5. Odinfile

Pliki o tej nazwie odpowiadają w Eli standardowym plikom Makefile. Określają one jeden lub więcej obiektów docelowych oraz zasady i źródła, z których system ma te obiekty zbudować. Oto przykłady takich zasad:

6. Ważniejsze pakiety

6.1. Adt - abstrakcyjne typy danych

Zaoszczędzają klepania typowych kawałków kodu

6.2. Output - funkcje pomocnicze dla plików wyjściowych

6.3. Prop - przypisanie/sprawdzanie własności obiektów

6.4. Clp - przetwarzanie linii poleceń

Jest to dość specyficzny moduł. Na podstawie specyfikacji składni wywołania programu generuje on funkcje przetwarzające linię poleceń i wypełniające stosowne zmienne. Oto przykład takiej specyfikacji:

  CompileOnly "-c" boolean "Compile only, do not link";
  MacroPackage "-m" joinedto strings "Load this macro package";
  FileName input "File to be processed";
  Others positionals "Rest of the parameters";

Z grubsza widać, co się dzieje:

A oto jak używać wygenerowanych opcji we własnym kodzie:

  if (FileName!=NoKey) {
    printf ("Compilling file %s\n",StringTable(GetClpValue(FileName,0)));
    Compile(StringTable(GetClpValue(FileName,0)));
    if (!CompileOnly) {
      CreateExecutable();
    }
  }

Dokładniejsze informacje i wyjaśnienie innych opcji można znaleźć w dokumentacji pakietu clp.

7. Integracja specyfikacji z dokumentacją

Bardzo oryginalnym pomysłem autorów Eli jest zintegrowanie w jeden plik (z rozszerzeniem .fw) formalnego opisu problemu w odpowiednich formatach z jego dokumentacją. Ideologia jest tu podobna jak np. w wypadku javadoc, tyle, że trochę odwrotnie - tutaj domyślnie mamy tekst dokumentacji (np. TeX), natomiast pliki źródłowe są w pliku specjalnie oznaczane. Efekt jest mniej więcej taki:

  @p typesetter = tex
  @p maximum_input_line_length = infinity
   ...
  \begin{document}
  \pagestyle{empty}
   ...
  \title{Tytuł dokumentu}
   ...
  @A@<Introduction@>
   ...
  @O@<sets.ptg@>@{
   (tu jest kod pliku źródłowego)
  @}
   ...
  i dalej dokumentacja

8. Przykłady z dystrybucji

Oprócz prostych programów wyjaśniających zasadę działania generatora, w pakiecie Eli dostępne są również bardziej zaawansowane aplikacje napisane z jego użyciem:

9. Literatura, źródła

9.1. Dokumenty

9.2. Oprogramowanie

Pakiet Eli wraz z dokumentacją i przykładami działania jest dostępny pod następującymi adresami: