Dlaczego nie przechowujemy drzewa składni zamiast kodu źródłowego?

Mamy wiele języków programowania. Każdy język jest analizowany i sprawdzany pod względem składni przed przetłumaczeniem na kod, dzięki czemu budowane jest abstrakcyjne drzewo składni (AST).

Mamy to abstrakcyjne drzewo składniowe, dlaczego nie przechowujemy tego drzewa składniowego zamiast kodu źródłowego (lub obok kodu źródłowego)?

Używając AST zamiast kodu źródłowego. Każdy programista w zespole może szeregować to drzewo w dowolnym języku (z odpowiednią gramatyką bez kontekstu) i po zakończeniu parsować z powrotem do AST. To wyeliminowałoby debatę na temat pytań dotyczących stylu kodowania (gdzie umieścić {i}, gdzie umieścić białe znaki, wcięcia itp.)

Jakie są zalety i wady tego podejścia?

Białe znaki i komentarze

Zasadniczo AST nie obejmuje białych znaków, terminatorów linii i komentarzy.

Znaczące formatowanie

Masz rację, że w większości przypadków jest to pozytywne (eliminuje formatowanie świętych wojen), istnieje wiele przypadków, w których formatowanie oryginalnego kodu ma pewne znaczenie, na przykład w wieloliniowych literałach łańcuchowych i „akapitach kodu” (oddzielając bloki instrukcje z pustą linią).

Kod, którego nie można skompilować

Podczas gdy wiele parserów jest bardzo odpornych na brakującą składnię, kod z błędami często skutkuje bardzo dziwnym drzewem składni, które jest w porządku i eleganckie aż do momentu ponownego załadowania pliku przez użytkownika. Czy kiedykolwiek popełniłeś błąd w swoim IDE, a potem nagle cały plik ma „zawijasy”? Wyobraź sobie, jak zostałoby to ponownie załadowane w innym języku.

Może użytkownicy nie popełniają niepoprawnego kodu, ale z pewnością muszą zapisać lokalnie.

Żadne dwa języki nie są idealnie dopasowane

Jak zauważyli inni, prawie nie ma dwóch języków o idealnej parzystości cech. Moim zdaniem najbliższy jest VB i C # lub JavaScript i CoffeeScript, ale nawet wtedy VB ma takie funkcje, jak Literały XML, które nie całkiem mają odpowiedniki w C #, a konwersja JavaScript na CoffeeScript może spowodować wiele literałów JavaScript.

W aplikacji, którą piszę, musimy to zrobić, ponieważ użytkownicy powinni wprowadzić wyrażenia „zwykły angielski”, które są konwertowane na JS w tle. Zastanawialiśmy się tylko nad przechowywaniem wersji JS, ale nie znaleźliśmy prawie żadnego akceptowalnego sposobu, aby niezawodnie załadować i wyładować, dlatego ostatecznie przechowaliśmy zarówno tekst użytkownika, jak i wersję JS, a także flagę wskazującą, czy „zwykły angielski „wersja przeanalizowana idealnie lub nie.

Dlaczego nie przechowujemy tego drzewa składni zamiast kodu źródłowego? Każdy programista w zespole może szeregować to drzewo w dowolnym języku i po zakończeniu parsować z powrotem do AST.

Rzeczywiście, to rozsądny pomysł. Microsoft miał projekt badawczy w latach 90., aby zrobić prawie dokładnie to .

Przychodzi mi na myśl kilka scenariuszy.

Pierwszy jest raczej trywialny; jak mówisz, możesz mieć AST renderowany w różnych widokach, w zależności od preferencji różnych programistów dla takich rzeczy, jak odstępy i tak dalej. Ale przechowywanie AST jest przesadą w tym scenariuszu; po prostu napisz sobie ładną drukarkę. Po załadowaniu pliku do edytora uruchom ładną drukarkę, aby ustawić go w preferowanym formacie i wrócić do oryginalnego formatu po zapisaniu.

Drugi jest bardziej interesujący. Jeśli możesz przechowywać abstrakcyjne drzewo składniowe, to różnicowanie kodu powoduje, że zmiana nie staje się tekstem, ale raczej składnią. Refaktoryzacje, w których przemieszczany jest kod, stają się znacznie łatwiejsze do zrozumienia. Wadą jest oczywiście to, że pisanie algorytmów różnicowania drzewa nie jest trywialne i często musi być wykonywane w zależności od języka. Różnica tekstu działa na prawie każdy język.

Trzeci jest bardziej podobny do tego, co Simonyi przewidział dla celowego programowania: że podstawowe pojęcia wspólne dla języków programowania są serializowane, a następnie masz różne poglądy na te pojęcia renderowane w różnych językach. Choć jest to piękny pomysł, brzydkim faktem jest to, że języki są wystarczająco różne pod względem szczegółów, że podejście o najniższym wspólnym mianowniku tak naprawdę nie działa.

Krótko mówiąc, jest to piękny pomysł, ale jest to ogromna ilość dodatkowej pracy dla stosunkowo niewielkiej korzyści. Dlatego mało kto to robi.

Można argumentować, że właśnie taki jest kod bajtów w .NET. Program odbijający Infact redgate tłumaczy kod bajtowy z powrotem na szereg języków programowania .NET.

Istnieją jednak problemy. Składnia jest specyficzna dla danego języka, ponieważ istnieją elementy, które można reprezentować w jednym języku, a które nie są reprezentowane w innych językach. Dzieje się tak w .NET, a C ++ jest jedynym językiem .NET, który ma dostęp do wszystkich 7 poziomów dostępu.

Poza środowiskiem .NET staje się znacznie trudniejsze. Każdy język zaczyna mieć swój własny zestaw powiązanych bibliotek. Nie byłoby możliwe odzwierciedlenie ogólnej składni zarówno w języku C, jak i Java, która odzwierciedlała to samo wykonanie instrukcji, ponieważ rozwiązują one podobne problemy na bardzo różne sposoby.

W pewnym sensie podoba mi się twój pomysł, ale przeceniasz, jak łatwo jest przetłumaczyć język na język. Gdyby to było takie proste, nie musiałbyś nawet przechowywać AST, ponieważ zawsze możesz parsować język X na AST, a następnie przejść z AST do języka Y.

Chciałbym jednak, żeby specyfikacje kompilatora zastanawiały się nieco więcej nad ujawnieniem części AST za pomocą API. Rzeczy takie jak programowanie aspektowe, refaktoryzacja i statyczna analiza programów mogłyby być implementowane za pomocą takiego interfejsu API, bez konieczności implementacji tych możliwości przez powtórzenie tak dużej ilości pracy już zaimplementowanej przez twórców kompilatorów.

Dziwne jest to, jak często struktura danych programisty do reprezentowania programu składa się z wielu plików zawierających ciągi znaków.

Myślę, że najbardziej istotne są:

• Nie ma korzyści. Powiedziałeś, że oznaczałoby to, że każdy mógłby używać swojego zwierzaka. Ale to nieprawda - użycie reprezentacji drzewa składniowego pozwoliłoby uniknąć tylko różnic składniowych, ale nie różnic semantycznych. Działa do pewnego stopnia w bardzo podobnych językach - takich jak VB i C # lub Java i Scala. Ale nawet nie do końca.

• To problematyczne. Zyskałeś wolność języka, ale straciłeś wolność narzędzi. Nie możesz już czytać i edytować kodu w edytorze tekstów, a nawet w dowolnym środowisku IDE - zależy od konkretnego narzędzia, które mówi reprezentację AST zarówno w zakresie odczytu, jak i edycji kodu. Nic tu nie zyskałem.

  Aby zilustrować ten ostatni punkt, spójrz na RealBasic, który jest zastrzeżoną implementacją potężnego dialektu BASIC. Przez pewien czas wydawało się, że język może wystartować, ale był całkowicie zależny od dostawcy, do tego stopnia, że ​​można było wyświetlać kod tylko w jego IDE, ponieważ został zapisany w zastrzeżonym formacie nietekstowym. Wielki błąd.

Myślę, że jeśli przechowujesz zarówno tekst, jak i AST, to tak naprawdę nie dodałeś niczego przydatnego, ponieważ tekst jest już w jednym języku, a AST można szybko odtworzyć z tekstu.

Z drugiej strony, jeśli przechowujesz tylko AST, tracisz takie rzeczy, jak komentarze, których nie można odzyskać.

Uważam, że pomysł jest interesujący w teorii, ale niezbyt praktyczny, ponieważ różne języki programowania obsługują różne konstrukcje, z których niektóre nie mają odpowiedników w innych językach.

Na przykład X ++ ma instrukcję „while select”, której nie można napisać w języku C # bez dużej ilości dodatkowego kodu (dodatkowe klasy, dodatkowa logika itp.). http://msdn.microsoft.com/en-us/library/aa558063.aspx

Mówię tu o tym, że wiele języków ma cukry składniowe, które tłumaczą duże bloki kodu tego samego języka lub nawet elementy, które w ogóle nie istnieją. Oto przykład, dlaczego podejście AST nie zadziała:

Język X ma słowo kluczowe K przetłumaczone w AST w 4 instrukcjach: S1, S2, S3 i S4. AST jest teraz tłumaczony na język Y, a programista zmienia S2. Co dzieje się z tłumaczeniem z powrotem na X? Kod jest tłumaczony jako 4 instrukcje zamiast jednego słowa kluczowego ...

Ostatnim argumentem przeciwko podejściu AST są funkcje platformy: co dzieje się, gdy funkcja jest wbudowana w platformę? Podobnie jak .NET's Environment.GetEnvironmentVariable. Jak to tłumaczysz?

Pomysł ten oparty jest na systemie: JetBrains MPS . Edytor jest trochę dziwny lub po prostu inny, ale ogólnie nie jest to taki duży problem. Największym problemem jest to, dobrze, że to nie jest tekst dłużej, więc nie można użyć dowolnego z normalnych narzędzi tekstowych - innych edytorów, grep, sed, scalanie i diff narzędzia, itd.

W rzeczywistości istnieje kilka produktów, ogólnie znanych jako „językowe stoły robocze”, które przechowują AST i przedstawiają w swoich edytorach „rzut” AST z powrotem na określony język. Jak powiedział @ sk-logic, MPS JetBrains jest jednym z takich systemów. Kolejnym jest Intentional Software's Intentional Workbench.

Potencjał dla warsztatów językowych wydaje się bardzo wysoki, szczególnie w obszarze języków specyficznych dla domeny, ponieważ można stworzyć projekcję specyficzną dla domeny. Na przykład, zamierzone dema DSL związane z elektrycznością, która wyświetla się jako schemat obwodu - o wiele łatwiej i dokładniej dla eksperta w dziedzinie do dyskusji i krytykowania niż obwód opisany w tekstowym języku programowania.

W praktyce stoły robocze są powolne, ponieważ programiści wolą pracować w znanym, ogólnym języku programowania. W porównaniu bezpośrednio z edytorem tekstu lub programowym IDE, językowe stoły robocze mają mnóstwo kosztów ogólnych, a ich zalety nie są tak jasne. Żaden z językowych środowisk roboczych, które widziałem, nie przywiązał się do tego stopnia, że ​​mogą z łatwością rozszerzyć własne środowiska IDE - to znaczy, jeśli językowe środowiska robocze są świetne pod względem produktywności, dlaczego narzędzia językowe nie są lepsze - i lepiej przy coraz szybszych stawkach?

Czytasz mi w myślach.

Kiedy kilka lat temu wziąłem kurs kompilatora, odkryłem, że jeśli weźmiesz AST i serializujesz go, z notacją prefiksu zamiast zwykłej notacji infiksu i użyjesz nawiasów do rozdzielenia całych instrukcji, otrzymasz Lisp. Podczas gdy uczyłem się o Scheme (dialekcie Lisp) podczas moich studiów licencjackich, nigdy tak naprawdę nie doceniłem tego. Zdecydowanie zyskałem uznanie dla Lispa i jego dialektów w wyniku tego kursu.

Problemy z tym, co proponujesz:

1. komponowanie AST w środowisku graficznym jest trudne / wolne. W końcu większość z nas może pisać szybciej niż my możemy poruszać myszą. A jednak powstaje pytanie: „jak piszesz kod programu za pomocą tabletu?” Pisanie na tablecie jest powolne / kłopotliwe w porównaniu do klawiatury / laptopa z klawiaturą sprzętową. Jeśli możesz utworzyć AST, przeciągając i upuszczając komponenty z palety na płótno na dużym urządzeniu z ekranem dotykowym, programowanie na tablecie może stać się rzeczywistością.

2. niewiele / żadne z naszych istniejących narzędzi nie obsługuje tego. Mamy dekady rozwoju poświęconego tworzeniu coraz bardziej złożonych IDE i coraz bardziej inteligentnych edytorów. Mamy wszystkie te narzędzia do formatowania tekstu, porównywania tekstu, wyszukiwania tekstu. Gdzie są narzędzia, które mogą wykonywać wyszukiwanie wyrażeń regularnych w drzewie? A może różnica dwóch drzew? Wszystkie te rzeczy można łatwo zrobić z tekstem. Ale mogą tylko porównać słowa. Zmień nazwę zmiennej, tak aby słowa były różne, ale znaczenie semantyczne było takie samo, a te narzędzia porównywania napotkały problemy. Takie narzędzia, opracowane do działania na AST zamiast tekstu, pozwolą zbliżyć się do porównania znaczenia semantycznego. To byłaby dobra rzecz.

3. podczas gdy przekształcanie kodu źródłowego programu w AST jest stosunkowo dobrze zrozumiane (mamy kompilatory i interpretatory, prawda?), przekształcanie AST w kod programu nie jest tak dobrze zrozumiane. Mnożenie dwóch liczb pierwszych w celu uzyskania dużej liczby zespolonej jest względnie proste, ale uwzględnienie dużej liczby złożonej z powrotem w liczbach pierwszych jest znacznie trudniejsze; to jest miejsce, w którym parsujemy vs dekompilujemy AST. Właśnie tutaj różnice stają się problemem. Nawet w określonym języku istnieje wiele sposobów dekompilacji AST. Iterowanie przez kolekcję obiektów i uzyskiwanie jakiegoś wyniku, na przykład. Użyć pętli for, iterując po tablicy? Byłoby to kompaktowe i szybkie, ale istnieją ograniczenia. Użyj jakiegoś iteratora, działasz na kolekcji? Kolekcja ta może mieć różne rozmiary, co zapewnia elastyczność przy (możliwym) koszcie prędkości. Mapa / Zmniejszenie? Bardziej złożone, ale domyślnie możliwe do zrównoleglenia. I to tylko dla Java, w zależności od twoich preferencji.

Z czasem wysiłek rozwojowy zostanie poświęcony, a my będziemy rozwijać się za pomocą ekranów dotykowych i AST. Pisanie stanie się mniej konieczne. Widzę to jako logiczny postęp z miejsca, w którym jesteśmy, patrząc na dzisiaj, jak korzystamy z komputerów, to rozwiąże # 1.

Już pracujemy z drzewami. Lisp to tylko serializowane AST. XML (i HTML, według rozszerzenia) to tylko zserializowane drzewo. Aby przeprowadzić wyszukiwanie, mamy już kilka prototypów: XPath i CSS (odpowiednio dla XML i HTML). Kiedy tworzone są narzędzia graficzne, które pozwalają nam tworzyć selektory i modyfikatory w stylu CSS, rozwiążemy część # 2. Kiedy te selektory mogą zostać rozszerzone o obsługę wyrażeń regularnych, będziemy bliżej. Wciąż szukam dobrego graficznego narzędzia do porównywania dwóch dokumentów XML lub HTML. Gdy ludzie będą rozwijać te narzędzia, # 2 będzie można rozwiązać. Ludzie już pracują nad takimi rzeczami; po prostu ich jeszcze nie ma.

Jedynym sposobem, w jaki widzę możliwość dekompilacji tych AST do tekstu w języku programowania, byłoby dążenie do celu. Jeśli modyfikuję istniejący kod, cel może zostać osiągnięty przez algorytm, który sprawia, że ​​mój zmodyfikowany kod jest jak najbardziej zbliżony do kodu początkowego (minimalne różnice tekstowe). Jeśli piszę kod od zera, celem może być najmniejszy, najściślejszy kod (prawdopodobnie pętla for). Lub może to być kod, który działa równolegle tak skutecznie, jak to możliwe (prawdopodobnie mapa / redukcja lub coś z udziałem CSP). Tak więc ten sam AST może skutkować znacznie innym kodem, nawet w tym samym języku, w zależności od tego, jak ustalono cele. Opracowanie takiego systemu rozwiązałoby # 3. Byłoby to skomplikowane obliczeniowo, co oznacza, że ​​prawdopodobnie potrzebowalibyśmy pewnego rodzaju konfiguracji klient-serwer,

Jeśli Twoim celem jest wyeliminowanie debaty na temat formatowania stylów, być może potrzebujesz edytora, który odczytuje plik źródłowy, formatuje go zgodnie z twoimi osobistymi preferencjami dotyczącymi wyświetlania i edycji, ale podczas zapisywania zmienia format na wybrany styl zespołu wykorzystuje.

Jest to dość łatwe, jeśli używasz edytora takiego jak Emacs . Zmiana stylu formatowania całego pliku to zadanie składające się z trzech poleceń.

Powinieneś także być w stanie zbudować haki, aby automatycznie ładować plik do własnego stylu podczas ładowania i przekształcać go do stylu zespołu podczas zapisywania.

Trudno jest odczytać i zmodyfikować AST zamiast kodu źródłowego.

Jednak niektóre narzędzia związane z kompilatorem pozwalają na korzystanie z AST. Kod bajtowy Java i kod pośredni .NET działają podobnie do AST.

to fajny pomysł; ale AST w każdym języku jest inny niż w każdym innym.

Jedyny wyjątek, jaki znam, dotyczy VB.NET i C #, gdzie Microsoft twierdzi, że jest to „ten sam język z inną składnią”. Nawet inne języki .NET (IronPython, F #, cokolwiek) różnią się na poziomie AST.

To samo dotyczy języków JVM, wszystkie są kierowane na ten sam kod bajtowy, ale konstrukcje językowe są różne, co czyni je różnymi językami i różnymi AST.

Nawet języki „cienkowarstwowe”, takie jak CoffeScript i Xtend, dzielą wiele teorii leżących u podstaw języków (odpowiednio JavaScript i Java); ale wprowadzić koncepcje wyższego poziomu, które są (lub powinny być) zachowane na poziomie AST.

jeśli Xtend można by zrekonstruować z Java AST, myślę, że zostałby zdefiniowany jako „kompilator Java-to-Xtend”, który magicznie tworzy abstrakcje wyższego poziomu z istniejącego kodu Java, nie sądzisz?