Jak dokładnie kompilator odzyskuje po błędzie typu?

Przeczytałem kilka artykułów, artykułów i sekcji 4.1.4, rozdział 4 kompilatorów: Zasady, techniki i narzędzia (2. wydanie) (aka „The Dragon Book”), które wszystkie omawiają temat odzyskiwania błędów kompilatora składniowego. Jednak po eksperymentach z kilkoma nowoczesnymi kompilatorami zauważyłem, że odzyskują one również po błędach semantycznych , a także błędach składniowych.

Rozumiem dość dobrze algorytmy i techniki kryjące się za kompilatorami odzyskującymi na podstawie błędów pokrewnych, ale nie do końca rozumiem, w jaki sposób kompilator może odzyskać dane po błędzie semantycznym.

Obecnie używam niewielkiej zmiany wzorca odwiedzającego, aby wygenerować kod z mojego abstrakcyjnego drzewa składni. Rozważ mój kompilator kompilujący następujące wyrażenia:

1 / (2 * (3 + "4"))

Kompilator wygeneruje następujące abstrakcyjne drzewo składniowe:

      op(/)
        |
     -------
    /       \ 
 int(1)    op(*)
             |
          -------
         /       \
       int(2)   op(+)
                  |
               -------
              /       \
           int(3)   str(4)

Faza generowania kodu użyłaby następnie wzorca odwiedzającego, aby rekurencyjnie przechodzić przez abstrakcyjne drzewo składniowe i przeprowadzać sprawdzanie typu. Drzewo abstrakcyjnej składni będzie przechodzić, dopóki kompilator nie znajdzie się w najbardziej wewnętrznej części wyrażenia; (3 + "4"). Kompilator sprawdza następnie każdą stronę wyrażeń i widzi, że nie są one semantycznie równoważne. Kompilator zgłasza błąd typu. Tutaj leży problem. Co powinien teraz zrobić kompilator ?

Aby kompilator mógł zresetować się po tym błędzie i kontynuować sprawdzanie typu zewnętrznych części wyrażeń, musiałby zwrócić pewien typ ( intlub str) z oceny najbardziej wewnętrznej części wyrażenia, do następnej najbardziej wewnętrznej części wyrażenia. Ale po prostu nie ma typu do zwrócenia . Ponieważ wystąpił błąd typu, nie wydedukowano żadnego typu.

Jednym z możliwych rozwiązań, które postulowałem, jest to, że jeśli wystąpi błąd typu, błąd powinien zostać podniesiony, a specjalna wartość, która oznacza, że ​​wystąpił błąd typu, powinna zostać zwrócona do poprzednich wywołań abstrakcyjnego drzewa przejścia składni. Jeśli poprzednie wywołania przechodzenia napotkają tę wartość, wiedzą, że błąd typu wystąpił głębiej w abstrakcyjnym drzewie składni i powinni unikać próby wywnioskowania typu. Chociaż ta metoda wydaje się działać, wydaje się bardzo nieefektywna. Jeśli najbardziej wewnętrzna część wyrażenia znajduje się głęboko w abstrakcyjnym drzewie składni, wówczas kompilator będzie musiał wykonać wiele rekurencyjnych wywołań tylko po to, aby zdać sobie sprawę, że nie można wykonać żadnej prawdziwej pracy, i po prostu powrócić z każdego z nich.

Czy zastosowałem metodę, którą opisałem powyżej (wątpię). Jeśli tak, to czy nie jest wydajne? Jeśli nie, jakie dokładnie metody są stosowane, gdy kompilatory odzyskują po błędach semantycznych?

Twój zaproponowany pomysł jest zasadniczo poprawny.

Kluczem jest to, że typ węzła AST jest obliczany tylko raz, a następnie zapisywany. Ilekroć typ jest ponownie potrzebny, po prostu pobiera zapisany typ. Jeśli rozdzielczość kończy się błędem, zamiast tego zapisywany jest typ błędu.

Jednym z interesujących podejść jest specjalny rodzaj błędów. Gdy taki błąd zostanie napotkany po raz pierwszy, diagnostyka jest rejestrowana, a typ błędu jest zwracany jako typ wyrażenia. Ten typ błędu ma kilka interesujących właściwości:

• Każda operacja, która zostanie na nim wykonana, zakończy się powodzeniem (w celu uniknięcia kaskady komunikatów o błędach spowodowanych przez tę samą pierwotną usterkę)
• Wynik każdej operacji wykonanej na obiekcie z typem błędu ma również typ błędu
• Jeśli typ błędu sięga aż do generowania kodu, generator kodu rozpoznaje użycie i generuje kod, który zawodzi (np. Zgłasza wyjątek, przerywa lub cokolwiek odpowiedniego dla twojego języka)

Dzięki tej kombinacji można faktycznie skompilować kod zawierający błędy typu, a dopóki ten kod nie jest faktycznie używany, nie wystąpi błąd czasu wykonywania. Może to być przydatne, na przykład, aby umożliwić uruchomienie testów jednostkowych dla części kodu, które nie ulegają zmianie.

Jeśli wystąpi błąd semantyczny, użytkownik otrzymuje komunikat o błędzie kompilacji wskazujący na taki błąd.

Po wykonaniu tej czynności można przerwać kompilację, ponieważ program wejściowy jest w błędzie - nie jest to legalny program w języku, więc można go po prostu odrzucić.

To dość trudne, więc istnieją bardziej miękkie alternatywy. Przerwij generowanie kodu i generowanie pliku wyjściowego, ale nadal szukaj czegoś więcej.

Na przykład może po prostu przerwać dalszą analizę typu dla bieżącego drzewa wyrażeń i kontynuować przetwarzanie wyrażeń z kolejnych instrukcji.

Załóżmy, że Twój język pozwala na dodawanie liczb całkowitych i pozwala na łączenie ciągów z +operatorem.

Ponieważ int + stringjest to niedozwolone, ocena +spowoduje zgłoszenie błędu. Kompilator może po prostu zwrócić errorjako typ. Lub może być bardziej sprytny, ponieważ int + int -> inti string + string -> stringsą dozwolone, może zwracać „błąd, może być int lub string”.

Potem przychodzi *operator i zakładamy, że tylko int + intdozwolone. Kompilator może następnie zdecydować, że +rzeczywiście powinien zostać zwrócony int, a typem zwróconym *byłby wówczas int, bez żadnego komunikatu o błędzie.