[Un compilateur en F#] Partie 2 : Analyse Syntaxique

La création d’un langage de programmation est quelque chose qui peut paraître insurmontable et abstraite pour les développeurs.
Maintenant que l’on a défini ce qu’était un compilateur dans le premier article, l’étape suivante est de transformer un fichier texte en un arbre syntaxique. Ce dernier représente le code a exécuter.

L’arbre de syntaxe abstraite

L’analyse syntaxique va transformer notre fichier texte en arbre de syntaxe abstraite. C’est cet arbre que nous allons manipuler après. Nous l’appellerons dans la suite de l’article un arbre syntaxique.

Mais qu’est-ce qu’un arbre syntaxique ? L’arbre syntaxique représente de manière hiérarchique notre code pour pouvoir le parcourir et le manipuler plus facilement.

Si nous prenons l’exemple suivant :

1 + 1

Nous pouvons le représenter sous la forme d’un arbre. Ainsi chaque nœud représente une opération. Les feuilles représentent un entier.

Si je prends quelque chose de plus complexe :

mavariable = 1 + 2 * 3

Lorsque l’on va vouloir évaluer notre programme, il suffira de parcourir notre arbre. Pour faire son analyse sémantique, nous allons pouvoir parcourir chaque nœud et vérifier la cohérence du programme. Par exemple, pour le typage, nous pourrons déduire que « mavariable » est de type entier car toutes les opérations sont entières.

Nous avons vu comment faire une représentation visuelle de notre arbre syntaxique. En F#, nous pouvons créer des types récursifs. Ainsi, la représentation précédente en F# peut s’écrire en utilisant des parenthèses.

Affect("Mavariable",  Add(Int(1), Mult(Int(2), Int(3))))

Nous avons :

  • Int() : Qui nous indique une constante entière
  • Mult(,) : Qui nous indique une opération de multiplication entre deux sous arbres.
  • Add(,) : Qui nous indique une opération d’addition entre deux sous arbres
  • Affect(,) : Qui indique une affectation a une variable de la valeur d’un sous arbre.

L’écriture en F# nous permet décrire un arbre de manière beaucoup plus simple que dans certains langages. Ainsi notre type F# ressemblera à :

type Prog = Program of Statement list
and Statement =
| Create of string * Expression
| Assign of Variable * Expression
| Return of Expression
and Expression =
| Int of int
| Bool of bool
| Float of float
| Add of Expression * Expression
| New of Property list
| Use of string
| Call of Variable
| Fun of string list * Statement list
| Get of Variable
| Greater of Expression * Expression
| GreaterOrEqual of Expression * Expression
| Less of Expression * Expression
| LessOrEqual of Expression * Expression
and Property =
| PropertySetter of string * Expression
and Variable =
| Variable of string
| Property of Variable * string

Ce type est récursif. Ainsi nous pouvons fournir des combinaisons infinies de notre syntaxe. C’est grâce à cette récursivité que nous pouvons écrire des syntaxes avec différentes combinaisons.

Lexer

Pour effectuer la première phase « analyse syntaxique » nous avons besoin de deux choses. La première est le lexer et la deuxième le parser. L’un ne va pas sans l’autre.

J’ai utilisé FsLexYacc qui est une implémentation d’un lexer/parser pour F#. Il utilise une syntaxe simple pour définir nos règles et génère un fichier F# associé plus complexe. L’installation et l’utilisation se trouvent à l’adresse suivante : http://fsprojects.github.io/FsLexYacc/.

Une fois que l’on a défini notre langage, il faut identifier tous les mots clés qui composent ce langage. C’est dans cette phase que tous les mots clés vont être spécifiés. Si un mot clé n’est pas défini, alors notre langage ne comprendra pas le fonctionnement.

Le lexer va découper notre fichier texte en une suite de tokens. Un token est une brique de construction de votre langage. Le parser va récupérer ces tokens pour les convertir en arbre syntaxique.

Les tokens représentent :

  • Des mots clés de notre langage if, else, fun, …
  • Des opérations +-/*…
  • Des constantes 1, 2.0, “mastring“
  • Des noms de variable, méthodes, propriétés, …
  • La fin du fichier

Notre lexer va transformer :

var maVariable = 1 + 2 ;

En une suite de token :

VAR NAME EQUAL INT PLUS INT SEMI EOF

Nous retrouvons le token EOF pour indiquer que c’est la fin du fichier. Cela est important pour vérifier que notre fichier est bien formaté.

Pour que mon programme fonctionne je vais avoir besoin de la définition de tokens suivante :

%token <string> NAME
%token <int> INT
%token TRUE FALSE
%token LBRACE RBRACE
%token LPAREN RPAREN
%token PLUS MINUS
%token VAR IF ELSE INCR USE
%token FUN ARROW RETURN
%token GREATER LESS GREATEREQUAL LESSEQUAL
%token SEMI COMMA
%token DESINCR AND DOT EQUAL STRING
%token EOF

La liste de token est à ajouter dans le fichier « fsy » qui contient les définitions des règles de grammaire que nous allons voir plus tard. Mais comme le lexer et le parser son très liés, la liste des tokens est définie avec les règles de grammaire.

Dans le fichier d’extension « fsl » nous allons définir par exemple le token VAR :

| "var"        { VAR }

Les tokens avec valeurs

Un token c’est une expression régulière. Ainsi, vous pouvez récupérer ce qui a été associé à chaque token. Dans le cas de NAME et INT, nous pourrons récupérer plus tard pendant la phase du parser, leurs valeurs associées.

Pour les tokens qui doivent récupérer les valeurs associées, nous allons faire :

| ['0'-'9']+   { INT(int(lexeme lexbuf)) }

La fonction lexeme est la substitution de LexBuffer.LexemeString

let lexeme = LexBuffer<_>.LexemeString

L’instruction « lexeme lexbuf » permet de récupérer la valeur courante dans le buffer. Dans le cas d’un entier, nous avons fait une expression régulière seulement sur des nombres sans virgules. Donc il peut être converti en entier facilement par la méthode int()

Cas du token STRING

Le cas du token STRING est un peu plus complexe. Le token commence à l’ouverture d’un guillemet et va jusqu’à la fermeture du guillemet. Le token STRING peut aussi utiliser un caractère d’échappement pour indiquer que le guillemet fait partie de la valeur et non pas de la fin de la chaine de texte.

Pour commencer nous allons dire que le guillemet va commencer le token STRING.

| ['"']   { stringToken "" false lexbuf }

Avec ce code nous lui indiquons d’aller chercher le contenu en utilisant « stringToken » ci-dessous et non plus notre lexer de départ :

and stringToken str ignorequote = parse

| '"'           { if ignorequote  then (stringToken (str+"\"") false lexbuf) else STRING (str) }
| '\\'          { stringToken str true lexbuf }
| [^ '"' '\\']+ { stringToken (str+(lexeme lexbuf)) false lexbuf }
| eof           { failwith ("String is not terminated") }

Cette méthode va :

  • Si c’est un guillemet, renvoyer le token STRING avec la valeur
  • Sauf si le guillemet a été précédemment échappé, dans ce cas-là nous allons continuer la lecture du buffer
  • Si c’est un caractère d’échappement, nous l’indiquons pour échapper le prochain guillemet
  • Si c’est un autre caractère, nous allons le rajouter à notre valeur.
  • Si c’est la fin de fichier, alors il y a une erreur, il manque le guillemet fermant la chaine de texte. Dans ce cas-là, il faut générer une exception pour indiquer l’erreur. Idéalement il faudrait retrouver le numéro de ligne et l’afficher dans le texte.

Cas des espaces et du retour à la ligne

Du point de vue d’un Lexer, un espace est un caractère comme un autre. Dans certains langages cela peut devenir un token important pour respecter le langage. Mais dans notre cas nous n’avons pas envie d’avoir une liste de token du style :

VAR ESPACE NAME ESPACE EQUAL ESPACE INT ESPACE SEMI ESPACE EOF

Cela va rendre difficile le parsing de notre suite de token. Donc pour cela nous allons consommer le buffer et réappliquer le lexer sur la suite :

| [' ' '\t' ]  { token lexbuf }

Par contre le cas des retours à la ligne n’est pas géré. Pour les retours à la ligne nous allons faire le même traitement. Par contre, nous allons faire avancer le compteur de lignes :

| ('\n' | '\r' '\n')  { newline lexbuf; token lexbuf }

« newLine » permet d’incrémenter la ligne dans « lexbuf » sa définition est :

let newline (lexbuf: LexBuffer<_>) =
lexbuf.EndPos <- lexbuf.EndPos.NextLine

L’intérêt d’incrémenter la ligne de EndPos c’est de pouvoir afficher sur quelle ligne se trouve une erreur de parsing.

Parser

Une fois notre lexer créé il nous reste le parser. Le parser va lui prendre ce flux de token et le traduire en arbre syntaxique.

Pour transformer notre suite de lexem en arbre, nous allons décrire nos règles de grammaire. Les règles de grammaire permettent de définir la forme du langage. Ce sont ces règles qui permettent de définir l’ordre logique de nos tokens. Ce sont elles qui vont transformer :

VAR NAME(Mavariable) EQUAL INT(1) PLUS INT(2) STAR INT(3)

En :

Create("Mavariable",  Add(Int(1), Mult(Int(2), Int(3))))

Tous les tokens précédemment décris vont être réutilisés pour définir notre syntaxe. La grammaire d’un langage permet de définir les règles de forme de notre langage. Ainsi chaque règle va nous dire comment transformer notre langage en arbre syntaxique.

Pour notre exemple, il nous faudra les règles :

statement = VAR NAME EQUAL expression
expression = INT
expression = expression PLUS expression

Avec ces règles de grammaire, nous indiquons que notre ligne se nomme « statement » et qu’il est formé d’un Var, d’un nom, suivis d’un égal et d’une « expression ».

Puis nous spécifions des règles qui indiquent à quoi ressemble une « expression ». Ainsi, une expression peut-être un entier, une addition, une multiplication etc. Dans le cas d’une addition, nous allons indiquer qu’une addition est une composition d’une « expression », un plus et une deuxième « expression ». Ainsi, nous bouclons de manière récursive. Nous aurons des compositions d’addition, soustraction, …

En F# grâce à FsLexYacc nous allons ajouter des règles de grammaire dans le fichier « fsy » :

statement: VAR NAME EQUAL expression          { Create($2, $4) }
expression: INT                               { Int($1) }
| expression PLUS expression        { Add($1, $3) }
…

Le dollar permet de récupérer la valeur :

  • Associé au token qui a été renvoyé par le lexer quand c’est un token come INT on aura la valeur constante.
  • L’arbre syntaxique déjà déduit des autres règles de grammaire. Dans le cas de l’addition, nous allons récupérer tout le sous arbre déjà précédemment déduit des règles de grammaire.

Dans notre fichier fsy nous allons lui spécifier à quel type de base correspond notre arbre syntaxique :

%type < AbstractSyntax.Prog > start

Avec cette ligne nous avons indiqué que « Prog » est l’élément de base. Et que le parsing va commencer par les règles « start »

start: File EOF { $1 }

« start » est la première règle de grammaire de notre langage. Nous indiquons que le fichier contient « File » et se termine par EOF.

File: StatementList { Program(List.rev($1)) }

La règle « File » va déterminer le premier élément de notre arbre syntaxique « Program ». Program contient une StatementList qui va être la liste d’instruction de notre programme.

StatementList: Statement SEMI               { [$1] }
| StatementList Statement SEMI { $2::$1 }

« StatementList » nous indique qu’une instruction est séparée par un point-virgule. La première ligne décrit comment la première ligne est interprétée. Ainsi un « statement » suivi d’un point-virgule indique que c’est une liste de seulement un « statement » Sinon, nous avons une liste de « statements » suivie d’un autre « statement ». Dans ce cas-là il faut ajouter dans la liste notre nouveau « statement ».

La suite

Nous avons maintenant une représentation mémoire du code que l’on souhaite exécuter. Dans le prochain blog post, nous allons regarder comment interpréter cette arbre syntaxique.

Tags: .net, C#, csharp, dot net,

Pas de commentaire

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *