Traduction Flashcards

1
Q

Définition d’une passe

A

En compilation, une passe correspond à une lecture des données afin de les transformer.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Compilateur en trois passes : passe 1

A

Lecture du texte source par l’analyseur lexical et l’analyseur syntaxique. L’arbre abstrait est construit pendant l’analyse syntaxique.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Compilateur en trois passes : passe 2

A

Lecture des données (arbre généré à la fin de la passe 1) durant l’analyse sémantique (après analyse syntaxique). L’arbre généré à la fin de la passe 1 est décoré (on ajoute des informations aux éléments de cet arbre), et la TDS est créée et remplie.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Compilateur en trois passes : passe 3

A

Le générateur de code parcourt les données, c’est-à-dire maintenant l’arbre abstrait décoré et la TDS, afin de produire le code cible.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Exemples de contrôles sémantiques

A
  • variable déclarée avant d’être utilisée
  • pas de double déclaration (un même nom de variable n’est pas utilisé pour deux déclarations différentes, sauf si ces déclarations ont lieu dans des blocs différents).
  • types cohérents lors des opérations (ex : on n’affecte pas une chaîne de caractères à une variable déclarée comme étant de type entier).
  • paramètres passés à une fonction de même type que les paramètres définis lors de la déclaration de la fonction.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Espace de noms

A

Ensemble de ce qui est désignable dans un contexte donné par une méthode d’accès faisant usage de noms symboliques. Autrement dit, cela désigne un lieu abstrait (méthode, bloc, fichier…) conçu pour accueillir un ensemble de termes (variables ayant un nom défini).
Une variable est unique dans son espace de noms.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Région ou bloc

A

Une région dans un programme informatique correspond à l’intérieur d’une fonction, ou d’une structure, ou encore d’un fichier.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Pile des régions ouvertes

A

Pile utilisée lors de l’analyse sémantique (ou syntaxique, selon la méthode utilisée). On associe à chaque bloc dans le programme un entier unique. En parcourant l’arbre abstrait, dès qu’une région s’ouvre (ex : une accolade ouvrante), alors on empile son numéro dans cette pile. Dès que la région est refermée, le sommet de la pile est dépilé. Cela permet de déterminer d’une part le nombre d’imbrications maximal dans le programme ; d’autre part, on connaît le nombre d’imbrications de chaque région du programme.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

AST (abstract syntax tree)

A

Pour faciliter l’analyse sémantique, on va simplifier et transformer l’arbre syntaxique “pur”. Cette simplification a lieu pendant l’analyse syntaxique, où l’on remplace et modifie en temps réel les branches de l’arbre en suivant un certain nombre de règles de transformation (appelées actions sémantiques).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Rappel sur les expressions régulières :
a+
a*
a?

A

a+ => “1 ou plusieurs a”
a+ => “0, 1 ou plusieurs a”
a? => “0 ou 1 a”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Action sémantique pour ANTLR : principe de base

A

→ ^(NOEUD feuille1 feuille2 …)

Cela remplace la branche courante par une branche ayant pour nœud NOEUD et les feuilles feuille1, feuille2, …

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Action sémantique pour ANTLR : renommer

A

program : declaration + → ^(ROOT declaration+) ;

On renomme le nœud “program” en “ROOT”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Action sémantique pour ANTLR : supprimer

A

variable : type ID ‘;’ → ^(DECL type ID) ;

On supprime le non-terminal ‘;’.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Action sémantique pour ANTLR : simplifier et réarranger

A

fonction : type ID ‘(‘ (formalParam (‘,’ formalParam)) ? ‘)’ block → ^(FONC type ID formalParam block) ;
On supprime les parenthèses et les virgules, et on regroupe les paramètres pour obtenir un arbre simplifié.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

3 manières de réaliser un contrôle sémantique

A
  • Les règles d’inférence
  • Les grammaires attribuées
  • L’utilisation de l’AST
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Contrôles sémantiques statiques

A

Essentiel des contrôles effectués. Ils se déroulent à la compilation.
Ex : x/0 (écrit comme ça)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Contrôles sémantiques dynamiques

A

Effectués à l’exécution, ils nécessitent l’ajout de code assembleur supplémentaire dans le programme cible.
Ex : x/y avec y qui diminue jusqu’à valoir 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Les 2 branches de l’AST à l’issue de l’analyse syntaxique

A
  • Une branche déclaration (chacune des variables déclarées dans le programme y est présente)
  • Une branche instruction (affectations de variables, utilisations de fonctions…)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Décoration de la branche déclaration de l’AST

A

Méthode qui associe des informations à chaque variable (type d’identificateur, type de variable, bloc de déclaration, portée dans le programme…)
Inconvénients : arbre lourd et difficile à lire par le générateur de code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Utilisation d’une table des symboles (TDS)

A

Méthode dans laquelle le générateur ne se sert plus de la branche déclaration. Il la remplace par une TDS, créée et remplie au cours de l’analyse sémantique (on peut aussi commencer le remplissage durant l’analyse syntaxique).
En général, une TDS par région puis regroupement en une TDS globale.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Contenu de la TDS pour un identificateur

A
  • type, place mémoire occupée, et les bornes (si tableau)
  • déplacement (différence d’adresses mémoires) nécessaire pour accéder à la variable depuis la base de la pile ou de la fonction
  • visibilité et portée (numéro de bloc, nombre d’imbrications)
  • arguments et leur type, type de retour (si fonction)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Définition d’un processus

A

Programme en cours d’exécution. Plus précisément :

  • un ensemble d’instructions à exécuter, souvent chargé depuis une mémoire de masse (disque dur) vers la mémoire vive (RAM)
  • un espace d’adressage en mémoire vive pour stocker les données de travail. Cet espace se divise en deux parties principales : la pile d’exécution (call stack) et le tas (heap).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Pile d’exécution

A

Sert à enregistrer des informations relatives à une fonction en train d’être exécutée et la trace de l’endroit où chaque fonction active doit retourner à la fin de son exécution (l’adresse de retour).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Tas

A

Utilisé pour allouer dynamiquement de l’espace mémoire à la demande du programme (malloc), par opposition à la pile qui est gérée automatiquement lors d’un appel de sous-routine ou de fonction. Il sert souvent à stocker des données de plus grande taille (tableaux, structures, et objets).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Cas des tableaux pour la mémoire

A
  • Tableaux statiques (taille fixe, connue à la compilation) : pile
  • Tableaux dynamiques (taille fixe, connue à l’exécution) : pile
  • Tableaux flexibles (taille variable à l’exécution) : tas

Dans tous les cas, le nombre de dimensions du tableau est connu à la compilation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Type statique vs type dynamique

A
  • Statique : type associé à la variable au moment de la compilation
  • Dynamique : type associé aux valeurs pendant l’exécution
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Analyseur lexicale

A
  • reconnaître les unités lexicales (ou tokens) qui sont les mots du langage et les présenter à l’analyseur syntaxique
  • éliminer les commentaires, tabulations, espaces…
  • afficher les erreurs lexicales (caractère inconnu)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Analyseur syntaxique

A
  • vérifier que la phrase en entrée est bien formée (conforme à la syntaxe du langage définie par une grammaire)
  • reconnaître les unités syntaxiques décrites par une grammaire (déclarations, affectations, instructions…)
  • détecter les erreurs syntaxiques
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Définition d’un compilateur

A

Le compilateur lit le code source fourni ; le fichier résultat, contenant le code machine (appelé aussi fichier cible), est exécutable une fois pour toute.
Bon compilateur : optimisations, rapide, gestion mémoire, signalement des erreurs.

30
Q

Définition d’un interpréteur

A

L’interpréteur ne crée pas de fichier cible. Il interprète et exécute au fur et à mesure les instructions du programme.

31
Q

Avantage de l’utilisation d’un lexique dans un compilateur

A

C’est plus efficace, à manipuler et à mémoriser :

  • plus facile de manipuler des codes entiers (int) que des chaînes de caractères.
  • éviter de répéter plusieurs fois la même chaîne de caractères dans la sortie de l’analyseur lexical.
32
Q

Pile d’un automate d’analyse syntaxique ascendante

A

Une liste des états où l’automate est déjà passé. Elle est vide au départ. On ajoute l’unité lexicale courante dans la pile. Si on reconnaît que la pile se termine par le membre droit d’une règle, on remplace ce dernier par le membre gauche de la règle.
Si le texte se réduit au marqueur de fin $ et si la pile se réduit à l’axiome, le texte était correct.

33
Q

Points communs et différences entre les méthodes LR(0), SLR(1), LR(1) et LALR(1)

A

Même construction de la table sauf pour les états de réductions :

  • LR(0) => on réduit tous les terminaux
  • LR(1) => on ne réduit que pour les terminaux appartenant au contexte, le but étant de limiter les risques de conflit
  • SLR(1) => on ne réduit que les terminaux appartenant aux suivants du non-terminal
  • LALR(1) => fusion d’états LR(1)
34
Q

Justifiez l’écriture de LR(0)

A

L => Left to right scanning
R => Right most derivation
0 => on a besoin d’aucune unité lexicale pour prendre la décision de réduction. (cas général LR(k) => on utilise k symboles du mot à analyser pour faire la prédiction)

35
Q

Signification LALR

A

Look-Ahead Left-to-right Rightmost derivation

36
Q

Signification SLR

A

Simplified Left-to-right Rightmost derivation

37
Q

Pourquoi introduit-on des symboles de prévision dans l’automate LR(0) qui devient alors un automate LR(1) ?

A

Pour supprimer certains conflits, notamment les conflits lecture-réduction.

38
Q

Définissez ce qu’est une grammaire récursive gauche. Une telle grammaire peut-elle être LL(1) ? LR(0) ?

A

Une grammaire est récursive gauche s’il existe une variable A telle que A =>+ Aa
Une telle grammaire ne peut pas être LL(1) mais peut être LR(0). En effet, une grammaire récursive gauche n’est LL(k) pour aucun k.

39
Q

Quand faut-il construire le lexique ?

A

Le lexique doit être conçu lors de l’analyse lexicale, avant l’analyse syntaxique.

40
Q

Quelle est la faiblesse de l’analyse SLR(1) ?

A

Elle enlève quelques conflits de lecture/réduction mais n’enlève pas tous les conflits.

41
Q

Comment l’analyse LR remédie à la faiblesse de l’analyse SLR(1) ?

A

Elle donne un contexte qui évite certains conflits supplémentaires.

42
Q

Algorithme de fermeture LR(0)

A

Soit I un ensemble d’items de G. Fermeture(I), est un ensemble d’items construits à partir de I tel que :

  • Placer chaque item de I dans Fermeture(I)
  • Si A → α•Bβ ∈ Fermeture(I) et B → γ, alors ajouter B → •γ à Fermeture(I) (sauf si déjà dedans)
  • Itérer jusqu’à ne plus trouver d’items à ajouter
43
Q

Algorithme de fermeture LR(1)

A

Calcul de la fermeture de I :

  • Initialisation : [S’→•S, [$]]
  • Si [A→α•Bβ, [a]] est dans I (avec B→γ) alors, pour tout terminal b appartenant aux premiers de (βa), ajouter [B→•γ, [b]] à Fermeture(I)
44
Q

Peut-il y avoir des conflits lecture/lecture dans une table d’analyse ascendante ?

A

Non, pas de conflit lecture/lecture pour les automates déterministes.

45
Q

De quel problème dans la conception de la grammaire les conflits réduction/réduction sont-ils synonymes ?

A

Un conflit de réduction/réduction se produit s’il existe deux règles ou plus qui s’appliquent à la même séquence d’entrée. L’erreur est une ambiguïté : il y a plus d’une façon d’analyser un seul mot dans une séquence.

46
Q

Trois propriétés permettant de décider qu’une grammaire n’est pas LL(1)

A
  • Récursivité à gauche
  • Grammaire ambiguë
  • Grammaire non factorisée à gauche
47
Q

Ecrivez une instruction C dans laquelle le compilateur signalerait une erreur lexicale, une erreur syntaxique et une erreur sémantique

A
int main(){
        int a= (void)3a
}
(Erreur lexicale car 3a n’est pas un lexème correct, erreur syntaxique car il manque le ‘;’ et sémantique car on a des types complètement différents).
48
Q

3 exemples d’erreur sémantique statique

A
  • x/0 avec 0 écrit comme ça
  • Erreur de cohérence de types int = char
  • Variables mal déclarées (portée et visibilité)
49
Q

3 exemples d’erreur sémantique dynamique

A
  • x/y dans une boucle avec y diminuant jusqu’à valoir 0
  • Erreur d’allocation mémoire
  • Dépassement
50
Q

Expliquez : LR(0) ⊆ SLR(1) ⊆ LALR(1) ⊆ LR(1)

A

LR(1) est le plus générique possible, SLR(1) est le simple LR(1), on prend en compte que les suivants, et LALR(1) va réduire la taille du LR(1).

51
Q

Item de l’automate LR(1)

A

Un item d’une grammaire G est une production de G avec un marqueur (noté•) repérant une position dans la partie droite.
Dans le cas d’une analyse LR(1), on ajoutera à la fin les contextes.

52
Q

A quoi sert un ramasse-miettes (Garbage Collector) ?

A

Il sert à déverrouiller et vider la mémoire qui n’est plus utilisée.

53
Q

Pour un compilateur multi-passes, la sortie de la passe k est utilisé comme entrée de la passe k+1. (V/F)

A

Vrai

54
Q

Une grammaire ambiguë ne peut être ni LL(1), ni SLR(1). (V/F)

A

Vrai

55
Q

Toute grammaire LR(0) est SLR(1). (V/F)

A

Faux (cependant l’inverse est vrai)

56
Q

Il existe 3 types de conflits en analyse ascendante : lecture - reduction, reduction-réduction, et lecture-lecture. (V/F)

A

Faux (lecture-lecture est impossible car la grammaire est correcte sinon pas d’analyseur)

57
Q

Un interprète est un logiciel exécutant le code objet d’un programme source. (V/F)

A

Faux (le code objet est le code obtenu après la compilation, il n’y en a pas pour les interpréteurs. C’est une suite d’instructions en langage binaire (0 et 1), uniquement compréhensible par l’ordinateur qui va l’utiliser pour exécuter le programme.)
Attention : Java n’est pas interprété il est compilé en bytecode puis interprété.

58
Q

La table des symboles est une structure indispensable dans l’écriture d’un compilateur. (V/F)

A

Faux (il est possible de s’en passer, mais alors la compilation est plus longue, car il faut aller rechercher chaque information. C’est une fonction accélératrice de compilation, dont l’efficacité dépend de la conception)

59
Q

La construction de l’arbre abstrait s’effectue après l’analyse syntaxique. (V/F)

A

Faux (elle a lieu pendant l’analyse syntaxique)

60
Q

Ensemble des non-terminaux produisant le mot vide

A

Pε(G) = {X∈N | X →* ε}

61
Q

Premier(α)

A

Premier(α) =
{x∈T | α →* xw} si α∈N
{a} si α=aβ avec a∈T

62
Q

Suivant(A)

A

Suivant(A) = {a∈(T∪{$}) | S →* αAaβ}

63
Q

Calcul de Suivant(A)

A
  • Suivant(X) = {$} si X=S et ∅ sinon
  • Pour chaque règle A → αBβ où B∈N et α,β∈(N∪T)* :
    Suivant(B) = Suivant(B)∪Premier(β)
    Suivant(B) = Suivant(B)∪Suivant(A) si β →* ε
  • Recommencer étape précédente jusqu’à stabilisation
64
Q

Remplissage de la table Action (terminaux) LR(0)

A
  • S’→S• ∈ I alors Action[I, $] = “accepter”
  • X→β• ∈ I alors Action[I, a] = “réduire par X→β” (r+n° règle) ∀a∈{T∪$}
  • X→α•aβ ∈ I alors Action[I, a] = “lire + aller à l’état Iᵣ” où Iᵣ = transition(I, a)
65
Q

Remplissage de la table Transition (non-terminaux) LR(0)

A

Si dans l’automate, Iᵣ = transition(I, X) alors Transition[I, X] = Iᵣ

66
Q

Remplissage de la table Transition (non-terminaux) SLR(1)

A

Même chose que pour LR(0)

67
Q

Remplissage de la table Action (terminaux) SLR(1)

A

Même chose que pour LR(0) sauf pour X→β• ∈ I avec X ≠ S :

Action[I, a] = “réduire par X→β” ∀a∈Suivant(X)

68
Q

Remplissage de la table Transition (non-terminaux) LR(1)

A

Même chose que pour LR(0)

69
Q

Remplissage de la table Action (terminaux) LR(1)

A
  • S’→S•, [$] ∈ I alors Action[I, $] = “accepter”
  • X→β•, [a] ∈ I alors Action[I, a] = “réduire par X→β”
  • X→α•aβ, [b] ∈ I alors Action[I, a] = “lire + aller à l’état Iᵣ” où Iᵣ = transition(I, a)
70
Q

Analyseur LALR(1)

A

Dans la table LR(1), regroupement des états ayant le même noyau (mais des contextes potentiellement différents)

71
Q

Chainage statique et dynamique

A

Chainage dynamique : lien appelant-appelé

Chainage statique : vers le bloc de déclaration