Rapport du Projet de Compilation

Ce travail est élaboré par : Kamoun Sabrine & Dridi Maissa & BenYounes Maryem

🔎

On a opté cette grammaire G ci-dessous:

P → P S | ε
S → id = E ; | if ( C ) S else S
S → while ( C ) S
E → E + T | T
T → T * F | F
F → ( E ) | id | N
N → N D | D
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
DC → E R EQ
R → == | != | < | ≤ | > | ≥

1. Analyse Descendant LL(1):

1.1) Elimination de récursivité:

🔎

Grammaire non récursive G’:

P → P'
P' → S P' | ε
S → id = E ; | if ( C ) S else S
S → while ( C ) S
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id | N
N → D N'
N' → D N'| ε
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
DC → E R EQ
R → == | != | < | ≤ | > | ≥

1.2) Elimination de l’ambiguïté:

🔎

Même grammaire G’ (pas d’ambiguïté)

P → P'
P' → S P' | ε
S → id = E ; | if ( C ) S else S
S → while ( C ) S
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id | N
N → D N'
N' → D N' | ε
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
DC → E R E

R → == | != | < | ≤ | > | ≥

1.3) Premiers & Suivants:

1.3.1) Premiers:

Suivant(P)={ε,id,if,while}

Suivant(P’)={ε,id,if,while}
Suivant(S)={id,if,while}

Suivant(E)={(,id,0,1,2,3,4,5,6,7,8,9}

Suivant(E’)={+,ε}

Suivant(T)={(,id,0,1,2,3,4,5,6,7,8,9

Suivant(T’)={*,ε}

Suivant(F)={(,id,0,1,2,3,4,5,6,7,8,9}

Suivant(N)={0,1,2,3,4,5,6,7,8,9}

Suivant(N’)={ε,0,1,2,3,4,5,6,7,8,9}

Suivant(D)={0,1,2,3,4,5,6,7,8,9}

Suivant(C)={(,id,0,1,2,3,4,5,6,7,8,9}
Suivant(R)={==,!=,<,<=,>,>=}

1.3.2) Suivants:

Suivant(P)={$}

Suivant(P’)={$}
Suivant(S)={$,id,if,while,else}

Suivant(E)={;,),==,!=,<,<=,>,>=}

Suivant(E’)={;,),==,!=,<,<=,>,>=}
Suivant(T)={+,;,),==,!=,<,<=,>,>=}

Suivant(T’)={+,;,),==,!=,<,<=,>,>=}

Suivant(F)={*,+,;,),==,!=,<,<=,>,>=}

Suivant(N)={*,+,;,),==,!=,<,<=,>,>=}

Suivant(N’)={*,+,;,),==,!=,<,<=,>,>=}

Suivant(D)={*,+,;,0,1,2,3,4,5,6,7,8,9,),==,!=,<,<=,>,>=}
Suivant(C)={)}
Suivant(R)={(,id,0,1,2,3,4,5,6,7,8,9}

1.4) Table LL1:

Nonterminal	id	=	;	if	(	)	else	while	+	*	0	1	2	3	4	5	6	7	8	9	==	!=	<	<=	>	>=	$
P	P -> P'			P -> P'				P -> P'																			P -> P'
P'	P' -> S P'			P' -> S P'				P' -> S P'																			P' -> ε
S	S -> id = E ;			S -> if ( C ) S else S				S -> while ( C ) S
E	E ->T E'				E ->T E'						E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'	E ->T E'
E'			E' ->ε			E' ->ε			E' -> + T E'												E' ->ε	E' ->ε	E' ->ε	E' ->ε	E' ->ε	E' ->ε
T	T -> F T'				T -> F T'						T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'	T -> F T'
T'			T' ->ε			T' ->ε			T' ->ε	T' -> * F T'											T' ->ε	T' ->ε	T' ->ε	T' ->ε	T' ->ε	T' ->ε
F	F -> id				F -> ( E )						F -> N	F -> N	F -> N	F -> N	F -> N	F -> N	F -> N	F -> N	F -> N	F -> N
N											N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'	N -> D N'
N'			N' ->ε			N' ->ε			N' ->ε	N' ->ε	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' -> D N'	N' ->ε	N' ->ε	N' ->ε	N' ->ε	N' ->ε	N' ->ε
D											D -> 0	D -> 1	D -> 2	D -> 3	D -> 4	D -> 5	D -> 6	D -> 7	D -> 8	D -> 9
C	C -> E R E				C -> E R E						C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E	C -> E R E
R																					R -> ==	R -> !=	R -> <	R -> <=	R -> >	R -> >=

2.Analyse Ascendant SLR:

2.1) Premiers & Suivants:

2.1.1) Premiers:

Premier(P)={ ε,id,if,while}
Premier(S)={id,if,while}
Premier(E)={(,id,0,1,2,3,4,5,6,7,8,9}
Premier(T)={(,id,0,1,2,3,4,5,6,7,8,9}
Premier(F)={(,id,0,1,2,3,4,5,6,7,8,9}
Premier(N)={0,1,2,3,4,5,6,7,8,9}
Premier(D)={0,1,2,3,4,5,6,7,8,9}
Premier(C)={(,id,0,1,2,3,4,5,6,7,8,9}
Premier(R)={==,!=,<=,>,<,>=}

2.1.2) Suivants:

Suivant(P)={$,id,if,while}
Suivant(S)={$,id,if,while,else}
Suivant(E)={;,+,),==,!=,<=,>,<,>=}
Suivant(T)={;,+,
,),==,!=,<=,>,<,>=}

Suivant(F)={;,+,,),==,!=,<=,>,<,>=}
Suivant(N)={;,+,,0,1,2,3,4,5,6,7,8,9,),==,!=,<=,>,<,>=}
Suivant(D)={;,+,,0,1,2,3,4,5,6,7,8,9,),==,!=,<=,>,<,>=}
Suivant(C)={)}
Suivant(R)={(,id,0,1,2,3,4,5,6,7,8,9}

2.2) Grammaire augmentée:

💡

''' P’ → P P → P S | ε
S → id = E ; | if ( C ) S else S
S → while ( C ) S
E → E + T | T
T → T * F | F
F → ( E ) | id | N
N → N D | D
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
DC → E R E
R → == | != | < | ≤ | > | ≥ '''

2.3) Collection des items :

I0= fermeture_{ P’ → .P }={P' -> .P; P -> .P S; P -> .}

transition(I0,P)={ P' -> P.; P -> P.S; S -> .id = E ;; S -> .if ( C ) S else S; S -> .while ( C ) S}= I1

transition(I1,S)= {P -> P S.}= I2

transition(I1,id)={S -> id.= E ;}= I3

transition(I1,if)={S -> if.( C ) S else S}= I4

transition(I1,while)={S -> while.( C ) S}= I5

transition(I3,=)={S -> id =.E ;; E -> .E + T; E -> .T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9} =I6

transition(I4,()={S -> if (.C ) S else S; C -> .E R E; E -> .E + T; E -> .T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I7

transition(I5,()={S -> while (.C ) S; C -> .E R E; E -> .E + T; E -> .T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I8

transition(I6,E)={S -> id = E.;; E -> E.+ T}= I9

transition(I6,T)= {E -> T.; T -> T.* F}= I10

transition(I6,F)= {T -> F.}= I11

transition(I6,()={F -> (.E ); E -> .E + T; E -> .T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I12

transition(I6,id)= {F -> id.}= I13

transition(I6,N)={ F -> N.; N -> N.D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}=I14

transition(I6,D)= {N -> D.}= I15

transition(I6,0)= {D -> 0.}= I16

transition(I6,1)= {D -> 1.}= I17

transition(I6,2)= {D -> 2.}= I18

transition(I6,3)= {D -> 3.}= I19

transition(I6,4)= {D -> 4.}= I20

transition(I6,5)= {D -> 5.}= I21

transition(I6,6)= {D -> 6.}= I22

transition(I6,7)= {D -> 7.}= I23

transition(I6,8)= {D -> 8.}= I24

transition(I6,5)= {D -> 9.}= I25

transition(I7, C)={S -> if ( C.) S else S}= I26

transition(I7, E)={C -> E.R E; E -> E.+ T; R -> .==; R -> .!=; R -> .<; R -> .<=; R -> .>; R -> .>=}= I27

transition(I7, T)= I10

transition(I7, F)= I11

transition(I7, ()= I12

transition(I7, id)= I13

transition(I7, N)= I14

transition(I7, D) =I15

transition(I7,0)= I16

transition(I7,1)= I17

transition(I7,2)= I18

transition(I7,3)= I19

transition(I7,4)= I20

transition(I7,5)= I21

transition(I7,6)= I22

transition(I7,7)= I23

transition(I7,8)= I24

transition(I7,9)= I25

transition(I8, C)={S -> while ( C.) S}= I28

transition(I8, E)= I27

transition(I8, T)= I10

transition(I8, F)= I11

transition(I8, ()= I12

transition(I8, id)= I13

transition(I8, N)= I14

transition(I8, D) =I15

transition(I8,0)= I16

transition(I8,1)= I17

transition(I8,2)= I18

transition(I8,3)= I19

transition(I8,4)= I20

transition(I8,5)= I21

transition(I8,6)= I22

transition(I8,7)= I23

transition(I8,8)= I24

transition(I8,9)= I25

transition(I9,;)= {S -> id = E ;.}= I29

transition(I9,+)={E -> E +.T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I30

transition(I10,*)={T -> T *.F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I31

transition(I12, E)={F -> ( E.); E -> E.+ T}= I32

transition(I12, T)= I10

transition(I12, F)= I11

transition(I12, ()= I12

transition(I12, id)= I13

transition(I12, N)= I14

transition(I12, D) =I15

transition(I12,0)= I16

transition(I12,1)= I17

transition(I12,2)= I18

transition(I12,3)= I19

transition(I12,4)= I20

transition(I12,5)= I21

transition(I12,6)= I22

transition(I12,7)= I23

transition(I12,8)= I24

transition(I12,9)= I25

transition(I14, D)= {N -> N D.}= I33

transition(I14,0)= I16

transition(I14,1)= I17

transition(I14,2)= I18

transition(I14,3)= I19

transition(I14,4)= I20

transition(I14,5)= I21

transition(I14,6)= I22

transition(I14,7)= I23

transition(I14,8)= I24

transition(I14,9)= I25

transition(I14,))= {S -> if ( C ).S else S; S -> .id = E ;; S -> .if ( C ) S else S; S -> .while ( C ) S}= I34

transition(I27,R)={C -> E R.E; E -> .E + T; E -> .T; T -> .T * F; T -> .F; F -> .( E ); F -> .id; F -> .N; N -> .N D; N -> .D; D -> .0; D -> .1; D -> .2; D -> .3; D -> .4; D -> .5; D -> .6; D -> .7; D -> .8; D -> .9}= I35

transition(I27,+)= I30

transition(I27,==)= {R -> ==.}= I36

transition(I27,≠)= {R -> !=.}= I37

transition(I27,<)= {R -> <.}= I38

transition(I27,≤)= {R -> <=.}= I39

transition(I27,>)= {R -> >.}= I40

transition(I27,≥)= {R -> >=.}= I41

transition(I28,))={S -> while ( C ).S; S -> .id = E ;; S -> .if ( C ) S else S; S -> .while ( C ) S}= I42

transition(I30, T)= {E -> E + T.; T -> T.* F}= I43

transition(I30, F)= I11

transition(I30, ()= I12

transition(I30 , id)= I13

transition(I30, N)= I14

transition(I30, D) =I15

transition(I30,0)= I16

transition(I30,1)= I17

transition(I30,2)= I18

transition(I30,3)= I19

transition(I30,4)= I20

transition(I30,5)= I21

transition(I30,6)= I22

transition(I30,7)= I23

transition(I30,8)= I24

transition(I30,9)= I25

transition(I31, F)= I11

transition(I31, ()= I12

transition(I31 , id)= I13

transition(I31, N)= I14

transition(I31, D) =I15

transition(I31,0)= I16

transition(I31,1)= I17

transition(I31,2)= I18

transition(I31,3)= I19

transition(I31,4)= I20

transition(I31,5)= I21

transition(I31,6)= I22

transition(I31,7)= I23

transition(I31,8)= I24

transition(I31,9)= I25

transition(I32,))= {F -> ( E ).} =I45

transition(I32,+)= I30

transition(I34, S)={S -> if ( C ) S.else S}= I46

transition(I34, id)= I3

transition(I34, if)= I4

transition(I34, while)= I5

transition(I35, E)= {C -> E R E.; E -> E.+ T}= I47

transition(I35, T)= I10

transition(I35, F)= I11

transition(I35, ()= I12

transition(I35 , id)= I13

transition(I35, N)= I14

transition(I35, D) =I15

transition(I35,0)= I16

transition(I35,1)= I17

transition(I35,2)= I18

transition(I35,3)= I19

transition(I35,4)= I20

transition(I35,5)= I21

transition(I35,6)= I22

transition(I35,7)= I23

transition(I352,8)= I24

transition(I35,9)= I25

transition(I42, S)= {S -> while ( C ) S.}= I48

transition(I42, id)= I3

transition(I42, if)= I4

transition(I42, while)= I5

transition(I43, *)= I31

transition(I46, else)={S -> if ( C ) S else.S; S -> .id = E ;; S -> .if ( C ) S else S; S -> .while ( C ) S}= I49

transition(I47, +)= I30

transition(I49, S)= {S -> if ( C ) S else S.}= I50

transition(I49, id)= I3

transition(I49, if)= I4

transition(I49, while)= I5

2.4) Table SLR

LR table
State	ACTION																											GOTO
	id	=	;	if	(	)	else	while	+	*	0	1	2	3	4	5	6	7	8	9	==	!=	<	<=	>	>=	$	P'	P	S	E	T	F	N	D	C	R
0	r 2			r 2				r 2																			r 2		1
1	s 3			s 4				s 5																			acc			2
2	r 1			r 1				r 1																			r 1
3		s 6
4					s 7
5					s 8
6	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25											9	10	11	14	15
7	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25											27	10	11	14	15	26
8	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25											27	10	11	14	15	28
9			s 29						s 30
10			r 7			r 7			r 7	s 31											r 7	r 7	r 7	r 7	r 7	r 7
11			r 9			r 9			r 9	r 9											r 9	r 9	r 9	r 9	r 9	r 9
12	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25											32	10	11	14	15
13			r 11			r 11			r 11	r 11											r 11	r 11	r 11	r 11	r 11	r 11
14			r 12			r 12			r 12	r 12	s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25	r 12	r 12	r 12	r 12	r 12	r 12									33
15			r 14			r 14			r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14	r 14
16			r 15			r 15			r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15	r 15
17			r 16			r 16			r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16	r 16
18			r 17			r 17			r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17	r 17
19			r 18			r 18			r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18	r 18
20			r 19			r 19			r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19	r 19
21			r 20			r 20			r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20	r 20
22			r 21			r 21			r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21	r 21
23			r 22			r 22			r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22	r 22
24			r 23			r 23			r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23	r 23
25			r 24			r 24			r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24	r 24
26						s 34
27									s 30												s 36	s 37	s 38	s 39	s 40	s 41											35
28						s 42
29	r 3			r 3			r 3	r 3																			r 3
30	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25												43	11	14	15
31	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25													44	14	15
32						s 45			s 30
33			r 13			r 13			r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13	r 13
34	s 3			s 4				s 5																						46
35	s 13				s 12						s 16	s 17	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25											47	10	11	14	15
36	r 26				r 26						r 26	r 26	r 26	r 26	r 26	r 26	r 26	r 26	r 26	r 26
37	r 27				r 27						r 27	r 27	r 27	r 27	r 27	r 27	r 27	r 27	r 27	r 27
38	r 28				r 28						r 28	r 28	r 28	r 28	r 28	r 28	r 28	r 28	r 28	r 28
39	r 29				r 29						r 29	r 29	r 29	r 29	r 29	r 29	r 29	r 29	r 29	r 29
40	r 30				r 30						r 30	r 30	r 30	r 30	r 30	r 30	r 30	r 30	r 30	r 30
41	r 31				r 31						r 31	r 31	r 31	r 31	r 31	r 31	r 31	r 31	r 31	r 31
42	s 3			s 4				s 5																						48
43			r 6			r 6			r 6	s 31											r 6	r 6	r 6	r 6	r 6	r 6
44			r 8			r 8			r 8	r 8											r 8	r 8	r 8	r 8	r 8	r 8
45			r 10			r 10			r 10	r 10											r 10	r 10	r 10	r 10	r 10	r 10
46							s 49
47						r 25			s 30
48	r 5			r 5			r 5	r 5																			r 5
49	s 3			s 4				s 5																						50
50	r 4			r 4			r 4	r 4																			r 4

2.5) Automate SLR

Note : L'ordre des états n'est pas le même et on a utilisé les termes « chiffre » et « oprel » pour représenter les chiffres et les opérations de comparaison, respectivement.