Projekt kompilatora - typy analizowania
Analizatory składni stosują się do reguł produkcji zdefiniowanych za pomocą gramatyki bezkontekstowej. Sposób, w jaki reguły produkcji są wdrażane (wyprowadzanie), dzieli analizowanie na dwa typy: analizowanie odgórne i analiza oddolna.
Analiza odgórna
Kiedy parser zaczyna konstruować drzewo parsowania od symbolu startu, a następnie próbuje przekształcić symbol początkowy na wejście, nazywa się to analizowaniem zstępującym.
Recursive descent parsing: Jest to powszechna forma analizy odgórnej. Nazywa się to rekurencyjnym, ponieważ wykorzystuje procedury rekurencyjne do przetwarzania danych wejściowych. Rekurencyjne analizowanie zejścia cierpi z powodu wycofywania.
Backtracking: Oznacza to, że jeśli jedno wyprowadzenie produkcji nie powiedzie się, analizator składni ponownie uruchomi proces przy użyciu innych reguł tej samej produkcji. Ta technika może przetwarzać ciąg wejściowy więcej niż jeden raz, aby określić właściwą produkcję.
Analiza oddolna
Jak sama nazwa wskazuje, analiza oddolna rozpoczyna się od symboli wejściowych i próbuje skonstruować drzewo analizy aż do symbolu początkowego.
Example:
Ciąg wejściowy: a + b * c
Zasady produkcji:
S → E
E → E + T
E → E * T
E → T
T → idZacznijmy analizę oddolną
a + b * cPrzeczytaj dane wejściowe i sprawdź, czy jakakolwiek produkcja jest zgodna z danymi wejściowymi:
a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S