Drzewo składni betonu odpowiada co gramatyka zasady powiedzieć to składnia. Celem abstrakcyjnego drzewa składni jest „prosta” reprezentacja tego, co jest istotne w „drzewie składni”.
Prawdziwą wartością w AST IMHO jest to, że jest mniejszy niż CST, a zatem jego przetwarzanie zajmuje mniej czasu. (Można powiedzieć, kogo to obchodzi? Ale pracuję z narzędziem, w którym mamy dziesiątki milionów węzłów na raz!).
Większość generatorów parserów, które mają jakiekolwiek wsparcie dla budowania drzew składni nalega, abyś osobiście określił sposób ich budowania przy założeniu, że twoje węzły drzewa będą "prostsze" niż CST (iw tym ogólnie mają rację, ponieważ programiści są ładni leniwy). Prawdopodobnie oznacza to, że musisz kodować mniej funkcji odwiedzających drzewo, a jest to również cenne, ponieważ minimalizuje energię inżynierską. Jeśli masz 3500 reguł (np. W języku COBOL), ma to znaczenie. I ta „prostsza” prostota prowadzi do dobrej właściwości „małości”.
Ale posiadanie takich AST stwarza problem, którego nie było: nie pasuje do gramatyki, a teraz musisz mentalnie śledzić oba z nich. A kiedy istnieje 1500 węzłów AST dla gramatyki 3500 reguł, ma to duże znaczenie. A jeśli gramatyka ewoluuje (zawsze tak jest!), Teraz masz dwa gigantyczne zestawy rzeczy do synchronizacji.
Innym rozwiązaniem jest pozwolić parserowi po prostu zbudować dla ciebie węzły CST i po prostu ich użyć. Jest to ogromna zaleta podczas tworzenia gramatyk: nie ma potrzeby wymyślania 1500 specjalnych węzłów AST, aby modelować 3500 reguł gramatycznych. Pomyśl tylko o tym, że drzewo jest izomorficzne z gramatyką. Z punktu widzenia inżyniera gramatyki jest to całkowicie bezmózgowe, co pozwala mu skupić się na poprawieniu gramatyki i hakowaniu jej do syta. Prawdopodobnie musisz napisać więcej reguł dotyczących odwiedzających węzeł, ale można nimi zarządzać. Więcej o tym później.
To, co robimy z DMS Software Reengineering Toolkit, to automatyczne tworzenie CST na podstawie wyników procesu analizy (GLR). Następnie DMS automatycznie konstruuje „skompresowany” CST ze względu na oszczędność miejsca, eliminując terminale nie przenoszące wartości (słowa kluczowe, znaki interpunkcyjne), semantycznie bezużyteczne produkcje jednoargumentowe i tworząc listy par reguł gramatycznych, które są listami takimi jak:
L = e ;
L = L e ;
L2 = e2 ;
L2 = L2 ',' e2 ;
oraz szeroką gamę odmian takich form. Myślisz w kategoriach reguł gramatycznych i wirtualnego CST; narzędzie działa na skompresowanej reprezentacji. Przyjazny dla mózgu, szybszy / mniejszy w czasie wykonywania.
Co ciekawe, skompresowany CST zbudowany w ten sposób wygląda na AST, który mógłbyś zaprojektować ręcznie (patrz link na końcu do przykładów). W szczególności skompresowany CST nie zawiera żadnych węzłów, które są po prostu konkretną składnią. Są to drobne kawałki niezręczności, na przykład: podczas gdy węzły betonowe dla „(” i „)” klasycznie znalezione w subgrammars wypowiedzi nie są w drzewie, „nawiasy węzła” ma pojawić się w sprężonym CST i musi być obsługiwane. Prawdziwy AST by tego nie miał. Wydaje się, że jest to dość niewielka cena za wygodę polegającą na tym, że nigdy nie trzeba określać konstrukcji AST. Dokumentacja drzewa jest zawsze dostępna i poprawna: gramatyka jest dokumentacją.
Jak uniknąć „dodatkowych gości”? Nie do końca, ale DMS zapewnia bibliotekę AST, która obsługuje AST i w przejrzysty sposób obsługuje różnice między CST i AST. DMS oferuje również ewaluator „gramatyki atrybutów” (AGE), który jest metodą przekazywania wartości obliczanych przez węzły w górę iw dół drzewa; AGE zajmuje się wszystkimi kwestiami związanymi z reprezentacją drzewa, więc inżynier narzędziowy martwi się tylko o efektywne pisanie obliczeń bezpośrednio na zasadach gramatycznych. Wreszcie, DMS zapewnia również wzorce „składni powierzchniowej”, które pozwalają fragmentom kodu od gramatyki do używanej do znajdowania określonych typów poddrzew, bez znajomości większości typów węzłów.
Jedna z pozostałych odpowiedzi mówi, że jeśli chcesz zbudować narzędzia, które mogą regenerować źródło, twoje AST będzie musiało pasować do CST. To nie do końca prawda, ale o wiele łatwiej jest zregenerować źródło, jeśli masz węzły CST. DMS generuje większość prettyprintera automatycznie, ponieważ ma dostęp do obu: -}
Konkluzja: AST są dobre dla małych, zarówno fizycznych, jak i koncepcyjnych. Zautomatyzowana konstrukcja AST z CST zapewnia jedno i drugie i pozwala uniknąć problemu śledzenia dwóch różnych zestawów.
EDYCJA Marzec 2015: Link do przykładów CST vs. „AST” zbudowanych w ten sposób
