Co to jest analiza składniowa?
Analiza składni to druga faza procesu projektowania kompilatora, w której podany ciąg wejściowy jest sprawdzany pod kątem potwierdzenia reguł i struktury gramatyki formalnej. Analizuje strukturę składniową i sprawdza, czy dane wejście ma poprawną składnię języka programowania, czy nie.
Analiza składni w procesie projektowania kompilatora następuje po fazie analizy leksykalnej. Jest również znany jako drzewo analizy lub drzewo składni. Drzewo parsowania jest rozwijane przy pomocy predefiniowanej gramatyki języka. Analizator składni sprawdza również, czy dany program spełnia zasady wynikające z gramatyki bezkontekstowej. Jeśli to spełnia, analizator składni tworzy drzewo analizy tego programu źródłowego. W przeciwnym razie wyświetli komunikaty o błędach.
W tym samouczku dowiesz się
- Dlaczego potrzebujesz analizatora składni?
- Ważna terminologia dotycząca analizatora składni
- Dlaczego potrzebujemy parsowania?
- Techniki analizy
- Błąd - metody odzyskiwania
- Gramatyka:
- Konwencje notacyjne
- Gramatyka bezkontekstowa
- Wyprowadzenie gramatyki
- Analizator składni a analizator leksykalny
- Wady korzystania z analizatorów składni
Dlaczego potrzebujesz analizatora składni?
- Sprawdź, czy kod jest poprawny gramatycznie
- Analizator składniowy pomaga zastosować reguły do kodu
- Pomaga upewnić się, że każdy nawias otwierający ma odpowiednią równowagę zamykającą
- Każda deklaracja ma typ i typ musi istnieć
Ważna terminologia dotycząca analizatora składni
Ważne terminologie używane w procesie analizy składni:
- Zdanie: zdanie to grupa znaków na pewnym alfabecie.
- Leksem: leksem to jednostka składniowa języka najniższego poziomu (np. Całość, początek).
- Token: token to tylko kategoria leksemów.
- Słowa kluczowe i słowa zastrzeżone - jest to identyfikator, który jest używany jako stała część składni instrukcji. Jest to zastrzeżone słowo, którego nie można używać jako nazwy zmiennej ani identyfikatora.
- Wyrazy zawierające szum - słowa zawierające szumy są opcjonalne i są wstawiane do oświadczenia w celu zwiększenia czytelności zdania.
- Uwagi - To bardzo ważna część dokumentacji. Najczęściej jest wyświetlany przez, / * * / lub // Puste (spacje)
- Ograniczniki - jest to element składniowy, który oznacza początek lub koniec jakiejś jednostki syntaktycznej. Podobnie jak w przypadku stwierdzenia lub wyrażenia, „początek”… '' koniec ”lub {}.
- Zestaw znaków - ASCII, Unicode
- Identyfikatory - to ograniczenie długości, które pomaga zmniejszyć czytelność zdania.
- Symbole operatora - + i - wykonują dwie podstawowe operacje arytmetyczne.
- Składniowe elementy języka
Dlaczego potrzebujemy parsowania?
Analiza sprawdza również, czy ciąg wejściowy jest poprawnie sformułowany, a jeśli nie, odrzuć go.
Poniżej przedstawiono ważne zadania wykonywane przez parser w projekcie kompilatora:
- Pomaga wykryć wszystkie typy 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 składniowa musi odrzucać nieprawidłowe teksty, zgłaszając błędy składniowe
Techniki analizy
Techniki parsowania są podzielone na dwie różne grupy:
- Analiza odgórna,
- Analiza oddolna
Analiza odgórna:
W analizie odgórnej konstrukcja drzewa parsowania zaczyna się od korzenia, a następnie przechodzi w kierunku liści.
Są dwa typy analizy odgórnej:
- Analiza predykcyjna:
Analiza predykcyjna może przewidzieć, która produkcja powinna zostać użyta do zastąpienia określonego ciągu wejściowego. Parser predykcyjny wykorzystuje punkt wyprzedzenia, który wskazuje na następne symbole wejściowe. Ta technika analizy nie stanowi problemu z wycofywaniem się. Jest znany jako Parser LL (1)
- Rekurencyjne analizowanie zejścia:
Ta technika parsowania rekurencyjnie analizuje dane wejściowe, aby utworzyć drzewo prazy. Składa się z kilku małych funkcji, po jednej dla każdego nieterminala w gramatyce.
Analiza oddolna:
W analizie oddolnej w projekcie kompilatora konstrukcja drzewa parsowania rozpoczyna się od urlopu, a następnie jest przetwarzana w kierunku jego korzenia. Nazywa się to również analizowaniem z redukcją przesunięcia. Ten typ analizy w projekcie kompilatora jest tworzony za pomocą niektórych narzędzi programowych.
Błąd - metody odzyskiwania
Typowe błędy występujące podczas analizowania oprogramowania systemowego
- Leksykalny : nazwa nieprawidłowo wpisanego identyfikatora
- Składnia : niezbalansowany nawias lub brakujący średnik
- Semantyczne : przypisanie niezgodnej wartości
- Logiczne : nieskończona pętla i niedostępny kod
Parser powinien być w stanie wykryć i zgłosić każdy błąd znaleziony w programie. Tak więc, ilekroć wystąpił błąd, parser. Powinien być w stanie sobie z tym poradzić i kontynuować analizowanie 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 usuwania błędów, które można zaimplementować w parserze
Odzyskiwanie w trybie instrukcji
- W przypadku, gdy parser napotka błąd, pomaga podjąć kroki naprawcze. Dzięki temu pozostałe dane wejściowe i stany mogą być analizowane z wyprzedzeniem.
- Na przykład dodanie brakującego średnika odbywa się w metodzie odtwarzania w trybie instrukcji. Jednak projektant analizy składniowej musi zachować ostrożność podczas wprowadzania tych zmian, ponieważ jedna błędna korekta może prowadzić do nieskończonej pętli.
Przywracanie stanu paniki
- W przypadku, gdy parser napotka błąd, ten tryb ignoruje resztę instrukcji i nie przetwarza danych wejściowych od błędnych danych wejściowych do separatora, jak średnik. To jest prosta metoda usuwania błędów.
- W tego typu metodzie odtwarzania parser odrzuca symbole wejściowe jeden po drugim, dopóki nie zostanie znaleziona pojedyncza wyznaczona grupa tokenów synchronizujących. Tokeny synchronizujące zwykle używają ograniczników, takich jak lub.
Odzyskiwanie na poziomie frazy:
- Kompilator poprawia program, wstawiając lub usuwając tokeny. Pozwala to na przystąpienie do analizy z miejsca, w którym się znajdował. Dokonuje korekty na pozostałym wejściu. Może zastąpić przedrostek pozostałych danych wejściowych jakimś ciągiem, co pomaga parserowi w kontynuowaniu procesu.
Error Productions
- Odzyskiwanie po wystąpieniu błędów rozszerza gramatykę języka, który generuje błędne konstrukcje. Następnie analizator składni przeprowadza diagnostykę błędów dotyczącą tej konstrukcji.
Globalna korekta:
- Kompilator powinien wprowadzać mniejszą liczbę zmian, jak to możliwe, podczas przetwarzania niepoprawnego ciągu wejściowego. Biorąc pod uwagę niepoprawny ciąg wejściowy 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 wykonane z tokenów potrzebnych do przekształcenia an w b są tak małe, jak to tylko możliwe.
Gramatyka:
Gramatyka to zbiór reguł strukturalnych, które opisują język. Gramatyka nadaje strukturę każdemu zdaniu. Termin ten odnosi się również do badania tych reguł, a ten plik zawiera morfologię, fonologię i składnię. Jest w stanie opisać wiele składni języków programowania.
Zasady gramatyki formularzy
- 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ę po prawej stronie
Konwencje notacyjne
Symbol konwencji notacji można wskazać poprzez umieszczenie elementu w nawiasach kwadratowych. Jest to dowolna sekwencja wystąpień elementu, którą można wskazać, umieszczając element w nawiasach, po których następuje symbol gwiazdki, {…} *.
Jest to wybór alternatywy, która może używać symbolu w ramach jednej reguły. W razie potrzeby może być ujęty w nawias ([,]).
Dwa typy konwencji notacji w obszarze Terminale i Nieterminale
1. zaciski:
- Małe litery alfabetu, takie jak a, b, c,
- Symbole operatora, takie jak +, -, * itp.
- Symbole interpunkcyjne, takie jak nawiasy, krzyżyk, przecinek
- 0, 1,…, 9 cyfr
- Wytłuszczone łańcuchy, takie jak id lub if, cokolwiek, co reprezentuje pojedynczy symbol terminala
2. nieterminale:
- Wielkie litery, takie jak A, B, C
- Nazwy pisane kursywą małymi literami: wyrażenie lub niektóre
Gramatyka bezkontekstowa
CFG jest gramatyką rekurencyjną lewostronną, która ma co najmniej jedną produkcję tego typu. Reguły w gramatyce bezkontekstowej są głównie rekurencyjne. Analizator składni sprawdza, czy określony program spełnia wszystkie zasady gramatyki bezkontekstowej, czy nie. Jeśli tak się stanie, analizatory składni tych reguł mogą utworzyć drzewo analizy dla tego programu.
expression -> expression -+ termexpression -> expression - termexpression-> termterm -> term * factorterm -> expression/ factorterm -> factor factorfactor -> ( expression )factor -> id
Wyprowadzenie gramatyki
Wyprowadzenie gramatyki to sekwencja reguł gramatycznych, która przekształca symbol początkowy w łańcuch. Wyprowadzenie dowodzi, że ciąg należy do języka gramatyki.
Wyprowadzenie najbardziej lewostronne
Kiedy zdaniowa forma danych wejściowych jest skanowana i zastępowana w kolejności od lewej do prawej, nazywa się to wyprowadzeniem najbardziej z lewej strony. Forma zdań, która jest wyprowadzana przez lewe wyprowadzenie, nazywa się formą zdaniową po lewej stronie.
Wyprowadzenie najbardziej po prawej
Wyprowadzenie z prawej strony skanuje i zastępuje dane wejściowe regułami produkcji, od prawej do lewej, w kolejności. Nazywa się to wyprowadzeniem najbardziej po prawej stronie. Forma zdaniowa wywodząca się z prawostronnego wyprowadzenia jest znana jako forma zdaniowa prawostronna.
Analizator składni a analizator 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 w celu rozpoznawania znaczących struktur 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 określi, czy token jest ważny, czy nie
- Not pomaga określić, czy operacja wykonana na typie tokenu jest prawidłowa, czy nie
- Nie możesz zdecydować, że token został zadeklarowany i zainicjowany przed użyciem
Podsumowanie
- Analiza składni to druga faza procesu projektowania kompilatora, która następuje po analizie leksykalnej
- Analizator składniowy 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
- Analizuj sprawdza, czy ciąg wejściowy jest poprawnie sformułowany, a jeśli nie, odrzuć go
- Techniki analizy dzielą się na dwie różne grupy: analiza odgórna, analiza oddolna
- Leksykalna, składniowa, semantyczna i logiczna to niektóre typowe błędy występujące podczas analizy
- Gramatyka to zbiór reguł strukturalnych, które opisują język
- Symbol konwencji notacji można wskazać poprzez umieszczenie elementu w nawiasach kwadratowych
- CFG jest gramatyką rekurencyjną lewostronną, która ma co najmniej jedną produkcję tego typu
- Wyprowadzenie gramatyki to sekwencja reguł gramatycznych, która przekształca symbol początkowy w łańcuch
- 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 określa, czy token jest prawidłowy, czy nie