Analyse syntaxique, solutions

L’énoncé est ici.

Un analyseur syntaxique complet pour Pseudo-Pascal

La solution est le fichier parser.mly.

On fait largement appel aux priorités des opérateurs binaires, ceci afin d’éviter trop de règles.

On veut pouvoir analyser l’expression x+y*x > 0 comme on s’y attend : (x+(y*x)) > 0. L’usage des priorités dans ce cas est très classique.

Une autre source d’ambiguïté provient des accès dans les tableaux. Comment interpréter par exemple x + t[i] ? Il semble clair que l’on veut x + (t[i]). C’est à dire que l’opérateur « [ » est en quelque sorte le plus prioritaire de tous.

Enfin, on règle le problème du dangling-else en rendant plus prioritaire le shift qui a la priorité du else que le reduce qui a la priorité du then.

Les déclarations des priorités sont :

%left AND OR
%nonassoc LT LE GT GE EQ NE
%left MINUS PLUS
%left TIMES SLASH
%nonassoc unary_minus NOT
%nonassoc LBRACKET
%nonassoc THEN
%nonassoc ELSE

On a donc du moins prioritaire au plus prioritaire :

  1. d’abord les opérateurs logiques qui sont d’égale priorité.
  2. ensuite les opérateurs de comparaison qui sont « non-associatifs », de sorte que x < y <= z déclenche une erreur.
  3. puis l’addition et la soustraction qui sont « associatifs à gauche », de sorte que les arbres « penchent à gauche ».
  4. puis la multiplication et la division.
  5. puis le moins unaire et la négation logique (opérateurs unaires).
  6. l’indexation dans un tableau vient en dernier.
  7. enfin, dans l’ordre on a then puis else.

Vous pouvez vous demander comment reformuler la grammaire pour régler ces conflits en l’absence de telles règles de priorité. Est-ce toujours possible ?

Enfin, vous pouvez aller jeter un coup d’oeil à l’analyseur lexical (lexer.mll), qui est ici relativement simple. Dans une grammaire plus importante, on utiliserait des tables de hachage pour la correspondance entre les chaînes de caractère à reconnaître (pour les mots-clés du langage, mais aussi les alias de types, etc) et les lexèmes correspondants.

Ce document a été traduit de LATEX par HEVEA