w tym artykule przeanalizujemy koncepcję i zastosowania drzewa Parse w projektowaniu kompilatora . Najpierw przyjrzyjmy się dwóm pojęciom:

• Parse : oznacza rozdzielenie (zdanie) na jego części składowe i opisanie ich ról składniowych lub po prostu jest to akt parsowania łańcucha lub tekstu.
• drzewo: drzewo może być powszechnie używanym abstrakcyjnym typem danych, który symuluje hierarchiczną strukturę drzewa, z wartością korzenia i pod drzewami młodych z węzłem macierzystym, reprezentowanym jako grupa połączonych węzłów.

Parse Tree :

• Parse tree jest hierarchiczną reprezentacją terminali lub nie-terminali.
• te symbole (terminale lub nie-terminale) reprezentują wyprowadzenie gramatyki w celu uzyskania wejściowych łańcuchów.
• w parsowaniu ciąg sprężyny za pomocą symbolu początku.
• symbol początkowy gramatyki musi być użyty jako korzeń drzewa parsowania.
• liście drzewa parsowego reprezentują końcówki.
• każdy węzeł wewnętrzny reprezentuje gramatykę.

zasady rysowania drzewa parsowania:

1. wszystkie węzły liści muszą być terminalami.
2. wszystkie wewnętrzne węzły nie muszą być terminalami.
3. in-order traversal daje oryginalny ciąg wejściowy.

przykład-1:
weźmy przykład gramatyki (reguły produkcji).

S -> sABA -> aB -> b

łańcuch wejściowy to „sab”, następnie drzewo Parse to:

przykład-2:
weźmy inny przykład gramatyki (reguły produkcji).

S -> ABA -> c/aAB -> d/bB

łańcuch wejściowy to „acbd”, następnie drzewo Parse jest :

Zastosowanie drzewa Parse:

• pomaga w analizie składniowej poprzez odzwierciedlenie składni języka wejściowego.
• używa reprezentacji danych wejściowych w pamięci o strukturze zgodnej z gramatyką.
• zalety używania drzew parsowania zamiast działań semantycznych: wykonasz wiele przejść nad informacjami bez konieczności ponownego analizowania danych wejściowych.

Uwaga czytelniku! Nie przestawaj się uczyć. Zdobądź wszystkie ważne koncepcje teorii CS dla SDE wywiady z kursem teorii CS w cenie przyjaznej dla studentów i przygotuj się na branżę.