ufferedReadereadLineLANCOIRfsystemutnrrrintrintln
Planche 1

Inf 431 -- Cours 5
Analyse lexicale
http://jeanjacqueslevy.net
secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX,
01 69 33 34 67
http://www.enseignement.polytechnique.fr/informatique/IF

Planche 2

Plan


.65@percent
  1. Caractères -- chaînes de caractères
  2. Exceptions
  3. Entrées-Sortie
  4. Analyse lexicale
  5. Expressions régulières
  6. Filtrage

Planche 3

Caractères -- Chaînes de caractères (1/2)


Planche 4

Caractères -- Chaînes de caractères (2/2)


Planche 5

Conversion des caractères en entiers (1/2)


  0 1 2 3 4 5 6 7 8 9 a b c d e f
00 nul soh stx etx eot enq ack bel bs ht nl vt np cr so si
10 dle dc1 dc2 dc3 dc4 nak syn etb can em sub esc fs gs rs us
20 sp ! " # $ % & ' ( ) * + , - . /
30 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
40 @ A B C D E F G H I J K L M N O
50 P Q R S T U V W X Y Z [ \ ] _
60 ` a b c d e f g h i j k l m n o
70 p q r s t u v w x y z { & } ~ del

Attention: les vieux logiciels ne sont souvent prévus que pour les caractères de code ASCII.

Planche 6

Conversion des caractères en entiers (2/2)

Cf. Cours de majeure 2 (info): Codes et théorie de l'information.
Planche 7

Conversion des chaînes en entiers (1/2)


static int parseInt (String s) {
  int r = 0;
  for (int i = 0; i < s.length(); ++i)
    r = 10 * r + s.charAt(i) - '0';
  return r;
}

(En fait, calcul du polynôme s
0 10-1 + s1 10-2 + ··· + s - 2 10 + s - 1 par la méthode de Horner.)

Exercice 1 Le faire en base 16.

Que faire si la chaîne contient des caractères différents des chiffres décimaux?

Planche 8

Conversion des chaînes en entiers (2/2)


static int parseInt (String s) {
  int r = 0;
  for (int i = 0; i < s.length(); ++i) {
    if (!Character.isDigit (s.charAt(i)))
      throw new Error ("Pas un nombre");
    r = 10 * r + s.charAt(i) - '0';
  }
  return r;
}

Error est une classe d'erreurs dites ``irrattrapables''.
(Pas besoin de les mentionner dans les signatures des fonctions).

Planche 9

Rappel sur les exceptions (1/2)


static int parseInt(String s) throws  NumberFormatException {
  int r = 0;
  for (int i = 0; i < s.length(); ++i) {
    if (!Character.isDigit (s.charAt(i)))
      throw new NumberFormatException (s);
    r = 10 * r + s.charAt(i) - '0';
  }
  return r;
}

NumberFormatException est une sous-classe de la classe générale des Exception.
    java.lang.Object
       +----java.lang.Throwable
               +----java.lang.Error
               +----java.lang.Exception
                       +----java.lang.RuntimeException
                               +----java.lang.IllegalArgumentException
                                       +----java.lang.NumberFormatException
Planche 10

Rappel sur les exceptions (2/2)


public static void main (String[ ] args) {
  try {
    int x = parseInt (args[0]);
    System.out.println (x);
  } catch (NumberFormatException e) {
    System.err.println ("Mauvais argument: " + e.getMessage());
  } catch (ArrayIndexOutOfBoundsException e) {
    System.err.println ("Mauvais nombre d'arguments");
  }
}

Exceptions Þ Isolement du cas anormal.

Le cas normal s'écrit indépendamment du cas anormal.

A la place de
catch, on peut utiliser finally pour effectuer une opération finale s'il y a exception ou pas (cela évite la duplication de code).
Planche 11

Entrées-Sorties standards

Impression: System.out.print, System.err.print
  public static void main (String[ ] args) {
    BufferedReader in =
        new BufferedReader(new InputStreamReader(System.in));
    try {
      String s;
      while ((s = in.readLine()) != null) {
        int n = Integer.parseInt(s);
        System.out.println(n);
      }
    } catch (IOException e) {
      System.err.println(e);
    }
  }

l'Inexplicable System.in flot de bytes
idiome en InputStreamReader flot de caractères
Java BufferedReader flot de caractères tamponné

Exercice 2 Comment éviter d'écrire la clause
catch dans la fonction main?
Planche 12

Analyse lexicale (1/7)


Planche 13

Analyse lexicale (2/7)


Planche 14

Analyse lexicale (3/7)


Planche 15

Analyse lexicale (4/7)

Trois lexèmes (tokens) définis par des expressions régulières:



Identificateur = Lettre  (Lettre
|
Chiffre)*
Entier = Chiffre  Chiffre
*
Operateur = +
|
- | * | /
Lettre = a
|
b ... | z | A | B ... | Z
Chiffre = 0
|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Blancs = (
' ' | '\t' | '\r' | '\n')*

Exercice 3 Donner l'expression régulière pour les constantes réelles.

Exercice 4 Donner l'expression régulière pour les constantes chaînes de caractères de Java.

Exercice 5 Donner l'expression régulière pour les constantes caractères de Java.

A partir de cette description, on construit l'analyseur lexical.
Certains outils (lex) peuvent le faire automatiquement.

Planche 16

Analyse lexicale (5/7)


class Lexeme {

  final static int L_Nombre = 0, L_Id = 1, L_Plus = '+'L_Moins = '-',
        L_Mul = '*'L_Div = '/'L_ParG = '('L_ParD = ')',
        L_CroG = '['L_CroD = ']'L_EOF = -1;

  int nature;
  int valeur;
  String nom;

  Lexeme (int t, int i) { nature = t; valeur = i; }
  Lexeme (int t, String s) { nature = t; nom = s; }
  Lexeme (int t) { nature = t; }

  static Lexeme suivant () { ... }

Et une fonction suivant() qui va chercher le lexème suivant.
Planche 17

Analyse lexicale (6/7)


  static int c;    // caractère courant

  static Lexeme suivant() {
    sauterLesBlancs();
    if (Character.isLetter(c)) return new Lexeme (L_Id, identificateur());
    else if (Character.isDigit(c)) return new Lexeme (L_Nombre, nombre());
    else switch (c) {
    case '+'case '-'case '*'case '/':
    case '('case ')'char c1 = (char)c; avancer(); return new Lexeme (c1);
    defaultthrow new Error ("Caractère illégal");
  } }

  static void avancer() {
    try { c = in.read(); } catch (IOException e) { }
  }

  static void sauterLesBlancs() {
    while ( Character.isWhitespace (c) )
      avancer();
  }

Attention: revoir la fin de fichier.

Planche 18

Analyse lexicale (7/7)


  static String identificateur() {
    StringBuffer r;
    while (Character.isLetterOrDigit (c)) {
      r = r.append (c);
      avancer();
    }
    return r;
  }

  static int nombre() {
    int r = 0;
    while (Character.isDigit (c)) {
      r = r * 10 + c - '0';
      avancer();
    }
    return r;
  }

Quand il y a de nombreux mots-clé, on donne (comme pour les opérateurs) des numéros de lexème distincts. Chaque lexème identificateur est comparé à une table des mots-clé.
Planche 19

Rappel sur les tables

Table: Clés |® Valeurs
Clés = {
"int""static""if""while",  ... }
Valeurs = {
L_IntL_StaticL_IfL_While,... }

Représentations statiques:
Représentations dynamiques:
Planche 20

Expressions régulières (1/5)

Soit un alphabet S = {a, b, ...}.

Une expression régulière e représente un ensemble [[ e ]] de chaînes de caractères (de mots), un langage, défini par:

[[ a ]] = { a }
[[ e + e' ]] = [[ e ]] È [[ e' ]]
[[ e e' ]] = [[ e ]] [[ e' ]] = {xy
|
xÎ e, y Î e' }
[[ e
* ]] = [[ e ]]* = { e } È e È e2 È ··· È en È ···
[[ (e) ]] = [[ e ]]

e est le mot vide (de longueur 0).
Parfois, on écrit e
|
e ' au lieu de e + e '.

Exemples


(a+b)
*abb est l'ensemble des mots sur a et b finissant par abb
(a+b)
*w(a+b)* est l'ensemble des mots contenant w.
Par abus de notation, S
* est l'ensemble des mots sur S
Planche 21

Expressions régulières (2/5)

Posons [[ 0 ]] = Ø, [[ 1 ]] = { e } et e £ e' pour e + e' = e'

Les 13 lois suivantes sont vérifiées et définissent une algèbre de Kleene.
(1) e + f = f + e
(2) e + (f + g) = (e + f) + g
(3) e + 0 = e
(4) e(fg) = (e f) g
(5) 1 e = e 1 = e
(6) e (f + g) = e f + e g
(7) (e + f) g = e g + f g
(8) 0 e = e 0 = 0 demi-anneau
(9) e + e = e
(10) 1 + e e * = e *
(11) 1 + e * e = e *
 
(12) f + e g £ g Þ e*f £ g (12') e g £ g Þ e*g £ g
(13) f + g e £ g Þ fe* £ g (13') g e £ g Þ ge* £ g

12-12' et 13-13' sont équivalents.

Pas de théorie équationnelle finie. Pas de formes normales.
Planche 22

Expressions régulières (3/5)

Exercice 6 Montrer e = e' ssi e £ e' £ e.

Exercice 7 Montrer e £ e' ssi e + f = e'.

Exercice 8 Montrer les équations suivantes:
a* a* = a *
a** = a *
(a *b)* a * = (a + b)*
a (ba)* = (ab)* a
a * = (aa)* + a (aa)*

Exercice 9 Montrer ces équations en n'utilisant que les règles (1-13).

Pour la première: 1 + a a
* = a* par A10. D'où a a* £ a*. D'où a* a* £ a* par A12'.
Réciproquement, a
* a* = (1 + a a*) a* par A10. Donc a* a* = a* + a a* a* par A7 et A5. D'où a* £ a* a*. Etc.

Cf. Les 2 cours de majeure 1 (info); livre de Kozen (Automata and Computability)

Planche 23

Expressions régulières (4/5)

Les commandes d'Unix contiennent souvent des expressions régulières. Toutes ont leur syntaxe propre. En général, elles essaient d'avoir les expressions régulières les plus déterministes possible, sauf awk et perl. Par exemple,
% ls *.java .??*
liste les fichiers de suffixe .java ou de plus de 3 caractères commençant par un point (.).

Exemple

Planche 24

Expressions régulières (5/5)


% sed -e 's/^  *$//'
remplace les lignes blanches par des lignes vides sur l'entrée standard.
% grep 'Contrôle' *
imprime toutes les lignes contenant le mot Contrôle dans tous les fichiers du répertoire courant.
% grep -i 'analyse.*lexicale' *.tex
imprime toutes les lignes contenant le mot analyse suivi du mot lexical dans tous les fichiers de suffixe .tex. (L'option -i signifie que majuscules et minuscules sont confondues)
% grep '^ *$' a3.tex | wc -l
compte le nombre de lignes blanches dans le fichier a3.tex

Exemple

Planche 25

Filtrage (1/3)

String Matching: algorithme naif

Complexité en O(mn)m = |s|, n =|t|


Planche 26

Filtrage (2/3)

Filtrage linéaire: [Knuth-Morris-Pratt]

Complexité en O(m+n)m = |s|, n =|t|


Planche 27

Filtrage (3/3)

Filtrage rapide [Boyer-Moore] en procédant de la droite vers la gauche.

Complexité en O(mn)m = |s|, n =|t|
souvent sublinéaire.


Planche 28

Exercices

Exercice 10 En se servant d'une pile, faire une calculette HP (avec la notation polonaise suffixe).

Exercice 11 Modifier l'analyseur lexical pour inclure des commentaires comme en Java, ou en C.

Exercice 12 Idem avec les constantes chaînes de caractères.



This document was translated from LATEX by HEVEA.