Théorie des langages

Analyse lexicale et syntaxique avec JavaCC et JJTree1

Jérôme Voinot
[email protected]
http://lifc.univ-fcomte.fr/~voinot

Licence informatique 3ème année

Octobre 2007

Laboratoire d’Informatique de l’Université de Franche-Comté

1 Réalisé à partir de documents de A. Giorgetti

 Principe de la compilation

Grammaire régulière

Texte en Séquence
Analyse
langage d’unités
lexicale Grammaire algébrique
source lexicales

Analyse
Compilation
syntaxique
Sémantique

Texte en Arbre de
Génération
langage syntaxe
de code
cible abstraite

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 2 / 26

 Analyse lexicale
Exemple

Id → ["a"-"z"]+
Op → "+" | "*"
Aff → ":="

som, :=,
som := som Analyse som, +,
+ n * coef lexicale n, *,
coef

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 3 / 26

 Analyse syntaxique
Exemple

Axiome X -> Id := E
E -> T + E | T
T -> F * T | F
F -> Id

:=

som, :=,
Analyse som +
som, +, n,
syntaxique som *
*, coef
n coef

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 4 / 26

 Génération de code
Exemple

* : MULT
+ : ADD
...

:=
LOAD n,R1
som + Génération LOAD coef,R2

som * de code MULT R1,R2

...
n coef

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 5 / 26

 JavaCC

JavaCC signifie Java Compiler Compiler

Générateur d’analyseur lexicaux et syntaxiques en Java
Analyseur lexical (lexer, scanner ) :
Découpe le code en unités lexicales (token)
Ignore le code non significatif (espaces, . . . )
Analyseur syntaxique (parser ) :
Vérifie que la structure du code est conforme aux règles d’une grammaire
hors-contexte
Construit des représentations internes du code sous formes d’arbres syntaxiques
Préprocesseur JJTree inclus dans JavaCC

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 6 / 26

 Mise en œuvre de JavaCC

Gram.jj javacc Gram.jj

GramToken Autres

Manager Gram.java classes

.java Java

javac *.java

*.class

Affichage
essai.txt java Gram
écran

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 7 / 26

 Structure du fichier Gram.jj

PARSER BEGIN(Gram)
public class Gram {
public static void main (String arg[]) throws ParseException {
Copié dans Gram p = new Gram(System.in) ;
Gram.java p.axiome() ;
}
}
PARSER END(Gram)

TOKEN : {
<SALUT : "Bonjour" | "Hello">
}
Liste de règles void axiome() : {
lexicales et }{
<SALUT> unNonTerminal() ("\n"|"\r")* <EOF>
syntaxiques }
void unNonTerminal() : {
}{ ...
}

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 8 / 26

 Analyse lexicale

Objectif : découper le code en lexème (unité lexicale, token)

PROGRAM calcul ;
VAR i : INTEGER ;
BEGIN
i := 1 ;
END

Sortes de lexèmes :
Mots réservés du langage
Identificateurs choisis par le programmeur
Non-lexèmes (whitespaces)
Espaces
Retours à la ligne
Tabulations
...

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 9 / 26

 Analyse lexicale avec JavaCC

Déclarer des unités lexicales

TOKEN : {
<"BEGIN"> | <" ;"> | <":=">
}
Méta-caractères (<, >, ", |, . . . ) utilisables comme lexèmes si entourer avec "
Nommer un ensemble de lexèmes
TOKEN : {
<VARID: ["a"-"z"] ["a"-"z"]*>
}
Non-terminaux lexicaux notés en majuscules par convention

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 10 / 26

 Analyse lexicale avec JavaCC

Associer des actions lexicales

TOKEN : {
<DEBUT: "bEgIN"> {
System.out.println(matchedToken.image.toUpperCase()) ;
}
}
Affichage, remplacement, suppression, . . .
Utiliser des expressions régulières
TOKEN : {
<ID: ["a"-"z"] (["a"-"z"] | ["0"-"9"])*>
}
Langages réguliers (éventuellement infinis) décrit à l’aide des méta-caractères
[, -, ], |, + et *

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 11 / 26

 Effets de l’analyse lexicale avec JavaCC

Construction d’une liste chaı̂née de lexèmes

image next
"som" ":=" ... "coef"

Objet de classe Token

Objet qui stocke le lexème courant

matchedToken dans GramTokenManager.java
token dans Gram.java
Classe Token décrite dans la documentation des classes JavaCC
https://javacc.dev.java.net/doc/apiroutines.html

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 12 / 26

 Lien avec l’analyse syntaxique

PARSER BEGIN(Lexer)
public class Lexer {
public static void main (String arg[]) throws ParseException {
(new Lexer(System.in)).axiome() ;
}
}
PARSER END(Lexer)

TOKEN : {
<ID : ...> // non-terminal lexical
Liste de règles
|
lexicales <AFF : ":=">
}

/* non-terminal syntaxique */
Liste de règles void axiome() : {
}{
syntaxiques avec non-
<ID> <AFF> (<ID>,)*<ID>
terminaux lexicaux }

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 13 / 26

 Sortes de lexèmes

4 sortes de règles lexicales

SKIP : ignore la chaı̂ne reconnue
Exécute une action lexicale sans construire d’objet Token
TOKEN : chaı̂ne reconnue comme un lexème
Retourne cette chaı̂ne à un analyseur syntaxique (ou à un autre extérieur) par
le champ image de la classe Token
MORE : continue la reconnaissance
La chaı̂ne reconnue préfixe le résultat complet
SPECIAL TOKEN : unité lexicale non retournée
Essentiellement pour gérer les commentaires
Pour plus de détails, voir le tutoriel TokenManager
https://javacc.dev.java.net/doc/tokenmanager.html

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 14 / 26

 Cas de SKIP et SPECIAL TOKEN

Pour les caractères “blancs”

SKIP : {
" " | "\t" | "\n" | "\r"
}
Caractères non stockés
Pour les commentaires
SPECIAL TOKEN : {
<LINE COMM: "//" (~["\n","\r"])* (\n" | "\r" | "\r\n")>
}
Commentaires stockés dans le champ specialToken du lexème suivant

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 15 / 26

 Principes de reconnaisance des unités lexicales

La chaı̂ne reconnue est la plus longue chaı̂ne conforme à une expression

régulière
Si plusieurs expressions sont conformes, de même longueur maximale, seule la
première dans l’ordre du fichier est appliquée
La lecture de la fin de fichier provoque la création du lexème EOF

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 16 / 26

 Notion d’état lexical

Permet de simuler un automate

Associer un état à une règle lexicale
Indiquer l’état suivant en fin de règle
<S1> TOKEN : {
...
: <S2>
}
Si aucun état n’est précisé, l’état lexicale suivant est le même
Cas particuliers :
Pour désigner l’état initial, utiliser le mot réservé <DEFAULT>
Pour désigner une règle lexicale applicable dans tout état, utiliser <*>

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 17 / 26

 Recapitulatif

Contenu d’une règle lexicale

Au minimum des expressions régulières
Eventuellement :
Des non-terminaux lexicaux
Des actions à exécuter
L’état lexical suivant
Pour aller plus loin sur ce sujet :
Pour la syntaxe des expression régulières, voir le cours “Détails d’analyse
lexicale avec JavaCC”
Pour le reste, consulter le tutoriel TokenManager
https://javacc.dev.java.net/doc/tokenmanager.html

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 18 / 26

 Syntaxe d’une règle syntaxique

En JavaCC, la règle I → V := E | B s’écrit :

void Instruction() : {
}{
<ID> <AFF> Expression()
| Bloc()
}

Différences :
: au lieu de →
Indentation, non terminaux plus explicites
Blocs de code Java en plus
Relations avec d’autres règles :
Analyse lexicale pour <ID> et <AFF>
Règles syntaxiques pour Bloc() et Expression()

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 19 / 26

 Syntaxe d’une règle syntaxique

Structure générale, format EBNF

String NTnom (. . . ) : {
String s1 = null ;
}{
( s1 = NTautreNom(. . . ) <VIRGULE>
{
String s2 = new String(s1) ;
s2.toUpperCase() ;
}
s1 = NTnom2(. . . ) { ... }
| s1 = NTnom3()
)
<EOF> { return(s1) ; }
}

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 20 / 26

 Principe de l’analyse syntaxique avec JavaCC

Analyse descendante LL(k)

Analyse = cherche si une grammaire engendre une séquence d’unités lexicales
donnée
Descendante = part de l’axiome (L : left to right) et dérive toujours le
non-terminal le plus à gauche (L : left most)
Condition : pas de récursivité gauche (E → E + T )
Conflits entre les règles (choice points)

{X → “b” “a” | Y , Y → “b” “c”}

Levés en lisant k lexèmes à l’avance (lookahead, par défaut k = 1)

Coût lié à k seulement (augmenter k localement seulement)
Pas toujours possible =⇒ changer de grammaire

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 21 / 26

 Construction d’arbres syntaxiques

Arbre d’analyse syntaxique : un noeud par règle syntaxique concrète

Arbre de syntaxe abstraite : nœuds selon la grammaire abstraite et les
besoins de génération de code
Origine des différences
Grammaire abstraite éventuellement ambiguë, pas LL(*)
Grammaire concrète LL(k), avec k minimal
plus longue, moins facile à lire
savoir améliorer la grammaire abstraite
élimination des récursions gauches
pratiquement toujours possible (↑ lookhead)

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 22 / 26

 Arbres syntaxiques avec JavaCC

Préprocesseur JJTree

Gram.jjt JJTree Gram.jj JavaCC

Node.java

Plusieurs classes de noeuds (+ héritage) si l’option JJTree MULTI a pour

valeur true

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 23 / 26

 Annotations JJTree (#)

Exemple
void Instruction() #void : {
}{
Id() <AFF> Expression() #InsNode(2)
| Bloc() #BlocNode(1)
}

Effets :
Pas de noeud associé à Instruction()
Noeud binaire de classe ASTInsNode
Noeud unaire de classe ASTBlocNode
Pour en savoir plus, voir TP2 et lire la documentation de JJTree
https://javacc.dev.java.net/doc/JJTree.html

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 24 / 26

 Génération de code

Deux méthodes possibles

Distribuer une méthode generer() dans toutes les classes de noeuds (+
héritage)
Utiliser le modèle de conception Visitor
Intérêts du modèle de conception
Plusieurs traitements différents (vérification de typage, estimation de la
mémoire requise, . . . ) sans avoir à éditer toutes les classes de noeuds
Prévu dans JJTree (option VISITOR=true)
Pour en savoir plus voir TP3 et suivants

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 25 / 26

 Téléchargement de JavaCC

Disponible sur le site https://javacc.dev.java.net

Pour Linux, télécharger le fichier javacc-4.0.tar.gz
Pour Windows, télécharger le fichier javacc-4.0.zip
Installation
Disposer d’un environnement d’exécution Java 1.2 ou plus
Extraire dans un dossier (par exemple C:\javacc) et ajouter le sous-dossier
bin à la variable système PATH
L’accès à l’outil se fait en ligne de commande (javacc NomFichier.jj)

J. Voinot TL - Analyse lexicale et syntaxique avec JavaCC et JJTree 26 / 26