Analiza 
Składniow
a

Przemysław Roszniowski-Bury
Łukasz Sobczuk

Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

AGH University of Science and Technology

Analiza składniowa (analiza 

syntaktyczna)

» Z ang. Parsing – proces analizy tekstu 

w celu ustalenia jego struktury 
gramatycznej i zgodności z gramatyką 
języka

Analiza składniowa 

(parsing)

Analizator 
Leksykaln
y

Analizator składniowy 

(parser)

» program odpowiadający za 

przeprowadzenie analizy składniowej

» Często jest jedną z części translatora 

lub interpretera. 

» Sprawdza składnie i buduję strukturę 

danych (drzewo składniowe, drzewo 
wyprowadzenia lub inna struktura 
gramatyczna )

Drzewo składniowe

» Wynik 

przeprowadzenia 
analizy składniowej 
zdania zgodnie z 
pewną gramatyką

» A(B(E,F),C,D(G(I),H(

J,K,L)))

Metody analizy składniowej

Analiza zstępująca

Analiza wstępująca 

Metody 

niekierunkowe

• Parser Ungera

• Algorytm CYK

Metody kierunkowe • Przeszukiwanie wszerz 

• Przeszukiwanie w głąb

• Metoda zejść 

rekurencyjnych z 

powrotami 

• LL(k)

• Algorytm Earleya

• Metoda przesunięcie – 

redukcja:

 M. Ograniczonego 

kontekstu BC (k,l)

 M. oparte na 

pierwszeństwie 

 Metody LR

Analiza zstępująca (top-

down)

» Strategia znajdowania powiązań 

między danymi przez stawianie 
hipotez dotyczących drzewa rozbioru 
składniowego i sprawdzanie, czy 
zależności między danymi są zgodne 
z tymi hipotezami. 

Przeszukiwanie wszerz

1 2 3 4
2 3 4 5 6
3 4 5 6
4 5 6 7 8
5 6 7 8 9 10
6 7 8 9 10
7 8 9 10 11 12
8 9 10 11 12
9 10 11 12
10 11 12
11 12
12

Przeszukiwanie wgłąb

1-2
2-3
3-4
3-5
2-6
1-7
1-8
8-9
9-10
9-11
8-12

Parser Ungera

» Zstępujący algorytm analizy 

składniowej działający dla gramatyk 
bezkontekstowych, opublikowany w 
1968 roku przez Ungera

» Działanie polega na przeszukiwaniu w 

głąb rozbić ciągu wejściowego 
zgodnych z produkcjami danej 
gramatyki

Parser LL

» parser czytający tekst od lewej do 

prawej 
i produkujący lewostronne 
wyprowadzenie metodą zstępującą. 
Popularne rodzaje parserów LL to 
parsery sterowane tablicą 
i rekurencyjne.

Analiza wstępująca 

(bottom-up)

Ogólna metoda analizy składniowej,      

     w której zaczyna się od słowa 

wejściowego     i próbuje się je 

zredukować do symbolu startowego. 

(Parser próbuje przepisywać wejście, 

poprzez zastępowanie znalezionych 

prawych stron produkcji gramatyki, ich 

lewymi stronami)

Metody niekierunkowe

analizy wstępującej

» Algorytm CYK 

Metody kierunkowe

analizy wstępującej

» Algorytm Earleya
» Metoda przesunięcie-redukcja

 metodą ograniczonego kontekstu (parsery 

BC)

 metodą pierwszeństwa operatorów
 Metoda LR

Gramatyka

Mleko małe dziecko wypiło.

Gramatyka

Małe dziecko wypiło mleko.

Jak zweryfikować w sposób 

formalny czy zdanie jest 

poprawne?

Małe      dziecko       wypiło        mleko.

Drzewo wyprowadzenia

Reguły definiujące 

gramatykę

Reguły definiujące 

gramatykę

Dziękujemy za uwagę !!