Option Traduction de Programmes Option Traduction de Programmes
TD Mercredi 5 février

Analyse Syntaxique

  1. Dans un automate déterministe il n'y a pas de transitions e. Donc, le processus de calculer les ensembles prévision ne peut pas être basé sur les transitions e; donner une description plus précise de comment ces ensembles sont calculés.

    Réponse Chaque fois qu'un état de l'automate déterministe contient deux items de la forme X® a. Y b et Y® . g, ajouter Prem(b) à l'ensemble de prévision de l'item Y® . g.
    Et, si b[ * || (® )] e, tout élément de l'ensemble de prévision de X® a. Y b sera propagé à celui de Y® . g.
    Et enfin la règle ``normale'' de propagation des ensembles comme dans le cas de l'automate nondéterministe: si un état contient un item X® a. y b {E}, E est ajouté à l'ensemble de l'item X® ay. b {E} dans le y successeur de l'état.
    En particulier, la partie des ensembles qui n'est pas propagée d'autres états, peut-elle être calculée à partir des items d'un état?
    Réponse Oui.

  2. Pour les grammaires suivantes:

    1. S  ®  X$
      X  ®  Ma  |  bMc  |  dc  |  bda
      M  ®  d
      Réponse Non SLR(1); pour le programme dc, après lecture de d, faut-il réduire par M  ®  d?
      LALR(1); le d successeur de l'état initial contient les items M® d. {a} et X® d.c {$}; donc pas de conflit
      LR(1) parce que LALR(1)
    2. S  ® (X  |  E]  |  F)
      X  ®  E )  |  F]
      E  ®  A
      F  ®  A
      A  ® 
      Réponse Non SLR(1); pour le programme (), après lecture de (, on fait la réduction par A ® e; on a maintenant (A sur la pile; faut-il réduire par E  ®  A ou F  ®  A?
      LALR(1); le (A successeur de l'état initial contient les items E ® A.  {)} et F® A. {]}; donc pas de conflit
      LR(1) parce que LALR(1)
  3. Pour la grammaire et le programme suivants, combien d'analyses de sous-mots seraient trouvées par un algorithme d'analyse par programmation dynamique?
    P  ®  Bloc
    Bloc ® { Dliste Iliste }
    Dliste  ®  D;Dliste | e
    Iliste  ®  I;Iliste | e
    D  ®  int decliste
    decliste  ®  decl | decl,decliste
    decl  ®  identificateur | identificateur=exp
    I  ®  exp | identificateur = exp | Boucle | Bloc | e
    Boucle  ®  for ( I;I;I ) I exp  ®  arith  |  arith boolop arith
    arith  ®  M  |  M addop arith
    M  ®  F  |  F mulop M
    F  ® identificateur | constante | identificateur postop | (arith)
    { int x=0,y;
    for (y=0;2*y<10;y++) x++;
    x--;
    y=0;
    }
    
    
    Réponse
    Enormément!
    P: un seul; tout le programme
    Bloc: comme pour P
    Dliste: tous les suites de longueur 0 du programme, une cinquantaine!
    et la ``vraie'' Dliste int x=0,y;
    Iliste: tous les suites de longueur 0 du programme,
    et y; et y;for (y=0;2*y<10;y++) x++; et for (y=0;2*y<10;y++) x++; et x++; et y;for (y=0;2*y<10;y++) x++;x--; et for (y=0;2*y<10;y++) x++;x--; et x++;x--; et x--; et y;for (y=0;2*y<10;y++) x++;x--;y=0; et
    for (y=0;2*y<10;y++) x++;x--;y=0; et x++;x--;y=0; et x--;y=0; et y=0;
    etc. Notez que la grammaire est ambigue! L'analyseur va trouver les deux analyses de y=0 comme un I.



File translated from TEX by TTH, version 3.05.
On 27 Feb 2003, 11:52.