Précédent Index Suivant

Chapitre 2 :   Analyse syntaxique

On définit un petit langage à la Pascal, PP. La première version s'appelle PP1. Le but est la construction d'un compilateur qui génère du P-Code (cf. section 1.5) à partir d'un programme PP1 ; ce compilateur s'appellera pp1 et sera développé en C (figure 2.1). Ce chapitre se limite à l'analyse lexicale et syntaxique du langage ; la construction du compilateur sera complétée dans les chapitres suivants. 

+---------------------------------+
|   PP1         pp1      P-Code   |
|                                 |
+----------+           +----------+
           |     C     |
           |           |
           +-----------+
Figure 2.1 : T-diagramme du compilateur pp1.

2.1   Syntaxe d'un langage

La syntaxe d'un langage peut être donnée par des exemples ou une description informelle. Cependant, il est plus aisé de décrire une syntaxe par une grammaire algébrique.

Une telle grammaire est formée de règles de production. Chaque règle indique en partie gauche un non-terminal qui peut être dérivé en l'une des formes apparaissant en partie droite (les formes sont séparées par des |).

Une forme est composée de terminaux (en minuscule, par exemple while, ou caractères spéciaux, par exemple + ; ces terminaux apparaissent tel quel dans le langage) et/ou de non-terminaux (en majuscule, par exemple BLOCK).

Une forme entre accolades { et } signifie qu'elle peut être présente zéro, une ou plusieurs fois. Le symbole e signifie que la partie gauche peut se dériver en une forme vide.

Le but de l'analyse syntaxique est de montrer que l'axiome de la grammaire (un non-terminal particulier, en général la partie gauche de la première règle, ici PROGRAM) peut être dérivé en une suite de terminaux formant le texte à analyser.

2.2   Syntaxe du langage PP1

La syntaxe du langage PP1 est donnée à la figure 2.2.
PROGRAM ::= program ID ; BLOCK .
BLOCK ::= CONSTS VARS INSTS
CONSTS ::= const ID = NUM ; { ID = NUM ; } | e
VARS ::= var ID { , ID } ; | e
INSTS ::= begin INST { ; INST } end
INST ::= INSTS | AFFEC | SI | TANTQUE | ECRIRE | LIRE | e
AFFEC ::= ID := EXPR
SI ::= if COND then INST
TANTQUE ::= while COND do INST
ECRIRE ::= write ( EXPR { , EXPR } )
LIRE ::= read ( ID { , ID } )
COND ::= EXPR RELOP EXPR
RELOP ::= = | <> | < | > | <= | >=
EXPR ::= TERM { ADDOP TERM }
ADDOP ::= + | -
TERM ::= FACT { MULOP FACT }
MULOP ::= * | /
FACT ::= ID | NUM | ( EXPR )

Figure 2.2 : Grammaire du langage PP1.

Les mots clés sont réservés ; ils apparaissent en minuscule dans la grammaire.

Certains non-terminaux ne sont pas décrits par cette grammaire. Il s'agit des non-terminaux pris en charge par l'analyse lexicale :
ID
représente les identificateurs, c'est-à-dire toute suite de lettres ou chiffres commençant par une lettre et qui ne représente pas un mot clé (qui sont les terminaux présents dans la grammaire) ;
NUM
représente les constantes numériques, c'est-à-dire toute suite de chiffres.

2.2.1   Méta-règles

Une série de règles définissent la forme d'un programme PP1 :
  1. Un commentaire est une suite de caractères encadrés des parenthèses (* et *) ;
  2. Un séparateur est un caractère séparateur (espace blanc, tabulation, retour chariot) ou un commentaire ;
  3. Deux ID ou mots clés qui se suivent doivent être séparés par au moins un séparateur ;
  4. Des séparateurs peuvent être insérés partout, sauf à l'intérieur de terminaux.

2.2.2   Sémantique

La sémantique de PP1 est claquée sur celle de Pascal. Les identificateurs doivent être déclarés pour être utilisés. Toutes les variables sont implicitement déclarées de type entier.

2.3   Analyseur syntaxique de PP1

L'analyseur lexical peut être vu comme une procédure appelée par l'analyseur syntaxique. Chaque appel à la procédure d'analyse lexical NEXT_TOKEN met à jour les variables TOKEN, SYM, et VAL :
TOKEN
contient le dernier token lu ;
SYM
contient la forme textuelle du dernier token lu ;
VAL
est la valeur du dernier token lu.
type TOKENS = (ID_TOKEN, NUM_TOKEN, PLUS_TOKEN, MOINS_TOKEN, MUL_TOKEN
    DIV_TOKEN, EGAL_TOKEN, DIFF_TOKEN, INF_TOKEN, SUP_TOKEN,
    INF_EGAL_TOKEN, SUP_EGAL_TOKEN, PAR_OUV_TOKEN,
    PAR_FER_TOKEN, VIRG_TOKEN, PT_VIRG_TOKEN, POINT_TOKEN,
    AFFEC_TOKEN, BEGIN_TOKEN, END_TOKEN, IF_TOKEN ,WHILE_TOKEN,
    THEN_TOKEN, DO_TOKEN, WRITE_TOKEN, READ_TOKEN,
    CONST_TOKEN, VAR_TOKEN, PROGRAM_TOKEN, TOKEN_INCONNU) ;
  ALFA = packed array [1 .. 8] of char ;
var TOKEN : TOKENS ;
  SYM : ALFA ;
  VAL : integer ;

Une procédure TESTE teste si le prochain token (TOKEN) est bien celui passé en paramètre à la procédure ; on s'arrête sur une erreur sinon (procédure ERREUR) : 
 procedure TESTE (T:TOKENS) ; 
 begin
    if TOKEN = T
       then NEXT_TOKEN
       else ERREUR
 end ;
Le langage PP1 ayant de bonnes propriétés (se référer au cours d'Analyse Syntaxique), il est possible d'écrire un analyseur récursif descendant simple (sans retour arrière). L'idée est que chaque règle de la grammaire est associée à une procédure qui << vérifie >> la concordance du texte à analyser avec une de ses parties droites. Voici la fonction principale d'un tel analyseur : 
 procedure PROGRAM;
 begin 
    TESTE(PROGRAM_TOKEN) ; 
    TESTE (ID_TOKEN) ; 
    TESTE (PT_VIRG_TOKEN) ;
    BLOCK ; 
    if TOKEN <> POINT_TOKEN then ERREUR
 end ;
La procédure BLOCK est la suivante : 
 procedure BLOCK ; 
 begin
    if TOKEN = CONST_TOKEN then CONSTS ;
    if TOKEN = VAR_TOKEN then VARS ;
    INSTS
 end
Les autres procédures sont : 
 procedure CONSTS ; 
 begin
    TESTE (CONST_TOKEN) ; 
    repeat
       TESTE (ID_TOKEN) ; 
       TESTE (EGAL_TOKEN) ;
       TESTE (NUM_TOKEN) ;  
       TESTE (PT_VIRG_TOKEN) 
    until TOKEN <> ID_TOKEN 
 end ;

 procedure VARS ; 
 begin 
    TESTE (VAR_TOKEN) ; 
    TESTE (ID_TOKEN) ; 
    while TOKEN = VIRG_TOKEN do 
       begin NEXT_TOKEN ; TESTE (ID_TOKEN) end ; 
    TESTE (PT_VIRG_TOKEN) 
 end ;

 procedure INSTS ; 
 begin 
    TESTE (BEGIN_TOKEN) ; 
    INST ; 
    while TOKEN = PT_VIRG_TOKEN do 
       begin NEXT_TOKEN ; INST end ; 
    TESTE (END_TOKEN) 
 end ; 

 procedure INST ; 
 begin 
    case TOKEN of 
       ID_TOKEN : AFFEC ; 
       IF_TOKEN : SI ; 
       WHILE_TOKEN : TANTQUE ; 
       BEGIN_TOKEN : INSTS ; 
       WRITE_TOKEN : ECRIRE ;
       READ_TOKEN : LIRE 
    end
 end ;

 procedure AFFEC ; 
 begin 
    TESTE (ID_TOKEN) ; 
    TESTE (AFFEC_TOKEN) ; 
    EXPR
 end ;

 procedure SI ; 
 begin 
    TESTE (IF_TOKEN) ; 
    COND ; 
    TESTE (THEN_TOKEN) ; 
    INST 
 end ;

 procedure TANTQUE ;
 begin 
    TESTE (WHILE_TOKEN) ; 
    COND ; 
    TESTE (DO_TOKEN) ; 
    INST 
 end ;

 procedure ECRIRE ; 
 begin 
    TESTE (WRITE_TOKEN) ;
    TESTE (PAR_OUV_TOKEN) ;
    EXPR ; 
    while TOKEN = VIRG_TOKEN do 
       begin NEXT_TOKEN ; EXPR end ; 
    TESTE (PAR_FER_TOKEN) ; 
 end ;

 procedure LIRE ; 
 begin 
    TESTE (READ_TOKEN) ; 
    TESTE (PAR_OUV_TOKEN) ;
    TESTE (ID_TOKEN) ; 
    while TOKEN = VIRG_TOKEN do 
       begin NEXT_TOKEN ; TESTE (ID_TOKEN) end ; 
    TESTE (PAR_FER_TOKEN) 
 end ;

 procedure EXPR ; 
 begin 
    TERM ; 
    while TOKEN in [PLUS_TOKEN, MOINS_TOKEN] do 
       begin NEXT_TOKEN ; TERM end 
 end ;

 procedure COND ;
 begin 
    EXPR ; 
    if TOKEN in [EGAL_TOKEN, DIFF_TOKEN, INF_TOKEN, SUP_TOKEN,
       INF_EGAL_TOKEN, SUP_EGAL_TOKEN ] 
       then begin
          NEXT_TOKEN ; 
          EXPR 
       end
 end ;

 procedure TERM ;
 begin 
    FACT ; 
    while TOKEN in [MULT_TOKEN, DIV_TOKEN] do 
       begin NEXT_TOKEN ; FACT end 
 end ;

 procedure FACT ;
 begin 
    if TOKEN in [ID_TOKEN, NUM_TOKEN]
       then NEXT_TOKEN 
    else begin
       TESTE (PAR_OUV_TOKEN) ; 
       EXPR ;
       TESTE (PAR_FER_TOKEN) 
    end 
 end ;
Cet analyseur s'arrête à la première erreur détectée. Nous verrons dans un chapitre suivant comment améliorer cette situation.

2.4   Travaux dirigés et travaux pratiques

  1. Quelle est l'utilité des points virgules dans la grammaire du langage PP1 (figure 2.2) ? Peux-t-on les supprimer ?

  2. Dans la grammaire de PP1 (comme en Pascal), une instruction INST peut se dériver en e. Quelle peut être l'utilité d'une instruction vide ?

  3. En PP1, les déclarations de constantes (const) doivent précéder les déclarations de variables (var). Quelle est l'utilité d'une telle règle ? Comment s'en affranchir ?

  4. Modifier la grammaire de PP1 (figure 2.2) pour inclure une branche else facultative à l'alternative if. Quel problème survient alors ? Considérer le code : 
     begin
    if A then
    ... 
    if B then
    ...
    else
    ...
 end
    Comment le résoudre ?

  5. Montrer que la méta-règle définissant les commentaires est ambiguë. Proposer une modification pour lever l'ambiguïté.

    La possibilité d'imbrication de commentaires est-elle souhaitable ? Considérer le code : 
     begin 
    (* Somme de A et B 
    A := A + B ;
    (* Produit de A et B *)
    A := A * B   
 end
  6. Écrire une fonction NEXT_CHAR qui retourne le prochain caractère du flux d'entrée en effectuant le filtrage suivant : tout séparateur sera renvoyé comme le caractère espace. (Tenir compte de la convention adoptée dans l'exercice précédent pour les commentaires).

  7. Écrire la fonction NEXT_TOKEN d'analyse lexicale en utilisant la fonction NEXT_CHAR.

  8. Écrire les fonctions d'analyse syntaxique du langage PP1 défini par la grammaire de la figure 2.2 sur le modèle donné dans ce chapitre.

  9. à l'aide des fonctions précédentes, écrire un programme qui vérifie la correction syntaxique d'un code PP1. En cas d'erreur, on affiche le numéro de la ligne à laquelle la première erreur apparaît.

  10. Comment imaginer la prise en compte de la possibilité d'inclure des blancs au milieu des mots clés et des identificateurs ? (Cette possibilité est, par exemple, offerte par le langage Fortran.)
Précédent Index Suivant