Jezyki bezkontekstowe PDF

Preview

Summary

Download Jezyki bezkontekstowe PDF

Description

TEORETYCZNE PODSTAWY INFORMATYKI

Języki bezkontekstowe, gramatyki bezkontekstowe, rekurencyjny opis wzorców, automaty ze stosem

Podstawowe pojęcia teorii języków Alfabet – dowolny skończony, niepusty zbiór symboli. Alfabetem nie może być zbiór pusty, ani zbiór nieskończony (np. zbiór liczb całkowitych) Język – dowolny podzbiór zbioru słów (może być nieskończony) nad pewnym alfabetem Językiem może być np.: zbiór wszystkich haseł w encyklopedii, zbiór wszystkich liczb pierwszych, zbiór nazw wszystkich jezior, zbiór wszystkich programów w języku C zapisujących do pliku, zbiór pusty. Językiem jest każdy zbiór, którego każdy element można opisać skończoną liczbą symboli z zastosowanego alfabetu. Język naturalny – język stosowany przez ludzi do komunikacji interpersonalnej. Język formalny – określony ścisłymi regułami zbiór słów, podawany na ogół z regułami ich interpretowania. Gramatyka formalna – sposób opisu języka formalnego Przy opisie języka poprzez gramatykę korzysta się z czterech rodzajów symboli:    

symboli terminalnych – symboli z alfabetu używanych w danym języku symboli nieterminalnych – symboli ze skończonego zbioru symboli pomocniczych symbolu początkowego – jeden symbol wybrany z symboli nieterminalnych metasymbolu () – oddziela definiowaną kategorię syntaktyczną od opisu sposobu jej utworzenia przez ciąg znaków

Korzystając z powyższych symboli konstruuje się reguły przepisywania (produkcje), które składają się z części nagłówkowej, metasymbolu „” oraz części zasadniczej. Reguły wiążące ze sobą zmienne i ciągi symboli nazywane są produkcjami. Ciągi symboli wykorzystywane w produkcjach konstruowane są z symboli terminalnych i nieterminalnych.

Gramatyki bezkontekstowe (GBK), ang. Context Free Grammars (CFG) Języki bezkontekstowe (JBK), ang. Context Free Languages (CFL) Gramatyka bezkontekstowa – skończony zbiór zmiennych (kategorii syntaktycznych), z których każda reprezentuje pewien język. Języki opisywane przez gramatyki bezkontekstowe nazywamy językami bezkontekstowymi. Opisuje się je z zastosowaniem rekurencji. Gramatyki te odgrywają kluczową rolę w technice kompilacji. Języki bezkontekstowe – szersza niż języki regularne klasa języków. Języki te mają rekurencyjną notację w postaci gramatyk bezkontekstowych.

Formalna definicja gramatyki bezkontekstowej Gramatyka bezkontekstowa jest uporządkowaną czwórką (V,T,P,S) gdzie:

V

jest skończonym zbiorem symboli nieterminalnych (zmiennych, nieterminali, kategorii syntaktycznych) dobieranych ze zbioru będącego alfabetem pomocniczym. T jest skończonym zbiorem symboli terminalnych (symboli końcowych, terminali) dobieranych z alfabetu końcowego, używanego w danym języku P jest skończonym zbiorem produkcji (reguł przepisywania) tworzących rekurencyjną definicję języka S jest symbolem początkowym (głową języka) – jednym z symboli nieterminalnych, od którego rozpoczyna się definicja języka T =V jest słownikiem czyli zbiorem będącym sumą teoriomnogościową alfabetu pomocniczego i alfabetu końcowego

Produkcje gramatyk bezkontekstowych mają postaci: gdzie:

A 



A 

jest symbolem nieterminalnym (zmienną, głową produkcji), AV jest metasymbolem produkcji oddzielającym definiowaną kategorię syntaktyczną od definicji sposobu jej utworzenia przez ciąg symboli jest ciągiem symboli nieterminalnych i terminalnych (ciałem produkcji),  =* (| |≥0)

Podany powyżej sposób notacji GBK z podanymi poniżej modyfikacjami nazywany jest notacją Backusa-Naura (ang. BNF, Backus-Naur Form). Zamiast metasymbolu  używamy ::=, natomiast zmienne zamiast literami (np. A, B) opisujemy słowami ujętymi w nawiasy trójkątne (np. liczba, cyfra). Język bezkontekstowy (JBK) to zbiór zawierający wszystkie słowa poprawne w sensie gramatyki G, czyli wyprowadzone z symbolu początkowego S z wykorzystaniem dostępnych w gramatyce produkcji P. Definiujemy symbol relacyjny „” opisujący rozwinięcie słowa z wykorzystaniem jednej z produkcji gramatyki G. Jeżeli ,=* oraz istnieje produkcja A to możemy zapisać: A  



Definiujemy także symbol relacyjny „  ”opisujący wielokrotne rozwinięcie słowa z wykorzystaniem wielu produkcji gramatyki G. 

   oznacza, że istnieje ciąg rozwinięć słowa : =1  2  3  …  i  …  n-1  n=

dla i=1,2, … ,n

Przykłady a) Gramatyka G = (V,T,P,S) = ({a,b,c},{0,1},P,a) P: a  bc a  cb b  0b0 c  1c1 b0 c1 Wyprowadzenie słowa „11111000” w tej gramatyce jest następujące: a  cb  1c1b  11c11b  11111b  111110b0  11111000 Przy wyprowadzaniu korzystamy z następujących produkcji: a  cb, c  1c1, c  1c1, c  1, b  0b0, b  0 b) Jaki język realizuje poniższa gramatyka bezkontekstowa? G = ({S},{a,b},P,S) P: S  aSb S  ab L(G) = anbn, n  1

ciąg n symboli a po których jest n symboli b

c) Przykładowa gramatyka prostych wyrażeń arytmetycznych G = ({w},{x,y,z,+,–,*,/,(,)},P,w) P: w  x | y | z w  (w) ww+w ww–w ww*w ww/w Wyprowadzenie słowa „(x+y–z)/(x*z)” w tej gramatyce jest następujące: w  w/w  (w)/w  (w+w)/w  (w+w–w)/w  (x+w–w)/w  (x+y–w)/w  (x+y–z)/w  (x+y–z)/(w)  (x+y–z)/(w*w)  (x+y–z)/(x*w)  (x+y–z)/(x*z) Przy wyprowadzaniu korzystamy z następujących produkcji: w  w / w, w  (w), w  w + w, w  w – w, w  x, w  y, w  z, w  (w), w  w * w, w  x, w  z

d) Jaki język realizuje gramatyka? E – element listy G = ({L,D,E},{l,”,”,(,)},P,L) P: L  (ED L – lista D  ,ED D – kontynuacja lub zakończenie listy (kolejny element listy lub nawias D) zamykający listę) EL E – element listy El Gramatyka definiuje niepuste zagnieżdżone listy. Elementy listy są ujęte w nawiasy i oddzielone przecinkami. Elementem listy może być lista. Przykładowe słowa: (l), (l,l,l,l), (l,l,(l,l),l), ((l,l,(l,l,l,l)),(l,l)) e) Jaki język realizuje poniższa gramatyka bezkontekstowa? G = ({S,A,B},{a,b},P,S) P: S  aB S  bA

Aa A  aS A  bAA

Bb B  bS B  aBB

ciąg symboli a i b, w którym ilość symboli a i b jest taka sama

Wykażemy że słowa języka składają się z takiej samej ilości symboli a i b, przy czym nie wykazujemy w ten sposób, że gramatyka generuje wszystkie możliwe słowa składające się z takiej samej ilości symboli. Załóżmy, że w poniższych produkcjach: S  w1 A  w2 B  w3

gdy w1 zawiera tyle samo symboli a co symboli b (la=lb) gdy w2 zawiera o jeden symbol a więcej niż ilość symboli b (la=lb+1) gdy w3 zawiera o jeden symbol b więcej niż ilość symboli a (la=lb-1)

Indukcja sprawdzamy dla ciągu o długości l=1: Aa prawda (la=1, lb=0) Bb prawda (la=0, lb=1) sprawdzamy dla ciągu o długości l=n: S(l=n,la=lb)  aB(l=n-1,la+1=lb) B(l=n,la+1=lb)  bS(l=n-1,la=lb) lub B(l=n=m+k+1,la+1=lb)  aB(l=m,la+1=lb)B(l=k,la+1=lb) analogicznie dla produkcji: S(l=n,la=lb)  bA(l=n-1,la=lb+1) A(l=n,la=lb+1)  aS(l=n-1,la=lb) lub A(l=n=m+k+1,la=lb+1)  bA (l=m,la=lb+1)A(l=k,la=lb+1)

Przykład zastosowania GBK do opisu języków naturalnych Konstrukcja zdań w języku polskim z wykorzystaniem GBK zdanie  grupa podmiotu grupa orzeczenia. grupa podmiotu  podmiot | przydawka grupa podmiotu podmiot  rzeczownik | rzeczownik zdanie przydawkowe, zdanie przydawkowe  , który grupa orzeczenia grupa orzeczenia  orzeczenie | okolicznik orzeczenie orzeczenie  czasownik nieprzechodni | czasownik przechodni dopełnienie dopełnienie  rzeczownik | rzeczownika | rzeczownik zdanie przydawkowe | rzeczownika zdanie przydawkowe dopełnienie  przydawkaego dopełnienie rzeczownik  kierowca | Piotr | kot | student | dom przydawka  lekki | krótki | zdrów | sam | niczyj czasownik nieprzechodni  wykłada | śpi | śpiewa | biegnie | gryzie czasownik przechodni  je | mówi do | sprzedaje | popiera okolicznik  chwilowo | na razie | dzisiaj | z pewnych względów Przykładowe zdanie:

Niczyj kot, który chwilowo mówi do Piotra z pewnych względów śpi

Definicja języka definiowanego przez GBK – języka bezkontekstowego (JBK) Jeżeli mamy GBK:

G = (V,T,P,S)

to język tej gramatyki oznaczamy przez L(G) i definiujemy następująco: 

* L(G) = {w; S  w; w=T }

JBK jest zbiorem łańcuchów złożonych z symboli terminalnych, które mają wyprowadzenia z symbolu początkowego GBK. Forma zdaniowa Wyprowadzenie z symbolu początkowego łańcucha składającego się z symboli terminalnych i nieterminalnych lub tylko nieterminalnych to forma zdaniowa. 

 jest formą zdaniową jeżeli S  ;

 = * = (VT) * lub  = V*

Wyprowadzenie lewo- i prawostronne W celu ograniczenia liczby wyborów produkcji jakie mamy do wyboru przy rozwijaniu form zdaniowych stosuje się pewne ograniczenie. Polega ono na tym, iż w każdym rozwinięciu formy zdaniowej wybieramy dla rozwinięcia lewostronnego tylko pierwszą zmienną z lewej, lub pierwszą z prawej dla rozwinięcia prawostronnego. Mówimy wtedy o rozwinięciu lewo- bądź prawostronnym i stosujemy oznaczenia: 



, , ,  l

l

p

p

Przykład Wyprowadzenie lewostronne słowa x*(y+z)+y dla gramatyki: G = ({w},{x,y,z,+,–,*,/,(,)},P,w) P: w  x | y | z w  (w) ww+w|w–w ww*w|w/w w  w + w  w * w + w  x * w + w  x * (w) + w  x * (w + w) + w  l

l

l

l

l

l

x * (y + w) + w  x * (y + z) + w  x * (y + z) + y l

l

Lewo- i prawostronna forma zdaniowa 



 jest lewostronną (prawostronną) formą zdaniową jeżeli S   (S  ); l

*

p

Drzewa wyprowadzenia (wywodu, rozkładu, rozbioru, analizy składniowej) Drzewa wyprowadzenia są użytecznymi sposobami reprezentacji GBK. Stosuje się je w kompilatorach języków programowania. Wierzchołki wewnętrzne drzewa rozbioru etykietuje się symbolami nieterminalnymi, liście drzewa – symbolami terminalnymi lub symbolem . Terminologia drzew korzeń – nie ma rodzica

wierzchołek wewnętrzny – ma wierzchołki potomne relacja rodzic-dziecko liść – nie ma wierzchołków potomnych

Formalna definicja sposobu konstrukcji drzewa rozbioru D dla gramatyki G = (V, T, P, S)     

Każdy wierzchołek drzewa D ma etykietę będącą symbolem ze zbioru V lub T, ewentualnie jest symbolem pustym  Etykietą korzenia drzewa D jest symbol początkowy S Wierzchołki wewnętrzne drzewa D etykietowane są symbolami nieterminalnymi V Liście etykietowane są symbolami terminalnymi T lub symbolem pustym . Jeżeli dany wierzchołek drzewa D ma etykietę , to wierzchołek ten jest liściem oraz jedynym potomkiem swojego rodzica Jeżeli dany wierzchołek drzewa D ma etykietę A, a jego wierzchołki potomne uszeregowane od lewego do prawego etykiety a1,a2, ... ,an to GBK musi posiadać produkcję P: A  a1a2 ... an Jeżeli będziemy przeglądać w głąb drzewo wyprowadzenia metodą preorder i odczytywać będziemy tylko etykiety liści to otrzymamy słowo nazywane plonem (wynikiem) drzewa wyprowadzenia.

Przykład 1 Dla danej gramatyki G=({S,A},{a,b},P,S) P: S  aAS | a A  SbA | SS | ba drzewo wyprowadzenia utworzone dla słowa (plonu drzewa) aabbaa wygląda następująco:

S  aAS  aSbAS  aabAS  aabbaS  aabbaa

Przykład 2 Dla gramatyki G=({w},{x,y,z,+, –,*,/,(,)},P,w) P: w  x | y | z w  (w) ww+w|w–w ww*w|w/w drzewo wyprowadzenia dla słowa (x+y) * z wygląda następująco:

Wieloznaczność języków i gramatyk Rozważmy gramatykę: G = ({w},{a,b,c,d,+,– , *,/,(,)},P,w) P: w  a | b | c | d ww+w|w–w ww*w|w/w w  (w) Słowo (a+b*c)*d ma w tej gramatyce dwa wyprowadzenia lewostronne: (1)

w  w * w  (w) * w  (w + w) * w  (a + w) * w  (a + w * w) * w  l

l

l

l

l

l

(a + b * w) * w  (a + b * c) * w  (a + b * c) * d l

(2)

l

w  w * w  (w) * w  (w * w) * w  (w + w * w) * w  (a + w * w) * w  l

l

l

l

l

l

(a + b * w) * w  (a + b * c) * w  (a + b * c) * d l

l

Odpowiadają im dwa różne drzewa wyprowadzenia o tym samym wynikowym słowie.

Najpierw mnożymy, potem dodajemy

Najpierw dodajemy, potem mnożymy

Def:

Wieloznaczność GBK Gramatyka bezkontekstowa jest wieloznaczna (niejednoznaczna), jeżeli istnieje co najmniej jedno słowo tej gramatyki, mające co najmniej dwa różne drzewa wyprowadzenia. Dlatego powyższa gramatyka jest niejednoznaczna. Nie nadaje się do zastosowania w kompilatorach języków bezkontekstowych. Aby ją zastosować w praktyce należy ją zmodyfikować tak, aby uwzględniała priorytety operacji arytmetycznych. Usuwanie wieloznaczności z gramatyk – nie ma ogólnej metody usuwania wieloznaczności gramatyk i ponadto nie dla każdej gramatyki wieloznaczność można usunąć. Aby opracować gramatykę jednoznaczną równoważną pod względem składni z podaną w powyższym przykładzie gramatyką wieloznaczną należy zdefiniować produkcje uwzględniające priorytety operacji arytmetycznych.

G = ({W,S,C,I},{a,b,c,d,+,– , *,/,(,)},P,W) P: W  W + W | W – W lub WW+S|W–S WS SS*S|S/S lub SS*C|S/C SC C  I | (W) Ia |b |c|d Jest to gramatyka jednoznaczna składająca się z czterech zmiennych nieterminalnych. Unikalne drzewo rozbioru utworzone dla tego samego słowa (a+b*c)*d wygląda następująco:

Def:

Ścisła wieloznaczność JBK Język bezkontekstowy L jest ściśle wieloznaczny gdy wszystkie jego gramatyki bezkontekstowe są wieloznaczne. Jeżeli choć jedna GBK tego języka jest jednoznaczna to język L jest językiem jednoznacznym. Rozważmy język: L = {an bn cm dm; n,mN}  {an bm cm dn; L jest JBK i ma GBK: G = ({S,A,B,C,D},{a,b,c,d},P,S) P: S  AB | C A  aAb | ab B  cBd | cd C  aCd | aDd D  bDc | bc

n,mN}

Słowo aabbccdd generowane przez tę gramatykę ma dwa wyprowadzenia lewostronne: (1)

S  AB  aAbB  aabbB  aabbcBd  aabbccdd

(2)

S  C  aCd  aaDdd  aabDcdd  aabbccdd

l l

l

l

l

l

l

l

l

l

którym odpowiadają dwa różne drzewa wyprowadzenia:

Jest to więc gramatyka wieloznaczna i ponadto można wykazać, że wszystkie możliwe gramatyki są także wieloznaczne. W związku z tym język ten jest ściśle wieloznaczny.

Postać normalna Chomsky’ego dla GBK Tw:

Dowolny język bezkontekstowy można generować gramatyką, która jest opisana tylko produkcjami typu: A  A 1A 2 Aa gdzie A, A1, A2 są symbolami nieterminalnymi, a a jest symbolem terminalnym Opis taki nazywamy postacią normalną Chomsky’ego (PNC). Zamiana GBK z postaci normalnej na postać Chomsky’ego (PNC) jest następująca: 1) Eliminujemy produkcje jednostkowe dla zmiennych, czyli produkcje o postaci: AB AV, BV w następujący sposób. Jeżeli: AB B  1 … B  n to A  1 … A  n

2) Produkcje jednostkowe dla symboli terminalnych, czyli produkcje o postaci: Aa AV, aT pozostawiamy bez zmian 3) W produkcjach o postaci: A  B 1B 2B 3 … B m AV, Bi, m2 (nie ma już produkcji jednostkowych) jeżeli Bi jest symbolem terminalnym (BiT) to wprowadzamy nową zmienną: Ci  Bi

BiT, CiV

4) Otrzymujemy produkcje: A  D1D2D3 … Dm AV, DiV tworzymy nowe zmienne: E1, E3, …, Em-2 i zastępujemy produkcje

A D1D2D3 … Dm

m-2 produkcjami A  D1E1 E1  D2E2 … Em-3  Dm-2Em-2 Em-2  Dm-1Dm Przykład Dana jest gramatyki bezkontekstowa G=({S,A,B},{a,b},P,S) P: S  Ab|Ba A  AbA|aS|aa B BaB|bS|bb Wyznaczymy dla niej PNC: C1  a S  AC2|BC1 C2  b A  AC2A|C1S|C1C1 B BC1B|C2S|C2C2 A  AE1 E1 C2A B  BE2 E2 C1B Otrzymujemy ostatecznie gramatykę w postaci PNC: S  AC2|BC1 A  AE1|C1S|C1C1 B  BE2|C2S|C2C2 E1 C2A E2 C1B C1 a C2 b

Postać normalna Greibach dla GBK Tw:

Dowolny język bezkontekstowy można generować gramatyką, która jest opisana tylko produkcjami typu: A  a gdzie A jest symbolem nieterminalnym, a symbolem terminalnym,  jest ciągiem symboli nieterminalnych o długości  0 Opis taki nazywamy postacią normalną Griebacha (PNG). Przykładowa gramatyka zapisana w postaci PNG S  aA1A2 A1  a A2  bA1SA3 A3  bA3 A4  aA1A2A3A4 ZY YNALE ŻNOŚCI SŁOWA D O J ĘZYK A GE SPRAWDZ DZANIE P RRZ GE NE ROW OWAN EGO PR PR ZEZ EZ G BK

K) Algo ) gor ytm tm C ock cke ’ a-Y -You ou nge gerra-Kasa mie ie go (CY CY K Algorytm wymaga gramatyki podanej w pos ostaci ci n ormalne nej C hom omsky’e go (P NC) C). Produkcje mają wtedy postać: P:

A  BC A a

(1) (2)

A,B,C V,

aT

Analizując PNC można zauważyć, że: słowo A o długości 1 (|A|=1) można wyprowadzić tylko z produkcji typu (2), A a

słowo A o długości |A|=2 można wyprowadzić tylko z produkcji typu (1) na jeden sposób, A B C

słowo A o długości |A|=3 można wyprowadzić tylko z produkcji typu (1) na dwa sposoby, A B

C C

B

słowo A o długości |A|=4 można wyprowadzić tylko z produkcji typu (1) na trzy sposoby. A C

B B

C B

itd ...

C

Słowo A o długości |A|=n składa się z dwóch podsłów B i C |A|=n,

|B|=1, 2, ... n-2, n-1;

|C|=n-1, n-2 ... 2, 1

czyli dla danego podziału k |B|=k,

|C|=n-k

Uwzględniając powyższe można utworzyć następującą tabelę wywodu słowa dla gramatyki G

nw1+ (n-1)w2+ (n-2)w3+ … +2wn-1+wn

wi= w1wi-1|w2wi-2| … |wi-2w2|wi-1w1

złożoność obliczeniowa algorytmu CYK wynosi O(n3) Przykład Dana jest gramatyka bezkontekstowa G=({W,A,B,C,P,G,N,Z},{x,y,z,+,*,(,)},P,W) P:

W  AW | BW | CZ A  WP B  WG C  NW Wx|y|z P+ G* N( Z)

Wykorzystując algorytm CYK sprawdzamy, czy słowo „(x+y)*z+y” należy do języka L(G)

Gramatyki bezkontekstowe a wyrażenia regularne Ponieważ JR  JBK, to każdy język możliwy do opisania za pomocą wyrażenia regularnego można również opisać za pomocą gramatyki bezkontekstowej, natomiast nie każdy język możliwy do opisania za pomocą GBK można opisać za pomocą WR. Przekształcanie wyrażeń regularnych na gramatyki bezkontekstowe suma WR

GBK

W1 | W2

W  W1 | W2

WR

GBK

złożenie W 1W 2 domknięcie Kleene’go

W  W 1W 2

WR

GBK

*

W  W 1W | 

W1 domknięcie dodatnie WR

W1

GBK

+

W  W 1W | W 1

Przykład Dla wyrażenia regularnego: a|b(c*|d+) wyznaczymy równoważną gramatykę WR

c* d+ (c*|d+) b(c*|d+) a|b(c*|d+)

GBK

    

A  cA| B  dB |d C  A|B D  bC S  a|D...