TRADUCTION

_______________________________________________________________________________

TD #1

<repeatstat> := repeat <statlist> until <exp>

2. Vérifer

Que le type de <exp>.res est un booléen
Référence en arriere vers début => mémorisation de l'@ du début

3. Ecriture

Nexts := repeatstat => entrée de cette procédure

Procédure repeatstat is
     R: String;
	 Début integer;
	 Begin
         Debut := nextquad;
         Statlist; -> Quadruplet pour statlist
         SHIP("until");
         EXP(R);
         CHECKTYPE ( R, Boolean );
         GEN (  " if  " ||  R || "= 0 goto" || str(Début) ); 
          \ générantion d'1 quadruplet
      End

ANALYSE ASCENDANTE

TD - 1998.12.15 - source jpm - Ex (1)

(1)
      | Q <exp1>
 ---------------------- ident := <exp1>.res
      | Q <exp2>		
 ---------------------- TEST : if ident > <exp3>.res goto SUITE
      | Q <exp3>
      | <statlist>
      ident := ident + <exp2>.res
      goto TEST

SUITE:
                            --- Utilisation de deux marqueurs syntaxiques

Ecrivons la grammaire :

 /  <forstat> -> 
|        for ident : = <exp1> <init> step <exp2> 
|        until <exp3> <test> do <statlist>
|   <init> -> _\
 \  <test> -> _\

Cherchons les piles sémentiques

adr : contient des @ incomplètes
res : contients les résultat des non terminaux

Actions sémantiques

synt: ( for    ident    :=     <exp1>      _\ )
res:  (                     <exp1>.res        )
adr:  (                                       )

Reduction <init> -> _\ :
{ 
    CHECKTYPE(<exp1>.res, entier);
    GEN ("ident.str := <exp1>.res ");
}

synt: ( for ident :=   <exp1>   <init> step   <exp2>   until    <exp3>      _\ )
res:  (              <exp1>.res             <exp2>.res       <exp3>.res        )
adr:  (                                                                        )
 Reduction <test> -> _\ :
{
    CHECKTYPE(<exp2>.res, entier); CHECKTYPE(<exp3>.res, entier);
    <test>.adr := NEXTQUAD;
    GEN ("id ident.str > <exp3>.res goto NIL ");
}

synt:(for ident := <exp1> <init> step <exp2> until <exp3> <test> do <statlist> )
res: (            <exp1>.res       <exp2>.res   <exp3.res>                     )
adr: (                                                     TEST                )

 Reduction <forstat> -> for ... <statlist>  :
{
    GEN(" ident.str := ident.str + <exp2.res> ");
    GEN ("goto <test>.adr ");
    BACKPATCH ( { <test>.adr } , NEXTQUAD ); 
}

TD - 1998.12.15 - source jpm - Ex (2)

<loopstat> -> ident : <debut> loop <statlist> endloop
<debut> -> _\
<inst> -> ... | <loopstat> | <exitstat>
<exitstat> -> when <exp> exit ident

Les piles

adr
res
autre pile : entree : entree dans la TDS

Action semantiques

synt: ( ident  : _\ )
res:  (             )
adr:  (             )

Reduire <debut> -> _\
{   
    ENTER(ident.str,P); 
    TDS(P).type := etiq_boucle;
    TDS(P).liste =  0 ;             // liste des goto @endloop_ident
    <debut>.entree := P ;
    <debut>.adr := NEXTQUAD ;
}

synt:  ( ident  : <debut> loop ... when <exp> exit ident1 )
res:   (                                                  )
adr:   (           DEBUT                                  )
entree:(             P 
Reduire when <exp> exit ident1 <- <exitstat>
{   
    CHECKTYPE( <exp>, boolean );
    SEARCH( ident1.str, Q);
    if q = 0 then ERROR endif;
    if ( TDS(Q).type =/= etiq.boucle ) then ERROR endif ;
    APPEND (TDS(Q).liste, NEXTQUAD );
    GEN( "if <exp>.res = 1 goto NIL ");
}

synt:  ( ident  : <debut> loop <statlist> endloop )
res:   (                                          )
adr:   (           DEBUT                          )
entree:(             P 

{ 	
    GEN( "goto <debut>.adr ");
    BACKPATCH( TDS( <debut>.entree ).liste , NEXTQUAD );
    CANCEL ( TDS(<debut>.entree).symbole);	
}

Reduire en <loopstat> !?!

Exam: 1997.01.22 - Source:jpm(1999.01.05)

Q.1/ Descente récursive

<boucle-aig> -> while-aig ident { and ident }* do
<suite-d-instruction> then
{ when ident => <suite-d-instruction> }⁺ end

Q I.1.a / Schema equivalent en quadruplets :

debut:
(t1:)   if B1 = 0 goto n1
(t2:)   if B2 = 0 goto n2
(t3:)   if B3 = 0 goto n3
(t4:)   if B4 = 0 goto n4
        | Q pour S0
        goto debut:
n4:
        | Q pour S4
n2:
        | Q pour S2
n1:
        | Q pour S1
n3:
        | Q pour S3
suite:

On suppose que la construction est corecte du point de vue des booléens

R I.1.b/

Réf en arriere: Debut -> Mémoriser Debut

Réf en avant:

if Bi = 0 goto ni /

            TDS
 ______________________________
| SYMBOLE |   TYPE   |   ADR   |  
|---------|----------|---------|
|   Bi    |          |   ti    |
|_________|__________|_________|

Adr est crée à la rencontre de Bi; MAJ when Bi => Si

goto SUITE ;
- liste @ de quad incomplets
- MAJ à la rencontre de end

Vérification des types des booleens : CHECKTYPE

Q I.1.C/

procedure BOUCLEAIG is:
    Debut :integer;
    L :list_of_quad := 0 ;
    P :integer;

    begin:
        SKIP('while-aig');
        Debut:=NEXTQUAD;
        loop
            if NEXTS =/= ident then ERROR endif;
            SEARCH(ident.string , P);
            if p=0 then ERROR endif;
            if TDS(P).type =/= booleen then ERROR endif; 
            
            TDS(P) := NEXTQUAD;
            GEN("if NEXTS.string = 0 goto NIL ");
            SCAN;
         exit when NEXTS =/= 'and' ;
            SKIP('and');
         endloop
         
         SKIP('do');
         Suite_inst;
         SKIP('then');
         GEN("goto Debut");
         
        loop
            SKIP('when';
            if NEXTS =/= ident then ERROR endif;
            SEARCH ( NEXTS.string, P);
            if TDS(P).type =/= boolean then ERROR endif;
        
            BACKPATCH({TDS(P).adr} , NEXTQUAD);
            SCAN;
            (*)
            SKIP ('=>');
            Suite_inst;
            APPEND(L,NEXTQUAD);
            GEN(goto NIL);
        exit when NEXTS =/= 'when' ;
        endloop;
        SKIP("end');
        BACKPATCH(L,NEXTQUAD);
    end

Modifications à apporter pour pouvoir gérer la structure suivante :

while-aig B1 and ... do
    when B2 => while-aig B1 ...                         <= IMBRICATION
                        when B1
    when B1
    ...

(*) CANCEL(TDS(P).symbol );

Q I.2 / ANALYSEUR ASCENDANT

<boucle-aig> ->
while-aig <conjonction-de-booleens> do <suite-d-instruction> then <suite-d-alternatives> end

Piles semanatiques :

Debut
L (liste quad incomplets)
Couple(liste symbole - adresse)

Actions semantiques

Synt: ( while-aig _\ )

Reduction: P -> _\
{
    P.DEBUT := NEXTQUAD;
}



Synt  (  while-aig     P      B1 )
DEBUT (     -        Debut       )

Red: <bool> -> ident
{
    SEARCH (ident.string, P):
    if P=0 then ERROR endif;
    CHECKTYPE (ident.string, boolean):
    <bool>.couple := (ident.string , NEXTQUAD );
    GEN("if ident.string = 0 goto NIL");
}    




Synt  (  while-aig     P      <bool>  )
DEBUT (     -        Debut            )
Couple(                      (B1,N1)  )

 Red <cb> -> <bool>
{  
    <cb>.coucple := <bool>.couple ; 
}



Synt: ( while-aig     P           <cb> 
DEBUT (             Debut
Couple(                          (B1,N1)  

 Reduction <cb1> -> <cb2> and bool
{
    <cb1>.couple := <cb2>.couple || <bool>.couple;
} 
note: || = Concatenation




Synt: ( while-aig   P                     do <statlist> then Q when B4 _\  )
DEBUT:(           Debut
Couple(                 {(B1,N1),...(B4,N4)}

Red: Q -> _\
{   
    GEN( "goto P.debut");   
}


Red R -> _\
{
    CHERCHER( <cb>.couple , ident.str, N);
    BACKPATCH( {N}, NEXTQUAD ):
}
Red: <alt> -> when ident R => <si> :
{
    <alt>.L = NEXQUAD;
    GEN( "goto NIL" );
}
Red <sa> -> <alt> : 
{    
    <sa>.L := <alt>.L ;
}        

Red <sa1> -> <sa2> <alt> :
{   
    <sa1>.L := <sa2>.L || <alt>.L     
}

Red <boucle-aig> -> while-aig P <cb> do <si> then Q <sa> end
{   
    BACKPATCH ( <sa>.L, NEXTQUAD );   
}

Exam: 1997.09.09 Source: JPM(1999.01.12)

Q I.1/ Schemas equivalent en quadruplets

...

Q I.3/ Actions Sémantiques

synt: ( for ident in    <exp1> .. <exp2>     loop _\ )
res : (             <exp1>.res  <exp2>.res 

reduction M -> _\ :
{
    CHECKTYPE ( <exp1>.res , entier );
    CHECKTYPE ( <exp2>.res , entier );
    ENTER(id.str, P);   TDS(P).type := 'entier'
    GEN ("id.str := <exp1>.res ");
    M.adr := NEXTQUAD;
    GEN( "if id.str > <exp2>.res goto NIL ");
}    

synt: ( for ident in   <e1> .. <e2>   loop M <si1> when <e3> N do <si2> endloop
res : (            <exp1>.res  <exp2>.res             <exp3>.res
adr : (                                  TEST              TEST2

Reduction de N -> _\: 
{
    CHECKTYPE (<exp3>.res, booleen );
    N.adr := NEXTQUAD;
    GEN("if <exp3>.res = 0 goto NIL ");
}

Reduction <boucle> -> for id in <e1> .. <e2>
                          loop M <si1> when <E3> N do <si2> endloop
{
    BACKPATCH( {N.adr}, NEXTQUAD );
    GEN(" id.str := id.str + 1 ");
    GEN(" goto string(M.adr)");
    BACKPATCH({M.adr}, NExTQUAD):
    CANCEL(id.str);
}

Exam 1998/01/23 - R.II

Q.1/

Ennoncer les problèmes posés pour la mise en oeuvre de la traduction, et les solutions proposées.

R.1/

Piles sémantiques necessaires :
- debut
- list eq
- res
Nescessiter de découper les règles
- aprés (ident) (solution (1) ) and ...) génerer ident:=0
- aprés ident dans when ... £
Faire des fusion de listeq <suite_alt> ; <alt>
transmettre liste <alt> -> <suitealt> et
<s.alt> -> <suitealt>

Q.2/

Donner les actions sémantiques pour la traduction couplée avec une analyse ascendante.

R.2/

Synt   ( cond  (ident)  _\  )
deb    (   -      -         )
listeq (   -      -         )


Red M -> _\

{ 
SEARCH ( ident.string, P) ;
if P=0 then ERROR endif;
CHECKTYPE (id.strring, entier);
GEN( " ident.string := 0 " );
}

Synt   ( cond  (ident1) M when ident2 _\  )
deb    (   -      -     -   -    -        )
listeq (   -      -     -   -    -        )
res    (   -      -     -   -    -        )

Red N -> _\

{
SEARCH (ident2.string , P);
if P=0 then ERROR endif;
CHECKTYPE (ident2.string , boolean);
N.deb =:= NEXTQUAD;
GEN ( "if ident2.string == 0 goto NIL" );
}

Synt   ( cond (ident1)  M when ident2 N =>: <inst> return <exp>  )
deb    (   -      -     -   -    -   N.deb    -             -    )
listeq (   -      -     -   -    -    -       -             -    )
res    (   -      -     -   -    -    -       -        <exp>.res )

{
CHECKTYPE (<exp>.res , entier );
GEN ( "ident1.string := <exp>.res ");
<alt>.listeq := NEXQUAD;
GEN ( "goto NIL");
BACKPATCH ( { N.deb}, NEXTQUAD );
}

Synt   ( Cond (ident2)  M  <alt>  )
deb    (   -      -     -     - )
listeq (   -      -     -     - )
res    (   -      -     -     - )

Red listealt -> alt
{ listeAlt.listeq := alt.listeq }

Red listalt1 -> listalt2; alt
{ listalt1.listeq := listalt2.listeq U alt.listeq


Synt   ( Cond (ident1)  M  <SuiteAlt>   endcond)
deb    (   -      -     -     -            -    )
listeq (   -      -     -     -            -    )
                             {B1, B2, B3}
res    (   -      -     -   suitealt.listq -    )

{ BACKPATCH ( <suitealt>.listq, NEXTQUAD ); }

Q.3/

On modifie G2 comme suit: alt - when expression booleenne = instruction return exp Donner les modifications induites par cette nouvelle règle.

R.3/

...
Nouveaux Pb, vérifier type de résultat de <expBool> memoriser ji dans M.deb aprés ERi ( Comme avant !) en compant la regle <alt> comme avant.

Note: _\ = lambda ; a/ = alpha

Synt: ( while-aig _\ )

Reduction: M -> _\
M.DEBUT := NEXTQUAD;
M.lqi :=) MAKELIST ;

Synt: (  while-aig   P  )
nom : (                  )
@   : (              M.adr )
lqi : (              M.lqi )



Synt: ( a/ while-aig   M   <cb> do <statlist> then _\  )
nom : (                                                )
@   : (              M.adr                             )
lqi : (              M.lqi                             )

Red: N -> _\

GEN( "goto" | str (M.adr) );



Synt: ( a/ while-aig   M   <cb> do <statlist> then   N   <sa> end )
nom : (                                                           )
@   : (              M.adr                                        )
lqi : (              M.lqi                                        )

Red: <boucle-aig> -> while-aig ...

NEXTQUAD := NEXTQUAD - 1;
BACKPATCH (M.lqi, NEXTQUAD );



Red: <booleen> -> ident

SEARCH (ident.string, P)
if P=0 then ERREUR(1)
CHECKTYPE (ident.string, Boolean)  <=> if TDS[P] type =/= Boolean then ERREUR(2)
TDS[P].branch := NEXTQUAD
GEN("if"||ident.string||"=0 goto NIL")



synt: ( a/ when   ident       _\  )
nom : (         ident.string      )

Red: P-> _\
SEARCH '(ident.string, boolean, P )
if P=0 then Erreur (1)
BACKPATCH ( TDS[P].branch, NEXQUAD )



( a/ while-aig  M  when    ident    =>  <statlist> )
(                      ident.string                )
(              M.adr                               )
(              M.lqi                               )

<alt> => when ident
M.lqi = MERGE (M.lqi, NEXQUD)
GEN( "goto fin" )
( a/ while ... <alt> )

( a/ while-aig M when ident => <statlist> ) ( ident.string ) ( M.adr ) ( M.lqi ) <alt> => when ident M.lqi = MERGE (M.lqi, NEXQUD) GEN( "goto fin" ) ( a/ while ... <alt> )