Aller au contenu principal
Version: 2024

03 - Analyse sémantique

Informations​

info

Deadline: le 15 mai, 23:59
Points: 2 points de la note finale
Lien: https://classroom.github.com/a/MT-NqADe
Téléchargement tardif: 0.5p/jour (maximum 4 jours)

Demandes​

Analysez du point de vue sémantique l’AST reçu. Remplissez les tableaux de symboles, vérifiez les déclarations et les types des données.

Vous allez recevoir l’AST sous la forme d’un JSON lu à partir d’un fichier reçu de la ligne de commande. Les entrées sont similaires aux sorties du devoir précédant. Les résultats auront toujours la structure de l’AST mais, cette fois, les tableaux de symboles et les types des expressions seront remplis.

attention

Le repository des testes contient aussi le code source à partir duquel on a obtenu l’AST en utilisant la solution du devoir précédant. Ne faites pas la confusion entre les deux! Les données d’entrée pour ce devoir seront les ASTs. On a ajouté aussi le code source pour rendre la resolution plus facile, mais ce devoir travail exclusivement avec des ASTs.

Le programme source recevra deux paramètres de la ligne de commande: le chemin vers le fichier d'entrée et le chemin vers le fichier de sortie.

$ ./gradlew run --args="path/to/input.json path/to/output.json"

Exemple:

Pour le code source suivant:

/* Variable value Attribution */

declare integer n;

n = 6;

L’entrée sera:

{
  "@type" : "Module",
  "block" : {
    "@type" : "Block",
    "statements" : [ {
      "@type" : "Group",
      "declarations" : [ {
        "@type" : "VariableDefinition",
        "variable" : {
          "@type" : "Identifier",
          "title" : "n",
          "typeName" : "I64",
          "line" : 3
        },
        "init" : null,
        "line" : 3
      } ],
      "line" : 3
    }, {
      "@type" : "Assignment",
      "to" : {
        "@type" : "Identifier",
        "title" : "n",
        "typeName" : null,
        "line" : 5
      },
      "from" : {
        "@type" : "Value",
        "value" : "6",
        "typeName" : "I64",
        "line" : 5
      },
      "line" : 5
    } ],
    "line" : 3,
    "scope" : {
      "@type" : "SymbolTable",
      "variables" : { },
      "types" : { },
      "functions" : { }
    }
  },
  "line" : 3
}

Et la sortie que vous devez obtenir après l’analyse est:

{
  "@type" : "Module",
  "block" : {
    "@type" : "Block",
    "statements" : [ {
      "@type" : "Assignment",
      "to" : {
        "@type" : "Identifier",
        "title" : "n",
        "typeName" : "I64",
        "line" : 5
      },
      "from" : {
        "@type" : "Value",
        "value" : "6",
        "typeName" : "I64",
        "line" : 5
      },
      "line" : 5
    } ],
    "line" : 3,
    "scope" : {
      "@type" : "SymbolTable",
      "variables" : {
        "n" : "I64"
      },
      "types" : {
        "I64" : {
          "@type" : "Integer",
          "itype" : "I64",
          "title" : "I64"
        }
      },
      "functions" : { }
    }
  },
  "line" : 3
}

Le tableau de symboles​

Pour une portée de visibilité (scope), le tableau de symboles gardera les types, les variables et les fonctions définis. Les tableaux de symboles contiennent les champs suivants:

  • variables : HashMap<String, String?> : la clé est le nom d’une variable. La valeur est le nom de son type. Les valeurs coïncident avec les clés du types
  • types : HashMap<String, Type> : la clé est le nom du type (qui se retrouve, pour les expressions, dans le champ typeName), et la valeur et le type corréspondant.
  • functions : HashMap<String, Function> : la clé est le nom de la fonction, la valeur est son contenu (obtenu après la définiton).

Erreurs semantiques​

Les erreurs sémantiques seront représentées en utilisant des instances de la classe Semantic Error. Si notre programme contient des erreurs sémantiques, le résultat ne sera plus l’AST, mais une liste contenant les erreurs.

Exemple:

Pour le code source suivant:

/* Attribution error */

declare integer a;
declare string s;

a = s;

L’entrée (l’AST) sera:

{
  "@type" : "Module",
  "block" : {
    "@type" : "Block",
    "statements" : [ {
      "@type" : "Group",
      "declarations" : [ {
        "@type" : "VariableDefinition",
        "variable" : {
          "@type" : "Identifier",
          "title" : "a",
          "typeName" : "I64",
          "line" : 3
        },
        "init" : null,
        "line" : 3
      } ],
      "line" : 3
    }, {
      "@type" : "Group",
      "declarations" : [ {
        "@type" : "VariableDefinition",
        "variable" : {
          "@type" : "Identifier",
          "title" : "s",
          "typeName" : "String",
          "line" : 4
        },
        "init" : null,
        "line" : 4
      } ],
      "line" : 4
    }, {
      "@type" : "Assignment",
      "to" : {
        "@type" : "Identifier",
        "title" : "a",
        "typeName" : null,
        "line" : 6
      },
      "from" : {
        "@type" : "Identifier",
        "title" : "s",
        "typeName" : null,
        "line" : 6
      },
      "line" : 6
    } ],
    "line" : 3,
    "scope" : {
      "@type" : "SymbolTable",
      "variables" : { },
      "types" : { },
      "functions" : { }
    }
  },
  "line" : 3
}

Et la sortie sera:

[ {
  "type" : "TYPE_MISMATCH",
  "line" : 6
} ]

Sérialisation et désérialisation​

Pour ce devoir, vous auriez besoin d’un moyen pour transformer les JSONs lus du fichier en instances des classes de la bibliothèque et aussi l’invrse. Ce processus s’appelle sérialisation (et l’inverse désérialization). On a vu une partie de cela aussi dans le devoir précédent.

Pour transformer le JSON lu dans un objet, on utilise le code suivant:

val deserializer = ObjectMapper().registerKotlinModule()
val json : String = readFromFile("chemin/vers/l'entree")
val program: AstObject = deserializer.readValue<AstObject>(json)

Pour obtenir le JSON à partir d’un objet, on utilise le code suivant:

val analysedProgram : AstObject = ... //le resultat de l'analyse

val serializer = ObjectMapper().writerWithDefaultPrettyPrinter() 
writeToFile("chemin/vers/la/sortie", serializer.writeValueAsString(analysedProgram))

On vous a ajouté dans le starter la déclaration des objets pour la sérialisation et la désérialisation, vous ne devez que les utiliser.

Situations d’analyse possibles​

Les types​

Vérifiez, chaque fois que vous rencontrez une expression, une valeur ou une variable, si son type existe. Sinon, traitez les deux cas: soit le type est l’un des types primitives (c’est-à-dire integer, float, string, symbol et float), le cas où vous pouvez les ajouter directement au plus proche tableau de symboles. S’il s’agit d’un type défini par le programmeur, assurez-vous qu’il a été vraiment défini avant l’utilisation.

attention

On a fait un changement dans la bibliothèque dès le devoir précédent: pour les types primitives integer et float, on a changé le nom du type (donc l’attribut typeName) avec I64, respectivement F64. Donc, une entrée dans le tableaux de symboles pour le type de nombre entier aura la forme:

...
"types" : {
        "I64" : {
          "@type" : "Integer",
          "itype" : "I64",
          "title" : "I64"
        },
        ...
      }
...

Les définitions​

Les définitions des variables, des fonctions et des nouveaux types n’apparaîtront pas dans l’AST après l’analyse. Les objets définis seront mis dans les tableaux de symboles associés.

Pour chaque objet défini, vérifiez qu’il ne soit pas déjà défini avant.

Pour les définitions des classes, vérifiez que le type de chaque champ existe et qu’un champ ne soit pas défini deux fois.

Pour les définitions des fonctions, vérifiez le type de chaque paramètre, aussi que l’existence de l’instruction return et le type de l’expression renvoyée.

Pour les définitions des listes, vérifiez le type des données et que les indices soient des nombres entières.

Les expressions​

Obtenez le type résultant du chaque expression. Evaluez ses membres et obtenez leur type. Pour la compatibilité des expressions, on a les règles suivantes:

  • les opérateurs logiques donnent toujours des résultats logiques, n’importe lequels soient leurs opérandes
  • une expression binaire conténant une expression ayant un type numérique (soit I64 soit F64) et une autre expression ayant un type avec des caractères (soit String soit Symbol) et un opérateur mathématique aura comme type résultant le type String.
  • une expression binaire contenant une expression ayant le type I64, le type F64 et un opérateur mathématique aura un résultat de type F64
info

Pour marquer la conversion d’une expression d’un type vers l’autre (par exemple, de I64 vers String), on utilise la classe Typecast. Le seul cas où on ne l’utilise pas, c’est quand on veut faire la conversion de I64 vers F64.

Faites les analyses corréspondantes pour chaque type d’expression:

  • pour les expressions binaires, vérifiez la compatibilité des opérandes et remplissez le champ typeName de l'instance avec le nom du type résultant
  • pour les appels des fonctions, vérifiez le type et le nombre de paramètres et remplissez, dans l’AST, l’instance avec le nom du type de retour
  • pour les accés dans les listes, vérifiez le type des données dans la liste et assurez-vous que l’indice soit aussi un nombre entier
  • pour les accés dans les classes, vérifiez l’existance et le type du champ

Les affectations​

Vérifiez, comme toujours, la compatibilité des types entre la quantité de la droite et celle de la gauche. Faites des transtypages (typecasts) si nécéssaire.

Conseils​

  1. Lisez les types possibles d’erreurs dans le repository des testes pour voir exactement les cas que vous devez traiter.
  2. Commencez avec les définitions. Remplissez les tableaux des symboles.
  3. Continuez avec les expressions. Traitez chaque type d’expression dans la manière corréspondante.
  4. Traitez premièrement les cas sans erreurs et ensuite ajoutez le traitement des erreurs.

Bonus (0.5p)​

Traitez aussi les cas de déclaration des variables sans préciser explicitement le type. Vous obtiendrez le type à partir de l’expression qu’on affecte à la variable. Les déclarations auront la forme suivante:

/* Type from value */

declare v = 90;

Dans ce cas, à la fin de l’analyse sémantique, on aura la variable avec le nom v, ayant le type de l’expression de la partie droite. Pour le code d’avant, l’AST analysé aura la forme suivante:

{
  "@type" : "Module",
  "block" : {
    "@type" : "Block",
    "statements" : [ {
      "@type" : "Assignment",
      "to" : {
        "@type" : "Identifier",
        "title" : "v",
        "typeName" : "I64",
        "line" : 3
      },
      "from" : {
        "@type" : "Value",
        "value" : "90",
        "typeName" : "I64",
        "line" : 3
      },
      "line" : 3
    } ],
    "line" : 3,
    "scope" : {
      "@type" : "SymbolTable",
      "variables" : {
        "v" : "I64"
      },
      "types" : {
        "I64" : {
          "@type" : "Integer",
          "itype" : "I64",
          "title" : "I64"
        }
      },
      "functions" : { }
    }
  },
  "line" : 3
}

Questions​

Si vous avez des questions concernant les devoirs, posez-les en publiant un problème sur le github repository pour les questions avec le format du titre [semantique]<titre de votre question>. Vous aurez besoin d'un compte github pour cela.

Attention

Ne postez pas de code. Cette action est considéré comme tentative de tricher et alors vous obtiendrez 0p pour le devoir.

Si vous souhaitez recevoir un e-mail lorsque des problèmes sont publiés ou lorsqu'il y a de nouveaux messages, accédez au repository pour les questions et cliquez sur Regarder.