Lucrare de Curs LFPC

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 )*!+


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+


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 #


4/19

*.%onstruim cuvintele {1 =2 373# si arbori de derivare

'. abbbaaba

*. abaabbaa

+. abbbaba


5/19

,. aaabbbab

5. abbbabba


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% %


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/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


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


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


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


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 %


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'


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$:


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


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


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 Ø.


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


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

Lucrare de Curs LFPC

Documents

Transcript of Lucrare de Curs LFPC