Analiza składni: typy analizowania z góry na dół i z dołu do góry kompilatora

Analiza składni w procesie projektowania kompilatora następuje po fazie analizy leksykalnej. Jest ona również znana jako drzewo parsowania lub drzewo składni. Drzewo parsowania jest opracowywane przy pomocy wstępnie zdefiniowanej gramatyki języka. Analizator składni sprawdza również, czy dany program spełnia reguły wynikające z gramatyki bezkontekstowej. Jeśli spełniają, parser tworzy drzewo parsowania tego programu źródłowego. W przeciwnym razie wyświetli komunikaty o błędach.

Dlaczego potrzebujesz Analizatora składni?

• Sprawdź, czy kod jest poprawny gramatycznie
• Analizator syntaktyczny pomaga zastosować reguły do ​​kodu
• Pomaga upewnić się, że każdy nawias otwierający ma odpowiednie saldo zamknięcia
• Każda deklaracja ma typ i typ musi istnieć

Ważna terminologia dotycząca analizatora składni

Ważne terminologie stosowane w procesie analizy składni:

• Zdanie: Zdanie to grupa znaków nad jakimś alfabetem.

• Leksem: Leksem to jednostka składniowa języka najniższego poziomu (np. suma, początek).

• Token: Token to po prostu kategoria leksemów.

• Słowa kluczowe i słowa zastrzeżone – Jest to identyfikator używany jako stała część składni instrukcji. Jest to słowo zastrzeżone, którego nie można używać jako nazwy zmiennej ani identyfikatora.

• Hałasowe słowa – Słowa stanowiące szum są opcjonalne i są wstawiane do wypowiedzi w celu zwiększenia czytelności zdania.

• Komentarze – To bardzo ważna część dokumentacji. Wyświetla się głównie przez, /* */ lub//Puste (spacje)

• Ograniczniki – Jest to element syntaktyczny, który wyznacza początek lub koniec jakiejś jednostki syntaktycznej. Podobnie jak instrukcja lub wyrażenie „rozpocznij”…”koniec” lub {}.

• Zestaw znaków – ASCII, Unikod

• Identyfikatory – Jest to ograniczenie długości, które pomaga zmniejszyć czytelność zdania.

• Operasymbole Tora – + i – wykonuje dwie podstawowe operacje arytmetyczne.
• Elementy syntaktyczne języka

Dlaczego potrzebujemy parsowania?

Analiza sprawdza również, czy ciąg wejściowy jest poprawnie sformułowany, a jeśli nie, odrzuca go.

Poniżej przedstawiono ważne zadania wykonywane przez parser podczas projektowania kompilatora:

• Pomaga wykryć wszystkie rodzaje błędów składniowych
• Znajdź pozycję, w której wystąpił błąd
• Jasny i dokładny opis błędu.
• Odzyskiwanie po błędzie, aby kontynuować i znaleźć dalsze błędy w kodzie.
• Nie powinno wpływać na kompilację „poprawnych” programów.
• Analiza musi odrzucić nieprawidłowe teksty, zgłaszając błędy składniowe

Techniki analizowania

Techniki analizowania dzielą się na dwie różne grupy:

• Analiza z góry na dół,
• Analiza oddolna

Analiza z góry na dół

W przypadku analizowania z góry na dół konstrukcja drzewa analizującego rozpoczyna się od korzenia, a następnie przebiega w kierunku liści.

Dwa typy analizowania z góry na dół to:

1. Analiza predykcyjna:

Analiza predykcyjna może przewidzieć, która produkcja powinna zostać użyta do zastąpienia określonego ciągu wejściowego. Analizator predykcyjny wykorzystuje punkt wyprzedzający, który wskazuje kolejne symbole wejściowe. W przypadku tej techniki analizowania wycofywanie się nie stanowi problemu. Jest znany jako parser LL(1).

2. Rekursywna analiza zejścia:

Ta technika analizowania rekurencyjnie analizuje dane wejściowe w celu utworzenia drzewa prase. Składa się z kilku małych funkcji, po jednej dla każdego nieterminala w gramatyce.

Analiza oddolna

W analizie składniowej od dołu w projektowaniu kompilatora konstrukcja drzewa składniowego zaczyna się od liścia, a następnie przetwarza się je w kierunku korzenia. Nazywa się to również analizą składniową przesunięcia-redukcji. Ten typ analizy składniowej w projektowaniu kompilatora jest tworzony przy pomocy pewnych narzędzia programowe.

Błąd – metody odzyskiwania

Typowe błędy występujące podczas analizowania oprogramowania systemowego

• Leksykalny: Nazwa błędnie wpisanego identyfikatora
• Syntaktyczny: niezrównoważony nawias lub brakujący średnik
• Semantyczny: niezgodne przypisanie wartości
• logiczny: Nieskończona pętla i nieosiągalny kod

Parser powinien być w stanie wykryć i zgłosić każdy błąd znaleziony w programie. Tak więc, gdy tylko wystąpi błąd, parser. Powinien być w stanie go obsłużyć i kontynuować parsowanie pozostałych danych wejściowych. Program może mieć następujące typy błędów na różnych etapach procesu kompilacji. Istnieje pięć typowych metod odzyskiwania błędów, które można zaimplementować w parserze

Odzyskiwanie trybu wyciągu

• W przypadku, gdy parser napotka błąd, pomoże Ci to w podjęciu kroków korygujących. Dzięki temu pozostałe wejścia i stany mogą być analizowane z wyprzedzeniem.
• Na przykład dodanie brakującego średnika jest możliwe w przypadku metody odzyskiwania w trybie instrukcji. Jednak projektant analizy składniowej musi zachować ostrożność podczas wprowadzania tych zmian, ponieważ jedna zła korekta może prowadzić do nieskończonej pętli.

Odzyskiwanie w trybie paniki

• W przypadku, gdy parser napotka błąd, ten tryb ignoruje resztę instrukcji i nie przetwarza danych wejściowych z błędnych danych wejściowych do ogranicznika, takiego jak średnik. Jest to prosta metoda odzyskiwania błędów.
• W tym typie metody odzyskiwania parser odrzuca symbole wejściowe jeden po drugim, aż zostanie znaleziona pojedyncza wyznaczona grupa tokenów synchronizujących. Tokeny synchronizujące zazwyczaj używają ograniczników, takich jak lub.

Odzyskiwanie na poziomie frazy

• Kompilator koryguje program wstawiając lub usuwając tokeny. Dzięki temu może kontynuować analizę od miejsca, w którym się znajdował. Wykonuje korekcję na pozostałym wejściu. Może zastąpić przedrostek pozostałych danych wejściowych jakimś ciągiem znaków, co pomaga parserowi kontynuować proces.

Produkcja błędów

• Odzyskiwanie produkcji błędów rozszerza gramatykę języka, który generuje błędne konstrukcje. Następnie parser wykonuje diagnostykę błędów dotyczącą tej konstrukcji.

Globalna korekta

• Kompilator powinien wprowadzać jak najmniej zmian podczas przetwarzania niepoprawnego ciągu wejściowego. Biorąc pod uwagę niepoprawne ciągi wejściowe a i gramatykę c, algorytmy będą szukać drzewa parsowania dla powiązanego ciągu b. Podobnie jak niektóre wstawienia, usunięcia i modyfikacje tokenów potrzebne do przekształcenia an w b, jest ich jak najmniej.

Gramatyka

Gramatyka to zbiór reguł strukturalnych opisujących język. Gramatyki przypisują strukturę każdemu zdaniu. Termin ten odnosi się również do badania tych reguł, a plik ten obejmuje morfologię, fonologię i składnię. Jest w stanie opisać wiele składni języki programowania.

Zasady gramatyki formy

• Symbol nieterminalny powinien pojawić się po lewej stronie co najmniej jednej produkcji
• Symbol celu nigdy nie powinien być wyświetlany po prawej stronie ::= żadnej produkcji
• Reguła jest rekurencyjna, jeśli LHS pojawia się w jej RHS

Konwencje notacyjne

Symbol konwencji notacyjnych można wskazać, umieszczając element w nawiasach kwadratowych. Jest to dowolna sekwencja wystąpień elementu, którą można wskazać, umieszczając element w nawiasach klamrowych, po których następuje symbol gwiazdki, { … }*.

Jest to wybór alternatywy, która może wykorzystywać symbol w ramach jednej reguły. W razie potrzeby można go ująć w nawiasy ([,] ).

Dwa typy obszarów konwencji notacyjnych Terminal i Non-terminale

1.Zaciski:

• Małe litery alfabetu, takie jak a, b, c,
• Operasymbole Tor, takie jak +, -, * itp.
• Symbole interpunkcyjne, takie jak nawiasy, skrót, przecinek
• 0, 1, …, 9 cyfr
• Ciągi pogrubione, takie jak id lub if, wszystko, co reprezentuje pojedynczy symbol końcowy

2. Nieterminale:

• Wielkie litery, takie jak A, B, C
• Nazwy pisane kursywą małymi literami: wyrażenie lub niektóre

Gramatyka bezkontekstowa

CFG to gramatyka lewostronnie rekurencyjna, która ma co najmniej jedną produkcję tego typu. Reguły gramatyki bezkontekstowej są głównie rekurencyjne. Analizator składni sprawdza, czy konkretny program spełnia wszystkie zasady gramatyki bezkontekstowej, czy też nie. Jeśli tak, analizatory składni tych reguł mogą utworzyć drzewo analizy dla tego programu.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Wyprowadzenie gramatyczne

Wyprowadzenie gramatyczne to sekwencja reguł gramatycznych, która przekształca symbol początkowy w ciąg znaków. Wyprowadzenie dowodzi, że ciąg znaków należy do języka gramatycznego.

Wyprowadzenie skrajnie lewe

Kiedy zdana forma danych wejściowych jest skanowana i zastępowana w kolejności od lewej do prawej, nazywa się to wyprowadzeniem od lewej strony. Forma zdaniowa wyprowadzona z wyprowadzenia skrajnie lewego nazywana jest formą zdaniową lewą.

Wyprowadzenie skrajnie prawe

Zeskanuj wyprowadzenie z prawej strony i zastąp dane wejściowe regułami produkcji, od prawej do lewej, sekwencja. Jest to znane jako wyprowadzenie skrajnie prawe. Forma zdaniowa wyprowadzona z wyprowadzenia znajdującego się najbardziej na prawo nazywana jest formą zdaniową prawą.

Analizator składni a leksykalny

Analizator składni	Analizator leksykalny
Analizator składni zajmuje się głównie rekurencyjnymi konstrukcjami języka.	Analizator leksykalny ułatwia zadanie analizatora składni.
Analizator składni działa na tokenach w programie źródłowym, aby rozpoznać znaczące struktury w języku programowania.	Analizator leksykalny rozpoznaje token w programie źródłowym.
Otrzymuje dane wejściowe w postaci tokenów z analizatorów leksykalnych.	Odpowiada za ważność tokena dostarczonego przez analizator składni

Wady korzystania z analizatorów składni

• Nigdy nie ustali, czy token jest ważny, czy nie
• Nie pomaga określić, czy operacja wykonana na typie tokena jest prawidłowa, czy nie
• Nie możesz zdecydować, że token zostanie zadeklarowany i zainicjowany przed jego użyciem

Podsumowanie

• Analiza składni to druga faza procesu projektowania kompilatora, następująca po analizie leksykalnej
• Analizator syntaktyczny pomaga zastosować reguły do ​​kodu
• Zdanie, leksem, token, słowa kluczowe i słowa zastrzeżone, słowa szumu, komentarze, ograniczniki, zestaw znaków, identyfikatory to niektóre ważne terminy używane w analizie składni w konstrukcji kompilatora
• Parse sprawdza, czy ciąg wejściowy jest poprawnie sformułowany, a jeśli nie, odrzuca go
• Techniki analizowania dzielą się na dwie różne grupy: analizowanie od góry do dołu i analizowanie od dołu do góry
• Leksykalne, syntaktyczne, semantyczne i logiczne to niektóre typowe błędy występujące podczas metody analizy
• Gramatyka to zbiór reguł strukturalnych opisujących język
• Symbol konwencji notacyjnej można wskazać, umieszczając element w nawiasach kwadratowych
• CFG to gramatyka lewostronnie rekurencyjna, która ma co najmniej jedną produkcję tego typu
• Wyprowadzenie gramatyczne to sekwencja reguł gramatycznych, która przekształca symbol początkowy w ciąg znaków
• Analizator składni zajmuje się głównie rekurencyjnymi konstrukcjami języka, podczas gdy analizator leksykalny ułatwia zadanie analizatora składni w DBMS
• Wadą metody analizatora składni jest to, że nigdy nie ustali, czy token jest ważny, czy nie