Remonter Suivant

1  Le filtre mgrep

Le filtre mgrep imprime les lignes de l'entrée standard qui contiennent un certain motif. Ce dernier correspond à l'ensemble des mots d'un langage associé à une expression rationnelle. Le motif recherché est donné dans la ligne de commande sous la forme d'un paramètre représentant une expression rationnelle. Le filtre mgrep doit donc reconnaître le langage associé pour effectuer la recherche du motif.

Pour toute expression rationnelle, il existe un unique (au nom des états près) automate fini déterministe minimal reconnaissant le langage associé. La construction d'un tel automate passe par trois phases :
  1. La construction d'un arbre de syntaxe abstraite associé à l'expression rationnelle.
  2. La construction d'un automate fini déterministe à partir de cet arbre.
  3. La minimisation de cet automate déterministe.
Nous allons coder ces phases bien que la dernière ne soit pas impérative à l'implantation du filtre mgrep.

La grammaire des expressions rationnelles utilisées par la commande mgrep est donnée par la figure 1. C'est une version très simplifiée de celle utilisée par grep. 
expression ::= expression_concatenation '|' expression || expression_concatenation
expression_concatenation ::= expression_repetition expression_concatenation 
                             || expression_repetition
expression_repetition ::= expression_simple '*' || expression_simple
expression_simple ::= '(' expression ')' || car_non_speciaux || intervalle
car_non_speciaux ::= tout caractere sauf '|', '*', '[', ']', '.' || '\|' || '\*' 
                     || '\[' || '\]' || '\.'
intervalle ::= '.' || '[' liste ']' || '[^' liste ']' || '[' liste '-]' 
               || '[^' liste '-]'
liste ::= non_moins liste1 
liste1 ::= non_fermant liste1
non_moins ::= tout caractere sauf '-'
non_fermant ::= tout caractere sauf ']'

Figure 1 : Grammaire des expressions rationnelles de mgrep

Notre filtre mgrep va prendre une chaîne de caractères codant une expression rationnelle en paramètre depuis la ligne de commande. Dans un premier temps, cette chaîne va être convertie en un arbre binaire dénommé arbre de syntaxe abstraite.

Remonter Suivant