Efektywna analiza skladniowa GBK PDF

Preview

Summary

Download Efektywna analiza skladniowa GBK PDF

Description

TEORETYCZNE PODSTAWY INFORMATYKI Efektywna analiza składniowa GBK Rozbiór zdań i struktur zdaniowych jest w wielu przypadkach procesem bardzo skomplikowanym. Jego złożoność zależy od rodzaju reguł produkcji użytych przy definiowaniu języka. Opracowaniem algorytmów rozbioru języków zajmuje się teoria analizy składniowej. Dąży się do tego, aby koszt obliczeń związanych z analizą zdania był funkcją liniową (O(n)), bądź quasi-liniową (O(n log(n)) w funkcji długości zdania. Rozbiór zdań – tworzenie algorytmów rozbioru syntaktycznego wyrażeń gramatycznych. Przykład 1 Dana jest gramatyka bezkontekstowa G = ({S,A},{a,b,c},P,S) P:

S  aA A  bA Ac

L(G) = {ac,abc,abbc,abbbc, …} Dla powyższej gramatyki decyzja o zastąpieniu zmiennej A ciągiem wynikającym z produkcji drugiej lub trzeciej może być podjęta po sprawdzeniu jaki jest następny symbol w badanym słowie. Dla innych gramatyk już tak nie można postępować. Przykład 2 Dana jest gramatyka bezkontekstowa G = ({S,A,B},{a,b,c},P,S) P:

S  aA | aB A  aA | b B  aB | c

L(G) = {ab,aab,aaab, … , ac,aac,aaac, …} w = a?...aaaab czy …aaaac Dla powyższej gramatyki decyzja o zastąpieniu zmiennej S ciągiem wynikającym z produkcji pierwszej lub drugiej nie może być podjęta po sprawdzeniu jaki jest następny symbol w badanym słowie. Istnieje co prawda możliwość rozbioru zdania według jednej wybranej możliwości dotąd, dokąd będzie to możliwe, a następnie, w przypadku niepowodzenia powrót do ostatniej możliwości wyboru jednej z dostępnych produkcji i ponowna próba rozbioru zdania. Postępowanie takie nazywamy analizą z powrotami, ale powoduje ono znaczny wzrost złożoności obliczeniowej i dlatego w praktycznych zastosowaniach powinno się unikać struktur językowych powodujących powroty w procesie rozbioru zdań. Dlatego zajmiemy się gramatykami, w których symbole początkowe alternatywnych ciał produkcji dla tych samych głów produkcji, są różne i dla takich gramatyk podamy technikę tworzenia kodu źródłowego dokonującego ich rozbioru.

-1-

Re guł a 1 Dla produkcji: A  B1 | B2 | … | Bn zbiory pierwszych symboli w zdaniach, które mogą być wyprowadzone z Bi muszą być rozłączne, tzn.:

p (Bi)  p (Bj) = 

dla wszystkich i  j gdzie p (B) oznacza zbiór pierwszych symboli zdania

czyli ⁞ A  aB | bC A  c | Ba Ad

{a}  {b}  {c}  {e,f}  {d} =  niepowtarzające się pierwsze symbole terminalne

⁞ B  eB | fC ⁞

Dla gramatyki z przykładu 2: P:

S  aA | aB A  aA | b B  aB | c

można podać jej inną postać spełniającą regułę 1: P:

S  aB B  aB | C Cb|c

Re guł a 2 Dla każdego zmiennej A, z której można wyprowadzić pusty ciąg symboli (A ) zbiór jego pierwszych symboli musi być rozłączny ze zbiorem symboli, które mogą następować po dowolnym ciągu wyprowadzonym z A, tzn.:

p (A)  n (A) =  czyli ⁞ A  aB |  A  b | cBC A  dA

{a,b,c,d}  {e,f,g} =  inne symbole terminalne pierwsze w A i pierwsze „po wyjściu z” A (o ile A generuje )

⁞ B  Ae | aCb C  BAf | aCAg ⁞

Powyższe reguły pozwalają na rozbiór zdań bez powrotów.

-2-

ukc jaa diagramuu składni i kodu programu Kons truk Diagram składni (rozbioru) jest graficznym sposobem zapisu GBK równoważnym zapisowi w postaci BNF. Podane powyżej reguły dla diagramów składni formułuje się następująco: Re guł a 1 W każdym punkcie rozgałęzienia o wyborze dalszej drogi decyduje pierwszy symbol terminalny pobrany w tej gałęzi. Dlatego żadne dwie gałęzie nie mogą zaczynać się od tego samego symbolu. Re guł a 2 Jeśli przez diagram A możemy przejść bez wczytania jakiegokolwiek symbolu terminalnego, to pierwsze napotkane symbole w tym diagramie muszą być inne niż pierwsze napotkane po wyjściu z diagramu A. Reguły konstrukcji diagramów składni 1. Każdemu wystąpieniu symbolu terminalnego a odpowiada następujący diagram: a w kodzie programu instrukcja rozpoznająca ten symbol, po której bezpośrednio jest następna instrukcja pobierająca kolejny symbol ze słowa wejściowego 2. Każdemu wystąpieniu zmiennej A odpowiada następujący diagram: a w kodzie programu wywołanie podprogramu A 3. Produkcji postaci A  B1 | B2 | … | Bn odpowiada następujący diagram alternatywy: a w kodzie programu instrukcja wyboru jednej z możliwości B1 lub B2 … lub Bn

4. Produkcji postaci A  B1 B2 … Bn odpowiada następujący diagram ciągu symboli:

a w kodzie programu instrukcja złożona składająca się z ciągu instrukcji B1, B2, … , Bn 5. Produkcji postaci A  BA |  odpowiada następujący diagram: a w kodzie programu pętla sprzężenia zwrotnego

-3-

Przykład Należy skonstruować diagram składni dla języka opisanego następującą GBK: G = ({A,B,C},{x,y,+,(,)},P,A) P:

A x |y A  (B ) B  AC C   | +AC

L(G) = {x,y,(x),(x+x),(x+y),((y+y)),((x)+x),((x)+(x)), …} Diagramy składni: A:

B:

C:

Powyższe diagramy łączymy w jeden A:

Reguły konstrukcji kodu programu w języku C na podstawie diagramów składni 1. Symbol terminalny: zastępujemy instrukcją:

if (ch==’a’) ch=getchar(); else discard();

2. Zmienną: zastępujemy wywołaniem funkcji:

funkcja_A();

3. Diagram alternatywy:

-4-

zastępujemy instrukcjami warunkowymi:

if (ch==’p1’) instrukcja(B1); else if (ch==’p2’) instrukcja(B2);

… else if (ch==’pn’) instrukcja(Bn); else discard();

lub równoważną instrukcją wyboru: switch(ch) { case ’p1’: instrukcja(B1); break; case ’p2’: instrukcja(B2); break;

… case ’pn’: instrukcja(Bn); break; default : discard(); }

gdzie pi jest p (Bi), a instrukcja(Bi) jest instrukcją otrzymaną z diagramu Bi

p (Bi) oznacza pierwszy symbol napotkany przy wejściu do diagramu Bi 4. Diagram ciągu symboli: zastępujemy instrukcją złożoną:

{ instrukcja(B1); instrukcja(B2);

… instrukcja(Bn); }

5. Diagram pętli:

zastępujemy instrukcją pętli

while (ch==’p’) instrukcja(B);

gdzie pi jest p (Bi), a instrukcja(Bi) jest instrukcją otrzymaną z diagramu Bi 6. Analizę rozpoczynamy od przeczytania pierwszego symbolu w łańcuchu wejściowym. Przykład Dla diagramu składni otrzymanego w poprzednim przykładzie:

-5-

kod programu w języku C wykonujący analizę składniową jest następujący: char ch; void gram_A() { if (ch==’x’) ch=getchar(); else if (ch==’y’) ch=getchar(); else if (ch==’(’) { ch=getchar(); gram_A(); while (ch==’+’) { ch=getchar(); gram_A(); } if (ch==’)’) ch=getchar(); else discard(); } else discard(); } void discard() { puts(“błędne słowo”); getch(); exit(0); } void main() { ch=getchar(); prog_A(); if (ch==’\0’); //czy koniec tekstu? puts(„poprawne słowo”) else discard(); getch(); }

-6-...