Le but de ce TD est de présenter les expressions rationnelles (ou régulières) permettant de caractèriser certains lexèmes.
Dans un premier temps, nous utiliserons la commande shell grep afin de réaliser la recherche de lignes contenant, par exemple, la chaîne de caractères IPV6 sans tenir compte de la casse, les lignes commençant par une variable en majuscule suivie du signe d'égalité, ... et ceci dans la sous-arborescence du répertoire /etc.
Puis nous utiliserons l'outil visual_regexp afin de tester des expressions rationnelles permettant de reconnaître, par exemple, les identificateurs du C, les chaînes de caractères du langage Pascal ou du langage C, ...
Enfin, nous écrirons un programme Java (utilisation du paquetage java.util.regex) qui permet de reconnaître dans un fichier (par exemple, exempleURLExtractor.txt) spécifié en argument les URL HTTP.

Des exemples pour les trois exercices de ce TD sont disponibles ici.

Le but de ce TD est d'implanter, à la main, un analyseur lexical pour des règles simplistes, puis d'utiliser un générateur de compilateurs Tatoo afin de récupérer des lexèmes reçus sur un flot.
Dans un premier temps, nous réaliserons un simulateur d'analyseur lexical en utilisant les classes DFAabstar et DFAa qui implantent des automates à états finis (interface DFA) reconnaissant, respectivement, (ab)* et a, écrire un analyseur lexical (à partir de la classe LexerSkeleton) qui reconnaît dans une chaîne de caractères passée en argument les tokens correspondants à ces classes.
Dans un second temps, à l'aide du générateur de compilateurs Tatoo, écrire un programme qui extrait les commentaires Java d'un fichier dont le nom est reçu en argument sur la ligne de commande (utilisez les expressions rationnelles définies lors du TD précédents).
Enfin, écrire un programme équivalent qui va utiliser un état indiquant si l'analyseur lexical est en dehors d'un commentaire, dans un commentaire sur une seule ligne ou dans un commentaire sur plusieurs lignes et qui utilise ces états afin de déterminer l'ensemble des règles à utiliser.

Des exemples pour les exercices de ce TD sont disponibles ici.

L'objectif de ce TD est de se familiariser avec les grammaires algébriques, les arbres de dérivation et la désambiguïsassions des grammaires.
Nous écrirons ainsi des grammaires reconnaissant le langage des palindromes (mots non vides qui peuvent se lire de droite à gauche et de gauche à droite) sur l'alphabet {a, b}, le langage des mots décrit par l'expression rationnelle a*b* contenant strictement plus de a que de b et nous donnerons l'arbre de dérivation du mot aaaabb pour cette seconde grammaire.
Nous verrons dans un second temps, quelques grammaires ambiguës que nous désambiguïserons.

Nous allons, durant ce TD, voir comment construire une table d'analyse LL(1) et pour ce faire, nous commencerons par construire les ensembles annulable, premier et suivant des grammaires.
En considérant trois grammaires différentes, nous calculerons dans un premier temps les ensembles annulable, premier et suivant puis nous construirons la table d'analyse LL de ces grammaires. Enfin, nous vérifierons si certains mots sont reconnus ou nous justifierons le fait que la grammaire n'est pas LL.

L'objectif de ce td est d'implantater un parser LL(1) dont nous avons construit les tables lors du td précédent.
Nous verrons ainsi dans un premier temps, l'écriture manuelle d'un analyseur syntaxique reconnaissant la grammaire G2 du TD précédent à partir d'un pseudo code et en supposant que les lexèmes sont retournés par un Reader.
Dans un second temps, on constuira l'arbre de syntaxe abstrait d'une expression que l'on parcoura à l'aide du patron de conception visiteur.
Enfin, on écrira les méthodes permettant de réaliser l'évaluation d'une expression saisie au clavier.

Le but de ce TD est de construire l'automate des items LR d'une grammaire, ainsi que la table d'analyse correspondante qui permet de tester si un mot appartient ou non au langage reconnu par la grammaire. Pour ce faire, nous commencerons, de même que dans le TD précédent, par construire les ensembles annulable, premier et suivant des grammaires.
En considérant trois grammaires différentes, nous calculerons dans un premier temps les ensembles annulable, premier et suivant puis nous construirons la table des items LR(0). Dans un second temps, nous construirons la table d'analyse SLR(1) correspondante. Enfin, nous vérifierons si certains mots donnés sont reconnus ou non et nous justifierons le type de la grammaire (par exemple, LL(1), LR(0), SLR(1), LR(1) ou LALR(1)).