Aflex 1.5 et Ayacc 1.3.0

Par Stephane Carrez2021-12-19 20:59:00

Aflex est un outil de génération d'analyseur lexical similaire à l'outil Unix lex (1). Ayacc est un générateur d'analyseur syntaxique pour Ada dans le style de yacc (1). De nouvelles versions sont disponibles pour ces deux outils et elles apportent un certain nombre de petites améliorations à ces outils écrits en Ada 83 dans les années 1990 par John Self, David Taback et Deepak Tolani de l'Université de Californie, Irvine.

Aflex Version 1.5.2021

La nouvelle version apporte les modifications suivantes :

Correction d'un crash lorsque le fichier du scanner utilise des caractères dans la plage 128..255,
Correction de divers avertissements de compilation,
Utilisation de gprbuild pour construire Aflex et prise en charge de alr,
Réduction du nombre d'avertissements de compilation de style dans le code généré

Pour installer Aflex, vous pouvez utiliser l'outil Alire en utilisant:

  alr get aflex
  cd aflex_1.5.2021_33198b8f
  alr build

Vous pouvez également le construire et l'installer aussi facilement avec les commandes suivantes:

  git clone https://github.com/Ada-France/aflex.git
  cd aflex
  make
  sudo make install

Vous pouvez également installer le package Debian suivant: aflex_1.5.2021.

Ayacc Version 1.3.0

La version Ayacc apporte un peu plus d'améliorations:

Nouvelle option -C pour désactiver la génération de la procédure yyclearin,
Nouvelle option -E pour désactiver la génération de la procédure yyerrok,
Nouvelle option -D pour écrire les fichiers générés dans le répertoire spécifié,
Nouvelle option -k pour conserver la casse des symboles grammaticaux,
Correction de divers avertissements de compilation,
Génération de constantes pour les tableaux shift, reduce et goto,
Meilleur typage fort dans les tables d'état générées,
Réduction du nombre d'avertissements de compilation de style dans le code généré

Pour installer Ayacc avec l'outil Alire, utilisez:

  alr get ayacc
  cd ayacc_1.3.0_9b8bf854
  alr build

Vous pouvez également le construire et l'installer aussi facilement avec les commandes suivantes:

  git clone https://github.com/Ada-France/ayacc.git
  cd ayacc
  make
  sudo make install

Vous pouvez également installer le paquet Debian suivant: ayacc_1.3.0.

Développement avec Aflex et Ayacc

Aflex est un outil pour générer un analyser lexical. Ayacc utilise une grammaire de type BNF pour générer un analyseur syntaxique Ada pour cette grammaire. Ces deux outils sont étroitement liés. Tout d'abord, le rôle du scanner est d'identifier les symboles définis dans la grammaire. Deuxièmement, l'analyseur utilisera le scanner pour identifier les symboles pendant qu'il analyse le contenu.

L'analyseur généré fournit une procédure principale YYParse qui est le point d'entrée pour analyser le contenu. Pour cela, il appelle la fonction YYLex fournie par le scanner généré.

Le modèle de développement est d'écrire un fichier pour le scanner décrivant les symboles lexicaux et la grammaire dans la spécification de type BNF. Aflex lit le fichier de description lexical et génère le scanner. Ayacc lit le fichier de grammaire et produit l'analyseur. Le scanner et l'analyseur sont composés de plusieurs paquetages Ada et ils sont utilisés les uns par les autres pour échanger certains types et opérations.

Mod&#E8;le de d&#E9;veloppement Aflex et Ayacc

Ayacc et Aflex ont besoin d'un certain nombre de types Ada pour leur travail et les types importants sont contrôlés par la grammaire Ayacc. Ils partagent également certaines variables globales pour contenir le symbole qui a été analysé ou pour décrire l'état actuel de l'analyseur. La liste des symboles possibles est générée par Ayacc dans le paquetage <Parser>_Tokens et représentée par le type Token.

package <Parser>_Tokens
  type Token is (T_AND, T_OR, T_STRING, ...);
end <Parser>_Tokens ;

Aflex va générer la fonction YYLex qui retourne un type Token :

  function YYLex return <Parser>_Tokens.Token;

De son côté, Ayacc génère la procédure YYParse dans le corps du paquetage. C'est à vous et à votre grammaire de décider si cette procédure doit être exportée telle quelle ou encapsulée dans une autre opération.

  procedure YYParse;
``` 

## Ecrire un scanner avec Aflex

Le fichier du scanner décrit les expressions régulières et
le code Ada qui est exécuté lorsqu'un texte d'entrée correspond à l'expression régulière.
Le fichier du scanner contient essentiellement trois zones séparées par une ligne contenant uniquement `%%`.
La disposition globale est la suivante:

```[C]
définitions
%%
règles
%%
Code utilisateur

Les extraits de scanner ci-dessous sont tirés d'un parseur CSS écrit en Ada, le fichier du scanner est css-parser-lexer.l. Je souligne ici quelques parties intéressantes de ce scanner.

La section des définitions contient un ensemble d'options de configuration qui indique au générateur Aflex comment générer le scanner Ada final. Premièrement, la directive %unit permet de contrôler le nom du paquetage Ada utilisé par le scanner final. Ce paquetage peut être un paquetage enfant ce qui donne beaucoup de flexibilité et de contrôle sur l'organisation du programme.

%unit CSS.Parser.Lexer
%option case-insensitive
%option yylineno

Le %option case-insensitive indique à Aflex d'ignorer la casse lors de la génération du scanner et le %option yylineno lui demande de maintenir une variable yylineno qui indique le numéro de la ligne actuelle. Il maintient également la variable yylinecol qui indique le numéro de colonne du symbole actuel. Ceci est utile pour garder une trace de la position du symbole afin de l'indiquer lorsqu'une erreur se produit.

Parce que l'écriture d'expressions régulières est difficile, Aflex vous permet de créer des définitions nommées où vous donnez un nom à une expression régulière. Une expression régulière peut utiliser une autre définition, simplifiant ainsi la création d'expressions régulières complexes.

h               [0-9a-f]
nonascii        [\240-\377]
unicode         \\{h}{1,6}(\r\n|[ \t\r\n\f])?
escape          {unicode}|\\[^\r\n\f0-9a-f]
string1         \"([^\n\r\f\\"]|\\{nl}|{escape})*\"
string2         \'([^\n\r\f\\']|\\{nl}|{escape})*\'
string          {string1}|{string2}
nl              \n|\r\n|\r|\f

Lorsque toutes les définitions sont écrites, la section suivante séparée par le marqueur %% définit les règles qui décrivent un modèle et une action associée. Le modèle est une expression régulière et l'action correspond à du code Ada qui est exécuté. Aflex n'est pas au courant de la grammaire Ada et ne vérifie pas sa validité. Il utilise le code d'action tel quelle et l'écrit dans l'analyseur Ada final. Lorsqu'une action est complexe et doit être écrite en plusieurs lignes, le bloc d'action peut être entouré de { et } (cette syntaxe vient du C, les deux symboles sont bien entendu omis dans le programme final).

L'extrait ci-dessous montre plusieurs règles:

%%
\-                      return '-';
\+                      return '+';
"and"                   { return T_AND; }
"or"                    { return T_OR; }
"not"                   { return T_NOT; }
{string}		{ Set_String (YYLVal, YYText, yylineno, yylinecol); return T_STRING; }

Ici, lorsque le scanner trouve les symboles - ou +, il renvoie les symboles - et +. S'il trouve le mot ''and'', il renvoie le symbole 'T_AND'.

La dernière règle de cet exemple correspondra à une chaîne CSS telle que « red » ou « blue » et on peut obtenir ces résultats lorsque la fonction YYText est appelée. L'action exécutera la procédure Set_String dont le but est de renseigner la variable 'YYLVal' (non représentée dans l'exemple, et pour les curieux, cette procédure est fournie par la partie privée du paquetage parent CSS.Parser, par conséquent, il est visible par le paquetage du scanner généré CSS.Parser.Lexer).

La dernière section du fichier contient le code utilisateur Ada qui sera utilisé pour la génération de code de scanner Ada. Cette section doit contenir une définition de la spécification du paquetage du scanner avec toutes les clauses «with» nécessaires. Il doit également fournir la déclaration de la fonction YYLex qui devrait retourner un type Token.

%%
with CSS.Parser.Parser_Tokens;
package CSS.Parser.Lexer is

   use CSS.Parser.Parser_Tokens;

   function YYLex return Token;

end CSS.Parser.Lexer;

with Ada.Text_IO;
with CSS.Parser.Lexer_dfa;
with CSS.Parser.Lexer_io;
package body CSS.Parser.Lexer is

   use CSS.Parser.Lexer_dfa;
   use CSS.Parser.Lexer_io;

   pragma Style_Checks (Off);
   pragma Warnings (Off);
##

end CSS.Parser.Lexer;

Le corps du paquetage doit également être écrit et il doit contenir un marqueur ## qui est l'endroit où le générateur Aflex écrira le code du scanner avec le corps de la fonction YYLex.

Comme Aflex n'analyse pas le code d'action Ada dans le fichier du scanner, il n'est pas en mesure d'indenter correctement le programme définitif. Le pragma Style_Checks (Off); est utile pour supprimer les avertissements d'indentation que le compilateur pourrait émettre.

Aflex génère également un paquetage <Lexer>_io et un paquetage <Lexer>_dfa qui fournit une aide aux opérations du scanner généré. Le paquetage <Lexer>_dfa définit deux fonctions importantes qui donnent accès au symbole courant sous forme de texte.

package CSS.Parser.Lexer_dfa is
  function YYText return String;
  function YYLength return Integer;
end CSS.Parser.Lexer_dfa;

Par exemple, si le scanner trouve la chaîne d'entrée "red", la fonction YYLex renverra la valeur T\_STRING et la fonction YYText contiendra la chaîne "red".

Le paquetage <Lexer>_io définit la procédure Open_Input qui ouvre le fichier qui doit être analysé. Le paquetage définit également plusieurs autres procédures et fonctions mais la plupart d'entre elles sont dédiées au scanner.

package CSS.Parser.Lexer_io is
  procedure Open_Input (Fname : in String);
end CSS.Parser.Lexer_io;

Génération du code

Le scanner Ada est généré en exécutant l'outil aflex. L'option -m indique à l'outil d'éviter d'émettre des clauses Ada with pour le paquetage Text_IO, l'option -s désactive la règle lex par défaut qui émet un écho d'entrée lorsqu'il n'y a pas de correspondance et l'option -L désactive les directives #line.

   aflex -ms -L css-parser-lexer.l
   gnatchop -w css-parser-lexer.ada

L'outil génère un seul fichier Ada qui contient la spécification et le corps du paquetage et il doit être séparé en utilisant gnatchop pour produire la spécification [css-parser-lexer.ads](https://github.com/stcarrez/ada-css/blob/master/src/parser/css-parser-lexer. annonces) et le corps du paquetage css-parser-lexer.adb.

Écrire un parseur avec Ayacc

Ayacc utilise une grammaire de type BNF pour générer l'analyseur syntaxique écrit en Ada. Le fichier de grammaire est similaire à un fichier de grammaire créé pour Yacc ou Bison mais il contient du code Ada pour les actions de cette grammaire. Le fichier de grammaire commence par un ensemble de définitions qui énumère les symboles disponibles et déclare le type principal pour décrire un état de l'analyseur syntaxique.

Comme pour le fichier scanner, la directive %unit permet de contrôler le nom du paquetage Ada généré. J'ai trouvé très pratique d'utiliser un paquetage parent Ada qui définit divers types et opérations que l'analyseur peut ensuite utiliser. En utilisant %unit et en spécifiant un paquetage enfant, l'analyseur généré peut facilement accéder à ces opérations et types même s'ils sont déclarés dans la partie privée.

%unit CSS.Parser.Parser
%token T_STRING
%token T_AND
%token T_OR
%token T_NOT

L'analyseur généré par Ayacc utilise une pile pour suivre et maintenir l'état lors de l'analyse d'un contenu. Chaque entrée de la pile représente une règle de grammaire qui a été reconnue et il est également possible d'enregistrer certaines information spécifique. Pour cela, la partie déclaration doit déclarer le type Ada YYSType. Ce type décrit l'état et les informations d'une règle de grammaire. L'analyseur ajoute ou supprime des valeurs sur la pile en fonction des règles de grammaire reconnues (après une opération shift ou _reduce_). Le type YYSType ne peut pas être un type limité ni abstrait car la valeur doit être copiée vers ou depuis la variable globale YYLVal.

Dans la définition suivante, le type YYSType est en fait déclaré dans la partie privée du paquetage parent CSS.Parser (encore une fois, ce type est visible pour l'analyseur car c'est l'un de ses packages enfants).

{
   subtype YYSType is CSS.Parser.YYstype;
}

Après la partie déclaration, le séparateur %% introduit une liste de règles de type BNF. Certaines règles de grammaire peuvent être associées à certaines actions qui sont exécutées lorsque la règle de grammaire est reconnue. Avec Ayacc, l'action est un code Ada qui peut contenir des constructions $n qui donnent accès aux valeurs des éléments de cette règle. En fait, les valeurs $n font référence aux valeurs de la pile de l'analyseur et la valeur $$ est la variable YYVal. Lorsqu'une action est exécutée, cela s'appelle une action reduce et tous les éléments de la règle sont remplacés par le résultat $$.

%%
expr :
    expr operator term
       { CSS.Parser.Set_Expr ($$, $1, $3); }
  |
    expr term
       { CSS.Parser.Set_Expr ($$, $1, $2); }
  |
    term  
  ;

Dans cet extrait de règle de grammaire, le $$ fait référence à la valeur de la règle actuelle (YYVal), le $1 contient la valeur du premier élément et ainsi de suite. Il n'est pas possible de dépasser le nombre d'éléments décrits par la règle. Ces valeurs sont de type YYSType. Lorsque l'action de la règle est terminée, les éléments correspondants à la règle sont supprimés de la pile et la valeur actuelle $$ (YYVal) est placée en haut de la pile.

Il est possible d'écrire du code d'action complexe dans le fichier de grammaire mais ce n'est pas très pratique. Dans de nombreux cas, il est plus facile de fournir des procédures ou des fonctions que l'analyseur peut utiliser pour que l'action reste simple.

Après les règles de grammaire, un dernier séparateur %% introduit le code Ada final utilisé par le générateur. Cette dernière section doit contenir le marqueur ## qui représente l'endroit où Ayacc émettra le corps de l'analyseur. Le code Ada doit également déclarer la procédure yyerror qui est appelée par le parseur lorsqu'une erreur de syntaxe est détectée.

Vous trouverez ci-dessous un exemple partiel d'un tel code Ada:

%%
with CSS.Core.Sheets;
package CSS.Parser.Parser is
   Error_Count : Natural := 0;

   function Parse (Content  : in String;
                   Document : in CSS.Core.Sheets.CSSStylesheet_Access) return Integer;

end CSS.Parser.Parser;

with CSS.Parser.Parser_Goto;
with CSS.Parser.Parser_Tokens;
with CSS.Parser.Parser_Shift_Reduce;
with CSS.Parser.Lexer_io;
with CSS.Parser.Lexer;
with CSS.Parser.Lexer_dfa;
with Ada.Text_IO;
package body CSS.Parser.Parser is

   procedure YYParse;

   procedure yyerror (Message : in String := "syntax error");

   procedure yyerror (Message : in String := "syntax error") is
   begin
      Error_Count := Error_Count + 1;
   end yyerror;

   function Parse (Content  : in String;
                   Document : in CSS.Core.Sheets.CSSStylesheet_Access) return Integer is
   begin
      Error_Count := 0;
      CSS.Parser.Lexer_Dfa.yylineno  := 1;
      CSS.Parser.Lexer_Dfa.yylinecol := 1;
      CSS.Parser.Lexer_IO.Open_Input (Content);
      CSS.Parser.Parser.Document := Document;
      YYParse;
      return Error_Count;
   end Parse;

##

end CSS.Parser.Parser;

Pour préparer le scanner à lire un contenu, vous devrez appeler la procédure Open_Input avec le nom du fichier en paramètre. Ensuite, tout ce que vous avez à faire est d'appeler la procédure YYParse qui appellera la fonction YYLex et procédera à l'analyse du fichier d'entrée.

Génération du code

L'analyseur Ada est généré en exécutant l'outil ayacc. L'option -n contrôle la taille de la pile de l'analyseur (la valeur par défaut est 8192). L'option -k indique au générateur de conserver la casse des symboles tels qu'ils sont écrits dans le fichier de grammaire (par défaut le symbole est converti avec une casse mixte). L'option -s affiche des statistiques sur la grammaire. Ceci est utile pour comprendre et vérifier les conflits shift/reduce et reduce/reduce qui pourraient survenir dans la grammaire. L'option -e contrôle l'extension du fichier généré.

  ayacc -n 256 -k -s -e .ada css-parser-parser.y
  gnatchop -w css-parser-parser.ada

L'outil génère un seul fichier Ada qui contient la spécification et le corps du paquetage. Il doit être divisé en utilisant gnatchop pour produire la spécification [css-parser-parser.ads](https://github.com/stcarrez/ada-css/blob/master/src/parser/css-parser-parser. annonces) et le corps du paquetage css-parser-parser.adb.

Aller plus loin

Les deux outils sont très proches des outils lex/flex et yacc/bison, ce qui signifie que la plupart des astuces et de la documentation que vous trouverez sur Lex et Yacc sont communs et applicables à Aflex et Ayacc. L'écriture d'une grammaire est probablement la tâche la plus difficile mais la documentation GNU Bison aide sérieusement.

Examiner comment les fichiers de scanner et de grammaire sont écrits dans d'autres projets peut aider. Ci-dessous une liste non exhaustive de fichiers scanner et grammaire pouvant être traités par Aflex et Ayacc :

Exemples d'analyseurs lexicaux

Exemple Aflex example.l
Exemple Aflex test95.l
Exemple Aflex options.l
Exemple de calcul Ayacc calc_lex.l
Exemple de scanner Ayacc Ada83 ada_lex.l
Scanner Ada CSS, CSS 3 css-parser-lexer.l
Ada CSS, analyseur de règles de définition CSS 3 css-analysis-parser-lexer.l
Outil d'analyse de la mémoire, scanner d'expressions mat-expressions-lexer.l

Exemples de grammaire

Exemple de calcul Ayacc calc.y
Exemple de grammaire Ayacc Ada83 ada.y
Ada CSS, analyseur CSS 3 css-parser-parser.y
Ada CSS, analyseur de règles de définition CSS 3 css-analysis-parser-parser.y
Outil d'analyse de la mémoire, analyseur d'expressions mat-expressions-parser.y

Laissez un commentaire

Pour ajouter un commentaire, vous devez être connecté.