Strona główna

Wykład 9 Języki formalne i gramatyki Podstawowe pojęcia


Pobieranie 105.63 Kb.
Data18.06.2016
Rozmiar105.63 Kb.
Wykład 9

Języki formalne i gramatyki

Podstawowe pojęcia

  1. Alfabetem nazywamy skończony zbiór symboli. Oznaczamy go jako V.

np. V={a, b, ..., z}

  1. Łańcuchem nad alfabetem V o długości m0 jest skończonym ciągiem m elementów zbioru V.

  2. Łańcuch o długości m=0 jest nazwany łańcuchem pustym i oznaczamy go: .

  3. Łańcuch o długości m zapisujemy w postaci: x1 x2...xm.

  4. Zbiór wszystkich łańcuchów nad alfabetem V oznaczamy V*. Elementy tego zbioru oznaczamy jako , , , ....

  5. Zbiór łańcuchów o długości m wygenerowanych nad danym alfabetem V oznaczamy jako

Sm(V)= Vm, gdzie Vm ={x1 x2...xm: xiV  im}

np. V={a, b},

m=2,

S2(V)={aa, ab, ba, bb}



  1. Zbiór wszystkich łańcuchów V* nad alfabetem V o długościach iN jest więc sumą wszystkich zbiorów Vi i oznaczmy go jako:

V*= iN Si(V).

np. V={a, b},

N=2,

S0(V)={},



S1(V)={a, b},

S2(V)={aa, ab, ba, bb}

V*={}{a, b}{aa, ab, ba, bb}={, a, b, aa, ab, ba, bb}


  1. Konkatenacją słów  i  nad alfabetem V zapisujemy jako . lub krótko , które jest słowem powstałym przez dopisanie do słowa  słowa .

  2. Slowo  jest podsłowem słowa , jeśli istnieją słowa (możliwe puste)  i  takie, że  =. Jeśli  i  są niepustymi słowami, wówczas  jest właściwym podsłowem.

np.  = aabb

ma 9 podsłów: , a, b, ab, aa, bb, abb, aab, aabb.



  1. Algebrą słów nad alfabetem V nazywamy algebrę , gdzie

    1. V* jest nośnikiem algebry,

    2. . : V*V*V* jest konkatenacją,

    3. : V* jest słowem pustym (stałą algebry).

  2. Niech V jest alfabetem. Podzbiory zbioru V* są językami nad V, oznaczane jako L. Jeśli L, wtedy  jest zdaniem języka L i LV*.

  3. Gramatyką G języka L jest skończony system reguł wyznaczających język L.

Język L wyznaczony przez gramatykę G jest oznaczany jako L(G).

Jeśli L(G1)=L(G2) wówczas gramatyki G1 i G2 są identyczne, czyli G1=G2.



  1. Gramatykę bezkontekstową definiujemy jako czwórkę GBK = , gdzie:

  2. V jest alfabetem symboli terminalnych (symboli końcowych)

  3. V’ jest alfabetem symboli nieterminalnych (zmiennych)

  4. P jest skończonym zbiorem produkcji, gdzie produkcją pP jest odwzorowaniem pojedynczego symbolu nieterminalnego z V’ do ciągu symboli terminalnych i nieterminalnych ze zbioru VV’, czyli

p: V’ (VV’)* jest relacją pV(VV’)*

  1. S – symbol początkowy, wyróżniony z symboli nieterminalnych, SV’.

Dwa łańcuchy  i  są związane relacją G dokładnie wtedy, gdy drugi z nich można otrzymać z pierwszego przez zastosowanie jakiejś produkcji.



  1. Proces wyprowadzania słowa:

Niech:

    1. , , , ..., ,  są słowami z (VV’)*,

    2. liczba słów jest  1 oraz

    3. G , G , ..., G .

Wtedy piszemy *G  i mówimy, że  jest wyprowadzalny z  w gramatyce G.

  1. Język L generowany przez gramatykę G jest zdefiniowany jako

L(G) = {: V* i S *G }.

Łańcuch  należy do języka L(G), jeżeli:



  • składa się wyłącznie z symboli terminalnych i

  • jest wyprowadzalny z symbolu początkowego S.

Łańcuch  złożony z symboli terminalnych i nieterminalnych jest nazywany formą zdaniową, jeśli S *G .

  1. Język L(G) jest nazywany bezkontekstowym (JBK), jeśli jest generowany przez gramatykę G = GBK.

Przykład 9.1

Niech:


V={a, comfortable, is, near, shoes, sometimes, table, the, wear, window, women},

V’= {S, A, AN, B, C, CN, D, N},

G=,

P:   SCN.AN, CNC.N, CNN, CNA.CN, ANA.AN, AND.CN, NB.N, Nwindow, Nwomen, Nshoes, Ntable, Anear, Asometimes, Bcomfortable, CA, Cthe, Dis, Dwear



np. S CN.AN

C.N.AN


the.N.AN

the.table.AN

the.table.D.CN

the.table.is.CN

the.table.is.A.CN

the.table.is.near.CN

the.table.is.near.C.N

the.table.is.near.the.N

the.table.is.near.the.window

lub S CN.AN

C.N.AN

C.N.D.CN



the.N.D.CN

the.table.D.CN

the.table.D.A.CN

the.table.D.A.C.N the.table.D.A.the.N

the.table.D.A.the.window

the.table.D.near.the.window

the.table.is.near.the.window

Uwaga: tylko przypadkowo to zdanie ma sens.

Inne zdanie języka L(G) na podstawie reguł produkcji P gramatyki G:

the.table.wear.near.near.a.window

S  CN.AN

 C.N.AN


 the.N.AN

 the.table.AN

 the.table.D.CN

 the.table.wear.CN

 the.table.wear.A.CN

 the.table.wear.near.CN

 the.table.wear.near.A.CN

 the.table.wear.near.near.CN

 the.table.wear.near.near.C.N

 the.table.wear.near.near.a.N

 the.table.wear.near.near.a.window


  1. Produkcje można zapisać w bardzo zwięzłej notacji BNF (Backus Normal Form), która pojedyncze produkcje zapisuje:

v::=v1v2 ...vn,

gdzie vV’,

v1v2 ...vn  (VV’)*.

W przypadku, gdy ta sama produkcja generuje różne słowa

v::=<>, v::=<>, ... v::=<>

wtedy stosuje się zapis w postaci

v::=<><>...<>,

gdzie , , ..., (VV’)*.

W przypadku zapisu ., mamy zapis

<><>.


  1. Drzewa wyprowadzenia

Drzewo wyprowadzenia D stanowi użyteczną formę reprezentowania produkcji gramatyki bezkontekstowej GBK= :

    1. każdy wierzchołek drzewa D ma etykietę, będącą symbolem ze zbioru VV’

    2. etykietą wierzchołka drzewa jest symbol S

    3. etykietami węzłów wewnętrznych drzewa (czyli węzłami-ojcami, które mają następców i nie są wierzchołkiem drzewa) są symbole należące do zbioru symboli nieterminalnych V

    4. jeżeli węzeł drzewa ma etykietę A ze zbioru V, a węzły wychodzące z tego węzła i uporządkowane od lewej do prawej mają odpowiednio etykiety B, C, …X, to A  B, C, …X musi być produkcją należącą do zbioru produkcji P

    5. każdy węzeł, który nie posiada następców i jest jedynym następcą swojego ojca, jest zwany liściem i posiada etykietę, która jest symbolem terminalnym, należącym do zbioru V’

    6. poddrzewem drzewa wyprowadzenia jest drzewo D’, złożone z dowolnie wybranego wierzchołka drzewa D wraz z jego z jego potomkami, krawędziami i etykietami.

Drzewo wyprowadzenia jest naturalnym opisem wyprowadzenia konkretnej formy zdaniowej gramatyki GBK, złożonej z etykiet, odczytanych od lewej do prawej.



Przykład 9.2

Z przykładu 9.1 mamy produkcje w notacji BNF:



::=

::= ||

::=
|

::= | window | women | shoes | table

::= near | sometimes

::=
comfortable

::= athe

::= is | wear
Istnieją 32 wyprowadzenia tego samego zdania z drzewa wyprowadzeń a) oraz 16 z drzewa b)



  • Pełny graf wyprowadzeń produkcji p ze zbioru P dla danej gramatyki GBK przedstawia graf, którego węzłami są:

  • spójniki & oznaczające, że krawędzie wychodzące oznaczają od lewej do prawej symbole jednego łańcucha z następników danej produkcji p, a krawędź wchodząca do węzła poprzednik tej produkcji p.

  • spójniki || oznaczające, że krawędzie wychodzące oznaczają od lewej do prawej alternatywne łańcuchy następników danej produkcji p, a krawędź wchodząca do węzła poprzednik tej produkcji p.

np. ::= |




Przykład 9.3

Pełne drzewo wyprowadzenia gramatyki z przykładu 9.1.






  • Wieloznaczne drzewo wyprowadzeń

::=
c | a

::=b | a

::=b | c



Dwa drzewa wyprowadzeń dotyczą tego samego zdania abc, czyli są drzewami wieloznacznymi.

Problem stwierdzania, czy dana gramatyka bezkontekstowa jest jednoznaczna, jest nieroztrzygalny.

Po zastosowaniu gramatyki nawiasowej, gdzie każdy następnik produkcji jest ujęty w nawiasy () (krawędzie wychodzące z każdego węzła od lewej do prawej), znika problem wieloznaczności drzewa wyprowadzenia. Otrzymujemy bowiem dwa różne zdania: (((a)b)c) oraz (a(b(c))).


  • Prefiksowa reprezentacja formuł

Dane jest wyrażenia arytmetyczne

a*b+c/d+e*f/g-h, ((a+b)/c-d)*e-h (1)

Obliczenia następują od lewej do prawej. Wprowadzając nawiasy (gramatyka nawiasowa) można określić kolejność wykonywania działań w wyrażeniach (1):

((((a*b)+(c/d))+((e*f)/g))-h), (((((a+b)/c)-d)*e)-h) (2)

Wyrażenie jest reprezentowane za pomocą drzewa wyprowadzenia, gdzie węzłami-ojcami są operatory, natomiast węzłami-liśćmi są argumenty.

Równoważny zapis wyrażeń arytmetycznych (1) w postaci prefiksowej są:

-++*ab/cd/*efgh, -*-/+abcdeh (3)

Drzewa wyprowadzenia wyrażeń (1) generują wyrażenia (3).



Algorytm obliczania wyrażeń arytmetycznych


  1. Przeczytaj sekwencję wejściową z lewa na prawo

  2. Umieść na stosach S1 pierwszą wartość argumentu i na S2 pierwszy operator

    1. kolejną zmienną umieść na stosie S1, jeśli koniec-przejdź do kroku 2.3

    2. kolejny operator

2.2.1.umieść na stosie S2, jeśli ma pierwszeństwo przed operatorem znajdującym się aktualnie na szczycie S2 i przejdź do 2.1, w przeciwnym wypadku przejdź do 2.2.2

2.2.2.zastosuj operator zdjęty ze stosu S2 na dwóch elementach zdjętych ze stosu S1 i wynik umieść na stosie S1, przejdź do kroku 2.2.1



    1. Po odczytaniu ostatniej zmiennej z sekwencji wejściowej

      1. jeśli stos S2 jest pusty, zakończ program

      2. w przeciwnym wypadku usuń operator ze szczytu stosu S2 i dwie zmienne ze szczytu S1, wykonaj działanie na nich i umieść wynik na szczycie S1 i powtórz krok 2.3.

Przykład 9.4

Obliczanie wyrażenia arytmetycznego

#ifndef _mstos

#define _mstos

#include

#include "strukt.h"

typedef struct Stack* PStack;
struct Stack

{Item data;

PStack next;

};
// stos - reprezentacja



inline int IS_EMPTY(PStack pstack);

inline PStack NEW();

PStack PUSH(PStack& start, Item item);

PStack POP(PStack& start);

Item TOP(PStack start);


//stos

void EMPTY_S(PStack & start);

int IS_EMPTY_S(PStack start);

int ADD_S(PStack &start, Item item);

int REMOVE_S(PStack & start);

int FRONT_S(PStack start,Item& item);
//funkcja pomocnicze

PStack NEW_ITEM(Item item);



#endif

#include

#include "mstos.h"
//funkcja pomocnicze
PStack NEW_ITEM(Item item)

{

PStack pstack;



pstack = new Stack;

if (!IS_EMPTY(pstack))

pstack->data=item;



return pstack;

}

//typ stos jako reprezentacja



inline int IS_EMPTY(PStack pstack)

{ return pstack==NULL;}


inline PStack NEW()

{ return NULL;}

PStack PUSH(PStack& start, Item item)

{PStack pstack;

pstack = NEW_ITEM(item);

if (IS_EMPTY(pstack))

return NULL;

pstack->next=start;

start= pstack;

return start; }
PStack POP(PStack& start)

{ PStack pop;

pop = start;

start = start->next;



delete pop;

return start; }
Item TOP(PStack start)

{ return start->data;}


// Stos

void EMPTY_S(PStack &pstack)

{pstack=NEW(); }


int IS_EMPTY_S(PStack pstack)

{ return IS_EMPTY(pstack);}


int ADD_S(PStack &start, Item item)

{ return !IS_EMPTY(PUSH(start, item)); }


int REMOVE_S(PStack & start)

{ if (IS_EMPTY(start)) return 0;

POP(start);

return 1;

}
int FRONT_S(PStack start,Item& item)

{ if (IS_EMPTY_S(start)) return 0;

item=TOP(start);



return 1; }

#include"mstos.h"

#include

#include

#include

const N=10;

char* lan="(((1+2)*(3+4))/(5-2))"; //bez spacji, brak kontroli liczby nawiasów

//char* lan="((1+2)*3+4)/5-2"; // zagnieżdżone wyrażenia w nawiasach

//char* lan="1+2*3+4/5-2"; // na początku wyrażenia

void arg(PStack& S1, PStack& S2, int&poz, char* lan);

void op(int k,PStack& S1, PStack& S2, int&poz, char* lan);

void oblicz(PStack& S1, PStack& S2);

void wyrazenie(PStack& S1, PStack& S2, Item c);

void operator_(PStack &S2,char*lan,int &poz);
void main()

{int poz=0;

PStack S1, S2;

EMPTY_S(S1); //stos S1 - argumentów

EMPTY_S(S2); //stos S2 - operatorów

//dokonaj analizy łańcucha i już oblicz wyrażenia od lewej strony o wyższym lub równym priorytecie

arg(S1,S2,poz,lan);

oblicz(S1,S2); //dokończ obliczenia po zakończeniu analizy łańcucha dla wyrażenia //zawierającego operatory na stosie S2 w kolejności wg ich priorytetów

printf("\n%s= %f",lan,S1->data.arg);} //wyświetlenie wyniku ze szczytu stosu S1


void op(int k, PStack& S1, PStack& S2, int&poz, char* lan)

{ int t=0; Item c;



if (lan[poz] == '\0' ) return; //koniec łańcucha

while (lan[poz] == ')' ) {poz++; t =1;} //nawiasy ‘)‘

switch (lan[poz])

{ case '*': case '/': case '+': case '-':



if(IS_EMPTY_S(S2)) //dodaj operator do pustego stosu

{operator_(S2, lan, poz); break;}



//oblicz wyrażenie, gdy na stosie S2 jest równorzędny operator

// lub nowy operator jest za nawiasem )*, ) /, ) +, ) -, czyli t==1

//,a jednocześnie nie rozpoczęto nowego wyrażenia ( czyli k==0

if (!k)

if (lan[poz] == '*' || lan[poz] == '/') //dla operatorów * , /

while (FRONT_S(S2, c) && (c.op == '*' || c.op == '/'|| t))

wyrazenie(S1, S2, c);



else while (FRONT_S(S2, c)) //dla operatorów +, -

wyrazenie(S1, S2, c);



//wstaw nowy operator, gdy ma wyższy priorytet niż operator na stosie S2

operator_(S2, lan, poz);



break;

} arg(S1, S2, poz, lan); }



void arg(PStack& S1, PStack& S2, int&poz, char* lan)

{ int k=0;



char p[N] = "";

Item a;


if(lan[poz] == '\0') return;

while(lan[poz] == '(' ) {poz++; k=1;}

if (isdigit(lan[poz]))

{while (isdigit(lan[poz]) || lan[poz] == '.') strncat(p, lan+poz++,1);

a.arg = atof(p);

ADD_S(S1, a); //dodano nowy argument do stosu S1

}

op(k, S1, S2, poz, lan);



}
void oblicz(PStack& S1, PStack& S2)

{ Item c;



//obliczanie wyrażenia aż do wyczerpania operatorów z S2

while(!IS_EMPTY_S(S2))

{FRONT_S(S2, c);



switch (c.op)

{ case '*': case '/': case '+': case '-':wyrazenie(S1, S2, c);

} } }
void wyrazenie(PStack& S1, PStack& S2, Item c)

//obliczanie wyrażenia: usuwanie dwóch argumentów ze stosu S1

//oraz operatora ze stosu S2, następnie wstawienie wyniku do stosu S1

{ Item a,b;



if (FRONT_S(S1, a))

{ REMOVE_S(S1);



if (FRONT_S(S1, b))

{REMOVE_S(S1);

REMOVE_S(S2);

switch(c.op)

{case '*': a.arg = a.arg * b.arg; break;



case '/': if (b.arg == 0) return;

a.arg = b.arg / a.arg; break;



case '+': a.arg = a.arg + b.arg; break;

case '-': a.arg = b.arg - a.arg; break;

}

ADD_S(S1, a);



} } }
void operator_(PStack &S2, char*lan, int &poz)

{ Item c; //dodawanie nowego operatora do stosu S2

c.op = lan[poz++];

ADD_S(S2, c); }



Przykład 9.5

Analiza leksykalna deklaracji dla języka C (na podstawie [13])
::= * |

::=|() | ()

| [opcjonalny_rozmiar]



::= | |
Przyjęto skróty:

::= * |

::= | () | () | [opcjonalny_rozmiar]

::= | |
(*t)[10] dla char(*t)[10] (*f)() dla char (*f)()



#include

#include

#include

#include

//spacja do nazwy predef. typu, dalej bez spacji, brak kontroli liczby nawiasów

const int N=3;

const int M=4;

char* lan= "float (*(*t())[])()";

char* typy[N] ={"char ", "int ", "float "};

char* info[M] ={ " wskaznik do ",

" funkcja zwracajaca",

" tablica",

" o elementach"};



char* wynik;

int ile;

int poz;
int dek(int&, char*&, int&, char*);

int bdek(int&, char*&, int&, char*);

int typ(char*, int&);

int Zmien(char*&, int, int&);

void Wstaw(char*, const char*, int);

int Dodaj(char*&, int , int& , char*);
void main()

{ int i= typ(lan, poz);



if (i == -1) return; // błąd typu danych

Dodaj(wynik, 1, ile, ””); //zainicjowanie łańcucha wynikowego



if (dek(poz, wynik, ile, lan)) //wynik analizy leksykalnej

printf("\n%s %s", wynik, typy[i]);



else printf("\nBledy"); //błąd pamięci

}
int typ(char* lan, int& poz) //funkcja pomocnicza rozpoznająca predef. typ danych

{ for (int i=0; i
if (strstr(lan, typy[i]) == lan)

{ poz=strlen(typy[i]);



return i;}

return -1; }
int Zmien(char*&wynik, int roz, int&ile)

{ char* pom=(char*) realloc(wynik, ile+roz);



if (pom)

{wynik=pom; ile+=roz; return 1;}



return 0; }

void Wstaw(char* wynik, const char*l, int s)

{ wynik[ile-s]='\0';

strncat(wynik, l, s);

}
int Dodaj(char*& wynik, int s, int& ile, char* l)

{ if (Zmien(wynik, s, ile))

{Wstaw(wynik, l, s); return 1;}



return 0;

}
int dek(int& poz, char*& wynik, int& ile, char* lan)



//funkcja obsługująca reguły produkcji deklaratora

{ int i=0;



while (lan[poz+i] == '*') i++;

poz += i;



int w = bdek(poz, wynik, ile, lan);

while (i-->0)

{if (!Dodaj(wynik, strlen(info[0]), ile, info[0]))



return 0;}

return w; }
int bdek(int& poz, char*&wynik, int& ile, char* lan)

//funkcja obsługująca reguły produkcji bezpośredniego deklaratora

{ int w =1;



if (lan[poz] == '(' ) //(deklarator)

{ poz++;


dek(poz, wynik, ile, lan); poz++;}

else

while(isalnum(lan[poz])) //nazwa

w = Dodaj(wynik, 1, ile, lan+poz++);



switch(lan[poz])

{

case '(': while(lan[poz] != ')') //funkcja

w = Dodaj(wynik, 1, ile, lan+poz++);

w = Dodaj(wynik, 1, ile, lan+poz++);

w = Dodaj(wynik, strlen(info[1]), ile, info[1]);

break;

case '[': w = Dodaj(wynik, strlen(info[2]), ile, info[2]); //tablica

while(lan[poz] != ']')

w=Dodaj(wynik, 1, ile, lan+poz++);

w = Dodaj(wynik, 1, ile, lan+poz++);

w = Dodaj(wynik, strlen(info[3]), ile, info[3]);



break;

}

return w;}



Zofia Kruczkiewicz, Języki programowania 1, Wykład 9




©snauka.pl 2016
wyślij wiadomość