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ę !!