Czy wyjście parsera musi być drzewem, czy może to być również ogólny wykres?
Co więcej, czy istnieje jakiś język, który jest wiarygodny i używa ogólnej reprezentacji grafów zamiast drzew do ich składni?
Odpowiedzi:
Dane wyjściowe analizatora składni nie muszą być drzewem. Rzeczywiście, gdy weźmie się pod uwagę takie elementy, jak odwołania z USE zmiennej do jej DEFinition nałożone na abstrakcyjne drzewo składniowe, natychmiast powstaje wykres.
Chodzi o to, że parsowanie generalnie odbywa się w jednym przebiegu - miało to znaczenie z powodów historycznych, takich jak brak miejsca i szybkość procesora, ale także dlatego, że łatwiej jest o tym myśleć. Następnie kolejne fazy ozdabiają parsowane drzewo dodatkowymi informacjami.
Są takie rzeczy, jak gramatyka grafowa, chociaż nie wiem, czy są one używane do analizowania języków programowania.
Pytanie PO jest nieco zacofane. Oczywiście algorytm analizujący może wygenerować cokolwiek chce. Chodzi raczej o zrozumienie, po co jest parsowanie i czy parser generuje wynik spełniający ten cel. Następnie można się zastanawiać, jaka jest odpowiednia reprezentacja tego, na przykład drzewo lub wykres.
Cóż, myślę, że parser to algorytm, który da ci strukturę składni zdania podanego jako dane wejściowe, zgodnie z daną formalną definicją składni języka.
Pamiętaj, że ludzie mogą nie zgadzać się co do składni języka. Niektórzy mogą ograniczyć to do szkieletu czysto formalnego języka, podczas gdy inni mogą wprowadzić nieco bardziej semantyczne rozważania, takie jak typ, gatunek, liczba lub inne bardziej złożone (nie rozróżniam NLP ani języków programowania). Większość języków ma funkcje, które wymagają przedstawienia wykresów, ale to „implementator” (z powodu braku lepszego słowa) decyduje, czy chce to uwzględnić w składni.
Zatem w zależności od tego, jak zdefiniujesz składnię, być może będziesz musiał wygenerować inny rodzaj struktury formalnej.
W prostym przypadku parsowania bezkontekstowego może to zrobić parsowanie drzewa, z wyjątkiem problemu niejednoznaczności opisanego poniżej lub faktu, że możesz go nieco zmodyfikować, aby uzyskać AST (patrz poniżej).
Jednak w bardziej skomplikowanych przypadkach możesz potrzebować różnych struktur, często reprezentowanych przez łącza w drzewie, co prowadzi do struktury wykresu. Zależy to bardzo od twojej definicji składni języka.
Ponadto, jakie drzewo powinieneś wygenerować, nie jest oczywiste. Jeśli weźmiemy pod uwagę gramatykę sąsiadującą z drzewem (TAG), działają one w taki sposób, że drzewo składniowe nie jest takie samo jak drzewo derywacji, chociaż pierwsze z nich można wyprowadzić z drugiego. Które chcesz wygenerować może być trafnym pytaniem.
Istnieje również inna kwestia dotycząca niejednoznaczności. Danemu zdaniu, które należy do twojego języka, można to zrobić na wiele różnych sposobów, można mu przypisać strukturę składniową na wiele różnych sposobów.
Następnie możesz wybrać wyjście tylko jednej z tych struktur, wybranych losowo lub zgodnie z jakimś ściśle określonym kryterium (na przykład podobnym). Możesz także wybrać wyjście kilku lub wszystkich z nich. Jeśli chcesz wypisać kilka, zwykle wygodnie jest spakować w unikalnej strukturze, która podzieli to, co ich łączy. Oszczędność miejsca i czasu obliczeniowego, a złożoność może być prawdziwym problemem.
Kiedy zdecydujesz się wyprowadzić je wszystkie, nie masz innego wyboru, jak udostępnić, ponieważ może istnieć nieskończona liczba możliwych analiz. I w nieskończoność można skończenie odświeżyć tylko poprzez cykl w postaci wykresu. Musisz więc ogólnie stworzyć strukturę graficzną. Ale właściwości tej struktury wykresu powinny być powiązane z wybranym składnią formalną.
Teraz pytanie dotyczyło także Drzewa Składni Abstrakcyjnej. Pominąłem część „abstrakcyjną”, ponieważ wprowadziłaby zamieszanie, imho. Rzeczywiście pytanie to jest już mylące w jego różnych stwierdzeniach.
Jeśli chodzi o AST w ujęciu historycznym, pochodzą one z języka Lisp i systemów manipulacji programowych w latach 1960–1970. Chodziło o to, by traktować programy jako duże wyrażenia, jak formuły matematyczne, zarówno do celów manipulacji, jak i do analizowania właściwości lub formalnego definiowania semantyki, co matematycy potrafią robić na formułach. Jako formuły miały naturalnie strukturę drzewa, ale można je było ozdobić różnymi informacjami, które zamieniły te drzewa w wykresy. Było to wygodne zarówno pod względem formalnym, jak i pragmatycznym, i było dalej wykorzystywane przez kompilatory i systemy programowania.
Zasadniczo AST jest drzewem, jak sugeruje nazwa, ale może przenosić dodatkowe informacje. Reszta zależy od wyborów implementatora i od oczu patrzącego. Czy to wykres czy ozdobione drzewo? Jednak podstawowe drzewo AS ma znaczenie, ponieważ jest to rusztowanie, na którym budujesz zarówno w teorii, jak i programowaniu.
Zauważ, że AST różniło się od drzewa parsowania (składnia była oparta na kontekście) utworzonego przez algorytm analizy składniowej badany w teorii języka formalnego. Powodem było to, że konstrukcja składni była ograniczona technologią parsowania czasu, która sama była ograniczona dostępną niską mocą obliczeniową. Rezultat był taki, że drzewa składniowe były jedynie torturowanymi wariantami tego, co naturalnie uznano by za strukturę programu, i konieczne było dalsze przetwarzanie, a nie realna część podstawowego formalnego procesu analizy, aby uzyskać czystszą i prostszą wersję o nazwie AST.
Jednak reprezentacja drzew na komputerze, zarówno abstrakcyjna, jak i nie, jest nieco ograniczona, gdy chcesz reprezentować wszystkie struktury zdania niejednoznacznego. W szczególności ukrywa to problemy ze złożonością. Problemem może być również zachowanie niejednoznaczności w strukturze wykresu podczas tłumaczenia z parsowania drzew na drzewa AS. Jednak, jeśli się tym martwisz, często możliwe jest zdefiniowanie konkretnej składni w taki sposób, aby parsowanie mogło służyć jako AST. Jest to dozwolone przez bardzo ogólne algorytmy, które radzą sobie z dwuznacznością, oraz przez moc obecnych komputerów.
Jeśli parsujesz używając parsowania GLR (Uogólniony LR) i jeśli parsowanie danych wejściowych jest niejednoznaczne (istnieje wiele możliwych sposobów parsowania danych wejściowych), wynik parsowania może być traktowany jako parsowanie DAG, a nie jako parsować drzewo. Analiza składni DAG w kompaktowy sposób koduje wiele możliwych analiz: wiele możliwych drzew analizy.
Najważniejsze jest jednak to, że jeśli masz gramatykę bezkontekstową i jeśli ciąg wejściowy jest jednoznacznie analizowalny (w gramatyce jest tylko jedno wyprowadzenie, które generuje ten ciąg wejściowy) i jeśli zadaniem analizy jest utworzenie to wyprowadzenie ... wtedy w tych warunkach wynikiem parsowania zawsze będzie parsowanie, ponieważ każda produkcja gramatyki bezkontekstowej z natury ma strukturę drzewa.
Kiedyś napisałem interpreter dla C, w którym „AST” dla operatora + = (na przykład) nie było drzewem. Zastanów się, a[i++] += dgdzie a[i++]jest inti djest double. Niejawne operacje konwersji i pobierania były jawne w drzewie, więc problemem jest to, gdzie umieścić pobieranie a[i++]i konwersję podwoić. Naszym rozwiązaniem było porzucenie drzew. Wynikowy „ASG” wyglądał tak
+=
/ | \
/ | \
/ | \
/ convert \
| | \
| fetch fetch
| / |
index d
/ \
a postinc
|
i
Byłem tym zaskoczony, dopóki nie zdałem sobie sprawy, że to nie drzewo jest abstrakcyjne, ani nie chodzi o jakieś abstrakcyjne „drzewo składniowe”, ale składnia jest abstrakcyjna.
Tak więc, aby odpowiedzieć na twoje pytanie, dochodzę do wniosku, że abstrakcyjne drzewo składniowe, a także konkretne drzewo składniowe lub drzewo decyzyjne, lub jakiekolwiek inne drzewo, powinno być drzewem.
Z drugiej strony nic nie powinno przeszkadzać nikomu w używaniu abstrakcyjnego wykresu składni lub abstrakcyjnego diagramu składni lub abstrakcyjnego sześcianu składni lub abstrakcyjnej specyfikacji składni.
Przypuszczam, że abstrakcyjne drzewo składniowe „abstrakcyjnego drzewa składniowego” pomogłoby mi uniknąć pomyłki.