7/23/2019 LFPC Lab1

1/4

Ministerul Educaiei al Republicii MoldovaUniversitatea Tehnic a Moldovei

RaportLucrare de laborator Nr.1la Limbaje formale i

proiectarea compilatoarelor

Tema: Gramatici ormale!arianta "#

$ eectuat: st. %r. T&'1#1(arp &on

$ veriicat: L. )ucaM. &acob

(hi*inu + ,"1- Sarcina lucrrii:

/entru %ramatica ormal G = (VN, VT,P, S)construii - *iruri0 careaparin limbaului L2G3 %enerat de aceast %ramatic. Lun%imea*irului trebuie s ie nu mai mic0 dec4t numrul de caractere dinalabet !N5,.

/entru iecare *ir s se construiasc arborii de derivare. )esenai automatul init echivalent acestei %ramatici. La ce clas al %ramaticilor dup (homs67 aparine %ramatica dat8

!N9;0 L

7/23/2019 LFPC Lab1

2/4

Efectuarea lucrrii: (onstruim - *iruri ce aparin limbaului L2G3 %enerat de aceast

%ramatic:13 ; '= dL '= >,3 ; '= a; '= adL '= adeL '= adee>?3 ; '= b; '= bc; '= bcdL '= bcdL '= bcd>#3 ; '= a; '= ab; '= abc; '= abcdL '= abcdeL '= abcdeL '= abcde >-3 ; '= c; '= cdL '= cdL '= cd >

Pentru fiecare ir construim arborii de derivare:1. ; @A d L @ e

,. ; @A a ; @A d L @A e L @ e

?. ; @A b ; @A c ; @A d L @A L @

#. ; @A a ; @A b ; @A c ; @A d L

@A e L @A

L

/\

f

-. ; @A c ; @A d L @A L @

7/23/2019 LFPC Lab1

3/4

Construim AF(automatul finit) echivalent acestei gramatici:

AF=(Q, , , q0, F), undeQ mulimea de stri

!"#a$ular %un#ia de tran&iie q0 starea iniial

F mulimea stril"r %inale

Al'"ritmul de #"nstruire AF

B 9 !NC0D< 9 ;0 L< 9 !T 9 a0b 0c0 d0 e0 0 < " 9 ; F 9 C0 D< /entru toate produciile deinim :

&niial toate mulimile 2$0 b3: 9 " ; a; ; b;

;

c; ; dL L eL L L LL L e L L

; d

1.; a;2;0 a3: 9 2;0 a3;< 9 F