8/17/2019 Lucrare de Curs LFPC
1/19
Ministerul Educaţiei al Republicii Moldova
Universitatea Tehnică a Moldovei
Lucrare de Curs
la Limbaje Formale i Proiectarea Compilatoarelor ș
A efectuat:
st. gr. SI!"! E.#e$erenco
A verificat:
lect. sup. %. &uca
'hi(inău )*!+
8/17/2019 Lucrare de Curs LFPC
2/19
Cuprins
Foaie de titlu.................................................................................1
Scopul si sarcina lucrarii................................................................3
Tema 1. Gramatici formale............................................................3
Tema 2. Automate finite................................................................6
Tema 3. Forma Normala Chomsky..............................................1
Tema !. Forma Normala Grei"ach...............................................13
Tema #. $atricia de %recedenta Simpla.......................................1!
Tema 6. &&'1(...............................................................................1)
Conclu*ie......................................................................................1+
8/17/2019 Lucrare de Curs LFPC
3/19
Tema: Gramatici formale
Sarcina : De creat o gramatica.
De creat 5 cuvinte (lung. min. find 7). Pentru fecare cuvint respectiv arbore
de derivare corenzator. De construit automat fnit pentru gramatica data.
G = {n! t! P! "#
n = {"! $! %! D!
t = {a! b#
P={ '. " a$
*. "a"
+."b
,.$aD
5.$b%
-.$b&
7.%a"
. %b%
/. %b"
'0. Da
''.DbD
'*. D
b%
'+.&a
',.&a&
'5.&bD #
8/17/2019 Lucrare de Curs LFPC
4/19
*.%onstruim cuvintele {1 =2 373# si arbori de derivare
'. abbbaaba
*. abaabbaa
+. abbbaba
8/17/2019 Lucrare de Curs LFPC
5/19
,. aaabbbab
5. abbbabba
8/17/2019 Lucrare de Curs LFPC
6/19
Te$a: , Auto$ate finite-
'. &ste dat automatul fnit "4=(! ∑! δ! 60! 4). eprezenta8i automatul sub
9orm de gra9.*. &ste sau nu automatul dat determinist;+. Dac automatul este nedeterminist! construi8i automatul fnit determinist
eciruri acceptate de
automat. ?ungimea >irurilor s nu fe mai mic dec@t nA*! unde n estenumrul de stri din .
7. Bcrie8i e1presia regulat ecir 1 scrie8i secven8a de confgura8ii pentru acceptarea>irului! adic (60! 1) |C (6i'! 1') |C (6i*! 1*) |C |C (69 ! ε)! unde 69 ∈ 4.
/. Petru toate cele 5 >iruri ob8inute construi8i aplic@nd lema de pomparedescompunerea 1=uvE.
Varianta 18
"4=(! ∑! δ! 60! 4)! = {60! 6'! 6* ! 6+#! ∑ = { a! b! c#! 4 = { 6+#.
δ (60! c) = {6'#
δ (6'! a) ={6*#
δ (6*! b) = {6*#
δ (6*! b) = {6+#δ (6*! a ) ={6*#
δ (6+! c) ={6+#
1. Reprezentaţi automatul sub formă de graf:
2. Este sau nu automatul dat determinist?Auto$atul dat este nedeter$inist deoarece din starea /) prin a se poate trece 0n 1 stări
diferite: /* /! i /1 deci ave$ș δ 2/)b3 45 /*/! / 16.
. !onstruiţi automatul "nit determinist ec#i$alent
a b c%& ' ' %1
%1 %2 ' '%2 ' %1%2% '%1%2% %2 %1%2% %
8/17/2019 Lucrare de Curs LFPC
7/19
% ' ' %
(.!onstruiţi gramatica regulată ec#i$alentă cu )*+
Am obţinut: AFD = ( Q', ∑ , ', q0 , F' ),, Q'={ [q0 , [q! , [ q" , [q! q" q# [q# $
F Q F ∩′=′
, F ′
= { [ q3 ] $
G={
1. q0-cq1
!. q1-aq!
3. q!-bq1q!q3
". q1q!q3-aq!
#. q1q!q3-bq1q!q3
$. q1q!q3-bq3
%. q3-cq3
8. q1q!q3-b
&. q3-c '
,. -n$entaţi un ir peste $ocabularul care nu $a fiacceptat de către )*+. )rătaţi acest lucru scriind
sec$enţa /sec$enţele0 de con"guraţii respecti$e.
'uvintul neacceptat de gra$atica dată este: caba
2/* 73 4 2/*caba3 892/!aba3 892/)ba3 892 /) a3! /) 4 ;⇒
nu este acceptat
. entru automatul finit )*+3/45 5 5 %&5 *0 construiţi , iruri acceptate de automat. 6ungimea irurilor să nu
"e mai mică dec7t n825 unde n este numărul de stări
din 4.
'. 1=cababbc*. 1=cabbbc+. 1=cababbbc,. 1=cabba
5. 1=cabbbbc
8/17/2019 Lucrare de Curs LFPC
8/19
9. entru "ecare ir scrieţi sec$enţa de con"guraţiipentru acceptarea irului5 adică /%&5 0 |; /%i15 10 |;
/%i25 20 |; < |; /%f 5 05 unde %f ∈ *.
!% 2/* 73 4 2/*cababbc3 892/!ababbc3 892/)babbc3 892 /! /) /1abbc3 892/)bbc3 892892 /!
/) /1 bc) 892/1c3! /1< ;⇒
acceptare
). 2/* 73 4 2/*cabbbc3 892/!abbbc3 892 /! /) /1 bbbc3 892 /! /) /1 bbc3 892/1 bc3 892/1c3
892/1 ε)! /1< ;⇒
acceptare
1. 2/* 73 4 2/* cababbbc3 892/! ababbbc3 892/) babbbc3 892 /! /) /1 abbbc3 892/) bbbc3 8
92 /! /) /1 bbc3 892 /! /) /1 bc3 892/1 c3 2/1ε)! /1< ;⇒
acceptare
". 2/* 73 4 2/* cabba3 892/! abba3 892/)bba3 892 /! /) /1ba3 892/)a3 892/)ε)! /)< ;⇒
acceptare
+. 2/* 73 4 2/* cabbbbc3 892/)abbbbc3 892 /! /) /1bbbbc3 892 /! /) /1bbbc3 892 /! /)
/1bbc3 892 /! /) /1bc3 892 /1c3 892/1ε3 /)< ;⇒
acceptare
=. etru toate cele , iruri obţinute construiţi aplic7ndlema de pompare descompunerea 3u$>.
1. z=uvw
!. |z| ≥ n, n=card(Q), |v|≥1
3. |uv| ≤ n
". uviw є L
'. 1=cababbc
u4ca
v4ba
=4bbc
*. 1=cabbbc
8/17/2019 Lucrare de Curs LFPC
9/19
u=cab
v=bE=bc+. 1=cababbbc
u=cav=baE=bbbc
,. 1=cabbc
u=cabv=bE=c
5. 1=cabbbbc
u=cabv=bE=bc
8/17/2019 Lucrare de Curs LFPC
10/19
Te$a: , ;or$a #or$ală 'ho$s>? 2;#'3-
Să se reducă la ;or$a #or$ală 'ho$s>? gra$atica independentă de conte7t
@ 4 2# T B S3 #4 5SAC '6 T 4 5ab6B4 5!. SD aC). SD 'A1. AD a". AD S+. AD bA'C
. CD bF. CD CSabaG. 'D H. 'D CA 6
ReJolvarea sarcinii:
!. &acă gra$atica independentă de conte7t conţine H producţii atunci ea poate fi transfor$ată 0ntrogra$atică echivalentă fără Hproducţii. Este dată @42#TBS3. 'onstrui$ @′42#TB′S3'onstrui$ # ε si genera$ gra$atica eli$inand producti de tipul dat : B′4BK5 A→ε 8 A→ε ∈B 6Acest pas se efectueaJa de atatea pina cand nu se vor intalni H productii in gra$atica respectiva.
# H4 5 ' 6
BL45 !. SD aC). SD 'A1. SD A". AD a+. AD S. AD bA'CF. AD bACG. CD b
. CD CSaba!*. 'D CA6
). Eli$ina$ redenu$irile:Se nu$e(te redenu$ire orice producţie de for$a ADC unde AC ∈ # &acă ave$ redenu$irileADC CD' 'D& &Dα la derivare ave$: ADCD'D&DN reiese A⇒ N.Atunci @′se construie(te 0n felul ur$ător: @′4 2# T B′S3!. Iniţial 0n B O :4 5toate producţiile din B care nu sunt redenu$iri6). ;ie ADN! ADN)... ADNn toate A producţii din B′ 1. Bentru toate si$bolurile C ∈ RA include$ 0n B′ producţiile CDN! CDN) ... CDNn C ∈ RAC P ⇒ A⇒ Ni Qn BO ave$ producţia CDNi
Mulţi$ea R A se construie(te 0n felul ur$ător:!. RA45A6 pentru toţi A∈ #). Bentru toate redenu$irile CD' pri$i$ R'4 R' ∪ RC
8/17/2019 Lucrare de Curs LFPC
11/19
1. Repetă$ pasul ) c0t ti$p apare ele$ente noi 0n RA A∈ #". STB
SD A R S45SA6 AD S R A 45A S 6
BLL4 5!. SD aC). SD 'A1. AD a". AD bA'C+. AD bAC. CD b
F. CD CSabaG. 'D CA. AD aC!*. AD 'A!!. SD a!). SD bA'C!1. SD bAC 6
3. ,liminam sim"olurile inaccesi"ile4ie "c mul8imea simbolurilor accesibile din a1iomF ini8ial "c={B#. *. Pentru toate simbolurile neterminale $ ∈ "c >i toate produc8iile $ → 1'1*
1n modifcm "c: = "c∪ {1'!1* ... 1n#. +. Dac la pasul * n "c au aprut elemente noi! salt la *. ,. Dac nu avem elemente noi! construim mul8imea ! = (H ∪I ) J "c Beelimin din P toate produc8iile care con8in cel pu8in un simbol inaccesibil (fedin partea st@ng! fe din partea dreapt).5. BIKP
AC - S/ A/ 0/ a/ "/ C
- deoarece nu aem sim"oluri inaccesi"ile
!.,liminam sim"olurile neproductieni8ial Pr=L.
*. a) Pentru toate produc8iile " → α! α∈IM modifcm Pr′ = Pr ∪{"#
b) Pentru toate produc8iile $ → N! N∈ (H ∪Pr)M Pr′ = Pr ∪{$#+. Dac au aprut modifcri n Pr salt la pasul *.,. %onstruim mul8imea H=HJPr5. BIKP.Kbserva8ie: Be elimin din P toate produc8iile care con8in cel pu8in un sOmbolinaccesibil (fe din partea stng! fe din partea dreapt)
%4-S/ A/ 0/ CN- deorece nu aem sim"oluri neproductie
8/17/2019 Lucrare de Curs LFPC
12/19
#. Forma Normala Chomsky
4ie gramatic independent de conte1t 9r εproduc8ii! redenumiri! simboluriinaccesibile >i simboluri neproductive! adic avem gramatica independent deconte1t proprie.
Ioate produc8iile au 9ormaa) "→ a
b) "→1'1*1nF unde n≥*! a∈I! 1i∈(I∪H)M
Pasul '. 4ie "→1'1*1n produc8ii de tipul b.
Pentru to8i 1i∈I introducem simboluri neterminale noi introducem simbolurineterminale noi i >i produc8ii noi i→1i substituim produc8ia "→1'1* 1i 1n cu
"→1'1* i 1n
Dup pasul ' toate produc8iile au 9orma a) "→ a b) "→ '*nF i∈H.Pasul *. Pentru orice produc8ie de tipul b) "→ '*n introducem neterminale noiQ.Produc8ia de tipul b) se nlocuie>te cu: "→ 'Q' Q'→ *Q* Q*→ +Q+ . Qn
*→ n'n
Pasul ' A Pasul * = G′ ?(G′) = ?(G)
4orma Hormala %
8/17/2019 Lucrare de Curs LFPC
13/19
*orma ormală Greibac# /*G0
Să se reducă la ;or$a #or$ală @reibach 2;#@3 gra$atica independentă de conte7t.@42# T B S3 #45S A C '6 T 45a b6B45 !. S D C'). ' D aA1. ' D b". C D SC
+. C D a. A D C' 6.
&eoarea sarcini *
!% Deoarece iniSial nu avem recursie st@nga!trecem la pasul urmtor.
Be substituie neterminalele din prima poziSie cu producSiile respective.B45 !. S D SC'). S D a'1. ' D aA". ' D b+. C D C'C
. C D aF. A D SC'G. A Da'6.
Kbservm c n producSii apare recursie st@nga Ti repetm pasul '. &liminm recursia st@nga prin metoda a *a:B45!.D C'). S D a'1. D U
". ' D aA+. ' D b. D 'CF.CD aV. D U .A DSC'!*.A Da' 6"ducem la 4orma Hormal Greibac< (4HG):
Gramatica independent de conte1t G este n 4HG !dac toate producSiile au
9orma "WaX ! a∈
I ! X∈
HM.4HG:P={ !. D a'). S D a'
8/17/2019 Lucrare de Curs LFPC
14/19
1. D U ". ' DaA+. ' D b. D bCF.C DaG.D U
. A D a'C'!*.A D a' 6+ramatici de precedenta simpa%
Multi$ile BRIMU% 2A3 si U%TIMU% 2A3.
BRIMU% 2A3 4 578A 7N6
U%TIMU% 2A3 4 5?8A ?6
Construirea multimii P!"#L$
Pasul 1%
Bentru toate productiile A 7N
N V 2 # U T3P
BRIM 2A3 4 578A 7N6
Pasul &%
Bentru toate $ulti$ile BRIM 2A3 daca C V BRIM 2A3 C V # atunci $odifica$:
BRIM 2A3 4 BRIM 2A3 U BRIM 2A3
A CN
Pasul '%
Repeta$ Basul ). cit ti$p apar $odificari.
Pasul %
STB.Construirea multimii #L!" (*)$
Pasul 1%
Bentru toate productiile A ?
V 2 # U T3P
U%TIM 2A3 4 5?8A ?6
Pasul &%
Bentru toate $ulti$ile U%TIM 2A3 daca C V U%TIM 2A3 C V # atunci $odifica$:
8/17/2019 Lucrare de Curs LFPC
15/19
U%TIM 2A3 4 U%TIM 2A3 U U%TIM 2A3
A Y C
Pasul '%
Repeta$ Basul ). cit ti$p apar $odificari.
Pasul %
STB.
Construirea relatiilor de +recedenta sim+la$
Intre 7! si 7) ave$ relatia 7! 4 7) daca e7ista productia A N 7! 7)
N W siruri arbitrare
7! si 7) 2ϵ # U T3
Intre 7! si 7) ave$ relatia 7! X 7) daca e7ista productia A N 7! C
A C ϵ # 7! 2ϵ # U T3
N W siruri arbitrare
7) 4 BRIM 2C3
Intre 7! si 7) ave$ relatia 7! Y 7) daca:
a3 e7ista productia A
N ' 7) ' ϵ # 7) ϵ T
7! 4 U%TIM 2'3
b3 e7ista productia A N ' C
' C ϵ # 7! 4 U%TIM 2'37) 4 BRIM 2C3 Z T.
[ X 7! 7! BRIM 2S3ϵ[ Y 7) 7) U%TIM 2S3ϵ[ $ar>er pentru inceputul si sfirsitul sirului.
-em+lu$
A&-A./A !
Este dată gra$atica independentă de conte7t
@42# T B S3 # 45S A C ' &6 T 45a b c d e6B45 !. S D A). A D C1. A D C e A ". C D a b & +. & D ' d
8/17/2019 Lucrare de Curs LFPC
16/19
. ' D cF. ' D ' c 6
Să se construiască $atricea relaţiilor de precedenţă (i să se analiJeJe (irul abcdeabcccd
BRIM 2 3 U%TIM 23
S A C a A C & d
A C a C A & d
C a & d
& ' c d
' ' c c
7! 4 7)
C 4 ee 4 Aa 4 b
b 4 &c 4 d'4c
7! X 7)
e X BRIM 2A3 b X BRIM 2&3
e X 5 C a 6 b X 5 ' c 6
7! Y 7)
U%TIM 2C3 Y eU%TIM 2'3 YcU%TIM 2'3 Yd5 & d 6 Y e
5 c6 Y c5 c6 Y d
8/17/2019 Lucrare de Curs LFPC
17/19
S A C & ' c a b d e [SA YC 4 Y& Y Y' 4 4
c Y Ya 4
b 4 X Xd Y Ye 4 X X[ X X Xabcdeabcccd ( )a=b)c*e)a=b)ccc*(( )a=b)C= *e)a=b)cc*(
( )a=b=+e)a=b)cc*(( ),=e)a=b)cc*(
( ),=e)a=b)C=c*(
( ),=e)a=b=+(( ),=e),(
( ),=e=(( )(
( ) (
Sirul este acceptat\
LL(!)%
@ra$atica independenta de conte7t este %%2!3 daca din e7istenta derivatelor !3 S 4YP 7AN! 4YP 7!N! 4YP 7 ?!
)3 S 4YP CN) 4YP 7)N) 4YP 7 ?)si egalitatea A 4 C ! 4 )
.e/% Se nu$este si$boluri directoare de productie A Y N ele$entele $ulti$ii.
¿ PRIM (α )
¿U URM ( A ) , α =¿∗ε (α =ε )
¿(¿ PRIM (α )−¿caz contrar¿
SD ( A → α )=¿
eorema% @ra$atica @ este %%2!3 atunci cind pentru toate si$boluri neter$inale A ϵ # si toateAproductii.A Y N! AY N) ] A Y Nn.S& 2A Y Ni3 Z S& 2A Y N ^3 4 Ø.
8/17/2019 Lucrare de Curs LFPC
18/19
Bentru toti i _ ^.
""HI" ' ??(') &ste dat gramatica independent de conte1t G=(H! I! P! B!)! H ={B! "! Z! &! V! #! I ={a!b!c!d#!P={ '. B W d Z*. Z W & V+. V W U,. V W c Z5. & W b "-. " W a 7. W U. W " #.
B se construiasc tabelul de analiz ??(') >i s se analizeze >irul dbacbaaa
S&'. B W d Z BRIM2d345d6*. Z W & V BRIM2E345b6+. V W U URM234 5 6,. V W c Z BRIM2c345e65. & W b " BRIM2b3U URM2E345bc 6-. " W a BRIM2a345a67. W U URM23456. W " BRIM2A345a6
BRIM23 URM23S d [
` E bE b c c U c U a "A a
a b c d [a ˅
b ˅c ˅d ˅[S !` )E + + " GA
2S [ dbacbaaa [3 8 2!3 2d` [ dbacbaa[3 8 2 3 2 ̀ [˅ bacbaa [38 2)3 2E [ bacbaa[3 8 2+3 2b A [ bacbaa [3 8 2 3 2 [˅ acbaa [3 8 23 2a [ acbaa [38 2v3 2 [ cbaa [3 8 2"3 2 c ` [ cbaa [38 2v3 2 ` [ baa [3 8 2)3 2 E [ baa [3 8 2+3
8/17/2019 Lucrare de Curs LFPC
19/19
2b A [ baa [3 8 2v3 2 A [ aa [3 8 23 2 a U [ aa [3 8 2v3 2 [ a [38 2G3 2 A [ a [3 8 23 2 a [ a [3 8 2v3 2 [3Sirul nu este acceptat.
Concuie*
Qn acestă lucrare de curs a$ generaliJat cuno tin ele ob inute la curs?l %i$ba^e for$ale siș ț ț
proiectarea co$pilatoarelor. A$ studiat progra$ul ;%AB si utiliJat pentru constructiaauto$atelor finite si arborilor de derivare. A$ studiat te$ele e7puse i a$ e7ersat.ș
@ibliogra"e:
%onspect la cursul ?4P%! ?.Duca! [I\ *0'5