Université Bordeaux 1 UFR Mathématiques et Informatique
Session de février 1998 Epreuve de J.Bétréma

Maîtrise d'informatique
Compilation

Durée : 3 heures
Tous documents interdits.
Les exercices sont indépendants.

Exercice 1

Un corrigé est disponible.

Dans un document LaTeX, une instruction de mise en page est appelée macro, elle commence par une contre-oblique (backslash chez les anglo-saxons) et sa portée est indiquée par une paire d'accolades. Dans un document HTML, une instruction de mise en page est appelée balise, elle est encadrée par les signes < et >, et sa portée est indiquée par une balise fermante (de même nom mais précédé d'une oblique).

En particulier une section d'un document LaTeX est indiquée par : \section{Titre de la section} tandis qu'en HTML on utilise : <H1>Titre de la section</H1> .

On souhaite écrire un analyseur lexical (dans le format reconnu par lex) qui transforme les annonces de sections d'un document LaTeX en annonces de sections HTML ; le reste du document n'est pas modifié.

  1. Est-ce possible si le titre de la section comporte lui-même des instructions de mise en page ? Justifier brièvement mais précisément votre réponse.

  2. Ecrire le programme dans le cas où le titre de la section est un texte ordinaire, sans indication de mise en page.
Note : un programme lex est par nature assez peu lisible ; il est donc impératif que celui figurant sur votre copie soit écrit sans aucune rature (c'est le rôle des brouillons) et présenté aussi clairement que possible. La réponse demandée est simple et courte : évitez de perdre du temps dans des complications qui indiqueraient que vous ne maîtrisez pas la construction d'un analyseur lexical simple.

Exercice 2

Un corrigé est disponible.

Sachant que la grammaire C comporte les règles suivantes :

expression -> ... -> ... | unaire
unaire     -> * unaire | postfixe
postfixe   -> postfixe ++ | primaire
primaire   -> identificateur | ( expression )
quel est l'arbre de dérivation de l'expression *p++ ? Cette expression est-elle équivalente à (*p)++ ou à
*(p++) (on donnera les arbres de dérivation de chacune de ces expressions) ? Commenter brièvement.

Pour récrire chacun des trois derniers symboles (unaire, postfixe, primaire) on a le choix entre deux règles : quels sont les choix qui peuvent être faits de façon déterministe lors d'une analyse descendante
LL(1) ?

Exercice 3

Un corrigé est disponible.

Soit G la grammaire :

    E -> T + E | T
    T -> F * T | F
    F -> ( E ) | id
obtenue à partir de la grammaire ETF en inversant l'ordre des symboles autour des opérateurs. On rappelle en annexe l'automate utilisé pour l'analyse ascendante de la grammaire ETF (dans le format produit par bison) ; dans les états 4 et 10 il y a un conflit décalage/réduction, résolu en examinant Suivant (expr).
  1. Construire l'automate analogue pour G ; utiliser la même présentation que dans l'annexe, ou toute autre qui soit claire et concise ; respecter l'algorithme de numérotation des états employé par bison.

  2. Quels sont les états pour lesquels l'automate comporte des conflits décalage/réduction ?

  3. Calculer la fonction Suivant pour chacun des trois symboles non-terminaux. Les conflits précédents peuvent-ils être résolus en examinant cette table ? autrement dit G est-elle SLR(1) ?

  4. Soit une somme de n termes x = t1 + t2 + ... tn. Quelle est la différence entre l'arbre de dérivation de x dans la grammaire ETF et dans G ?

    Après lecture et réduction de t1 par un analyseur syntaxique ascendant, quel est l'état de la pile si la grammaire utilisée est a) ETF b) G ? Même question après lecture et réduction de + t2, + t3, etc.

    En déduire une différence fondamentale de comportement entre les analyseurs ascendants pour les grammaires ETF et G.

  5. La grammaire C comporte la règle suivante :
    liste-instructions -> liste-instructions instruction | instruction
    Que se passe-t-il si l'on remplace cette règle par :
    liste-instructions -> instruction liste-instructions | instruction ?

    Note : cette question est la suite logique de la précédente.

Exercice 4

Attention : cet exercice est destiné à ceux qui s'ennuient après avoir résolu soigneusement les trois exercices précédents ; il est nettement plus difficile que l'exercice 1. Perdre du temps à développer les détails d'une solution dont le principe n'est pas compris ne rapporte aucun point.

Dans une formule mathématique d'un document TeX, un indice est indiqué par le caractère _ (souligné, ou underscore chez les anglo-saxons) ; par exemple x_i désigne xi ; si l'indice n'est pas réduit à un seul caractère, il faut employer des accolades : x_{i+1} désigne xi+1 ; la notation x_{i} est bien sûr autorisée.

Dans un document HTML, un indice est indiqué par la balise <SUB> obligatoirement suivie de la balise fermante </SUB> ; ainsi xi s'écrit x<SUB>i</SUB> et xi+1 s'écrit x<SUB>i+1</SUB> .

Dans les deux langages les indices peuvent être emboîtés sans limitation (bien que la lisibilité du résultat puisse en souffrir). Le but de l'exercice est de construire un analyseur syntaxique qui effectue une conversion du format TeX vers le format HTML pour la spécification des indices (et rien d'autre).

  1. Ecrire une grammaire non ambiguë G qui engendre les expressions mathématiques TeX décrites ci-dessus. Attention : cette grammaire n'a rien à voir avec la grammaire ETF, car opérateurs et parenthèses sont (dans ce modèle simplifié) des caractères comme les autres.

  2. Donner les arbres de dérivation de y+x_i+1 et de x_{i+1}+y dans G.

  3. Ecrire un analyseur lexical (dans le format reconnu par lex) et un analyseur syntaxique (dans le format reconnu par yacc) qui transforment les formules TeX en formules HTML. Attention : l'analyseur syntaxique doit utiliser évidemment la grammaire G donnée en réponse à la question 1 ; si celle-ci n'est pas raisonnable, la réponse à la question 3 est vouée à l'échec et ne rapporte aucun point.