Devoir 2 - SEG-2501 - Hiver 2005

Dû: le 7 mars à 12:00 (midi) (donné: le 15 février)  

Devoir 2 :  Analyse lexicale

1. [20 points]

Écrire des expressions régulières pour les langages suivants:

1. Toutes les chaînes de lettres minuscules qui contiennent les 5 voyelles (a e i o u) dans cet ordre. Chaque voyelle devrait apparaître seulement une fois dans chaque chaîne.
2. Toutes les chaînes de lettres minuscules qui contiennent les 5 voyelles (a e i o u) dans cet ordre. Chaque voyelle pourrait apparaître plusieurs fois dans une chaîne, entre autre, plusieurs occurrences au même endroit. Par exemple, la chaîne bghaaatrasdfeeqprilkohmoooozu est une chaîne acceptable.
3. Toutes les chaînes de zéros et uns avec un nombre de uns impair (parité impaire).

2. [50 points]

Nous considérons l'expression régulière suivante qui décrit un ensemble de chaînes sur l'alphabet {a, b}:

(a*|b*)*a(a|b)(a|b)*

1. Utilisez l'algorithme de Thompson (discuté en classe) pour dériver un automate non déterministe qui accepte cet ensemble de chaînes.
2. Transformez l'automate obtenu en un automate déterministe en utilisant l'algorithme discuté en classe.
3. Minimisez le nombre d'états de l'automate déterministe, c'est-à-dire, trouvez un automate minimal équivalent.
4. Utilisez Java ou C/C++ pour simuler l'automate déterministe. On peut se référer à l'algorithme 3.1 du livre de Aho. Le programme devrait répondre par "oui" si l'automate accepte la chaîne donnée, et par "non" autrement.
5. Utilisez Lex pour construire un analyseur lexical qui reconnaît les chaînes définies par l'expression régulière ci-haute. L'analyseur devrait écrire "oui" si l'automate accepte la chaîne donnée, et "non" autrement.

3. [30 points]

Construisez un analyseur lexical pour un sous-ensemble du langage C/C++ en utilisant Lex. L'analyseur doit être capable de compter le nombre d'identificateurs, de constantes (integer, float, double, scientific notation), de lignes, de définitions macro, de mots clés et de commentaires.Optionnellement (pour 5 points extra), l'analyseur devrait remplacer les noms de macros par leur définition macro (rencontrée précédemment).

Notes:

1. Votre program test peut lire d'un fichier en utilisant une commande de la forme: 

   test < myinputfile

2. Votre program test peut écrire sur un fichier en utilisant une commande de la forme: 

   test > myoutputfile

3. Votre program test peut lire d'un fichier et écrire sur un fichier en utilisant une commande de la forme: 

   test < myinputfile > myoutputfile

4. Une définition macro, dans sa forme la plus simple, ressemble à

   #define MacroName MacroValue

   où  macroName peut être une chaîne de lettres, chiffres et ponctuations, et Macrovalue peut être une chaîne, caractère, nombre ou ligne de texte. L'effet de la définition macro est l'association de la valeur avec le nom. Avant d'être compilé, le pré-processeur remplacera chaque occurrence de Macroname par la valeur associée. Par exemple,  

   #define PI 3.14159

   #define MESSAGE “Hello, World.”

   Cout << PI << endl;

   Cout << MESSAGE << endl;

   sera traduit par le pré-processeur en

   Cout << 3,14159 << endl;

   Cout << “Hello, World.” << endl;

5. Les mots clés suivants devraient être reconnus:

   bool, break, case, char, cin, class, const, continue, cout, do, double, else, endl, extern, false, float, for, goto, if, #include, int, long, main, namespace, new, public, return, short, sizeof, static, std, struct, switch, this, true, try, typedef, union, unsigned, using, void, while.

6. Des formats acceptables pour les constantes:

   ·         String: a string constant is a sequence of zero or more characters enclosed in double quotes. E.g., “Hello, World.\n”.

   ·         Character: a character constant is created by enclosing the character desired with single quotes (‘). E.g., ‘a’, ‘1’, ‘+’, ‘;’.

   ·         Integer: the simpliest way to write an integer constant is to just write the number. E.g., 23, 45, 101, 55.

   ·         Float: a float-point constant can be written in the following format.

   

   • Scientific: a scientific notation is in the following format:

     

Pour d'autres informations sur C/C++, svp. référer à un livre sur ces langages. Voici un programme exemple:

// A sample C++ program

#include <iostream>

#include <string>

using namespace std;

#define PI 3.14159

#define MESSAGE “Hello, World.”

double main()

{

int x, y, sum;

cout << PI << endl;

cout << MESSAGE << endl;

cin >> x;

cin >> y;

sum = x + y;

cout << x << “ + ” << y << “ = “ << sum << endl;

cout << 230.E+3 << endl;

cout << 230E3 << endl;

cout 23000.0 << endl;

cout << 2.3e5 << endl;

cout 0.23E6 << endl;

cout << .23e+6 << endl;

return 0.;

}