cette application implémente un petit compilateur des expressions arithmétique. Deux modules sont implémentés l'analyse lexicale et l'analyse syntaxique.
La différence entre cette application et les codes équivalents disponibles sur internet est que l'analyse syntaxique se fait de façon descendente et prédéctive de type LL1.
Dans le module analyse lexicale (classe Scanner), les tokens sont identifiés en implémentant des diagrammes de transitions.
Dans le module analyse syntaxique, la grammaire est définie dans un fichier texte. Ce qui fait la force du Parser est qu'il est générique et peut fonctionner avec n'importe quelle grammaire LL1.
Source / Exemple :
//enum Categorie.java
package smi5.compilation.anaLex;
/**
- @author samir MBARKI
- @version 06/11/2011
- /
public enum Categorie{
EOF,
$,
NUL,
PAREND,
PARENG,
PLUS,
FOIS,
NOMBRE,
ID,
E,
EPRIME,
T,
TPRIME,
F;
public static final int MIN=3, MAX=8, MAX1=13;
public String toString() {
return this.name().toLowerCase();
}
public static Categorie toCategorie(String s) {
for(Categorie c:Categorie.values())
if(c.toString().equalsIgnoreCase(s))
return c;
return null;
}
public boolean estTerminal() {
return ordinal()>=MIN && ordinal()<=MAX;
}
public boolean estNonTerminal() {
return ordinal()>MAX;
}
}
//Classe UniteLexicale.java
package smi5.compilation.anaLex;
/**
- @author samir MBARKI
- @version 06/11/2011
- /
public class UniteLexicale {
private Categorie categorie;
private Object lexeme;
public UniteLexicale(Categorie categorie, Object lexeme) {
this.categorie=categorie;
this.lexeme=lexeme;
}
public Categorie getCategorie() {
return categorie;
}
public String toString() {
return "<"+categorie.toString()+","+lexeme+">";
}
}
//Classe Scanner.java
package smi5.compilation.anaLex;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
/**
- @author samir MBARKI
- @version 06/11/2011
- /
public class Scanner {
private ArrayList<Character> fluxCaracteres;
private int indiceCourant;
private char caractereCourant;
private boolean eof;
public Scanner() {
this("");
}
public Scanner(String nomFich) {
BufferedReader f=null;
int car=0;
fluxCaracteres=new ArrayList<Character>();
indiceCourant=0;
eof=false;
try {
f=new BufferedReader(new FileReader(nomFich));
}
catch(IOException e) {
System.out.println("taper votre texte ci-dessous (ctrl+z pour finir)");
f=new BufferedReader(new InputStreamReader(System.in));
}
try {
while((car=f.read())!=-1)
fluxCaracteres.add((char)car);
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void caractereSuivant() {
if(indiceCourant<fluxCaracteres.size())
caractereCourant=fluxCaracteres.get(indiceCourant++);
else
eof=true;
}
public void reculer() {
if(indiceCourant>0)
indiceCourant--;
}
public UniteLexicale lexemeSuivant() {
caractereSuivant();
while(eof || Character.isWhitespace(caractereCourant)) {
if (eof)
return new UniteLexicale(Categorie.EOF, "");
caractereSuivant();
}
if(Character.isLetter(caractereCourant))
return getID();
if(Character.isDigit(caractereCourant))
return getNombre();
if(caractereCourant=='+')
return new UniteLexicale(Categorie.PLUS, "");
if(caractereCourant=='*')
return new UniteLexicale(Categorie.FOIS, "");
if(caractereCourant=='(')
return new UniteLexicale(Categorie.PARENG, "");
if(caractereCourant==')')
return new UniteLexicale(Categorie.PAREND, "");
return null;
}
public UniteLexicale getID() {
int etat=0;
StringBuffer sb=new StringBuffer();
while(true) {
switch(etat) {
case 0 : etat=1;
sb.append(caractereCourant);
break;
case 1 : caractereSuivant();
if(eof)
etat=3;
else
if(Character.isLetterOrDigit(caractereCourant))
sb.append(caractereCourant);
else
etat=2;
break;
case 2 : reculer();
return new UniteLexicale(Categorie.ID, sb.toString());
case 3 : return new UniteLexicale(Categorie.ID, sb.toString());
}
}
}
public UniteLexicale getNombre() {
int etat=0;
StringBuffer sb=new StringBuffer();
while(true) {
switch(etat) {
case 0 : etat=1;
sb.append(caractereCourant);
break;
case 1 : caractereSuivant();
if(eof)
etat=3;
else
if(Character.isDigit(caractereCourant))
sb.append(caractereCourant);
else
etat=2;
break;
case 2 : reculer();
return new UniteLexicale(Categorie.NOMBRE, sb.toString());
case 3 : return new UniteLexicale(Categorie.NOMBRE, sb.toString());
}
}
}
@Override
public String toString() {
// TODO Auto-generated method stub
return fluxCaracteres.toString();
}
}
//Classe Parser.java
package smi5.compilation.anaSyn;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import smi5.compilation.anaLex.Categorie;
/**
- @author samir MBARKI
- @version 06/11/2011
- /
public class Parser {
private Categorie axiome;
private TreeMap<Categorie,ArrayList<ArrayList<Categorie>>> production;
private TreeMap<Categorie, Boolean> nullable;
private TreeMap<Categorie, TreeSet<Categorie>> premier;
private TreeMap<Categorie, TreeSet<Categorie>> suivant;
private HashMap<ArrayList<Categorie>, TreeSet<Categorie>> premierRegles;
private String fichierproduction;
private Stack<Categorie> pile;
private ArrayList [] [] TA;
public Parser() {
fichierproduction="grammaire.txt";
production=new TreeMap<Categorie, ArrayList<ArrayList<Categorie>>>();
nullable=new TreeMap<Categorie, Boolean>();
premier=new TreeMap<Categorie, TreeSet<Categorie>>();
suivant=new TreeMap<Categorie, TreeSet<Categorie>>();
premierRegles=new HashMap<ArrayList<Categorie>, TreeSet<Categorie>>();
TA=new ArrayList [Categorie.MAX1-Categorie.MAX][Categorie.MAX-Categorie.MIN+2];
pile=new Stack<Categorie>();
}
public void initialiserPile() {
pile.clear();
pile.push(Categorie.$);
pile.push(axiome);
}
public void lireProduction() {
setAxiome();
try {
BufferedReader br=new BufferedReader(new FileReader(fichierproduction));
String ligne=null;
while((ligne=br.readLine())!=null) {
String t1[]=ligne.split("::=");
ArrayList<Categorie> liste=new ArrayList<Categorie>();
Categorie clé=Categorie.toCategorie(t1[0]);
ArrayList<ArrayList<Categorie>> valeur=production.get(clé);
String t2[]=t1[1].split("\\s+");
for(int i=0;i<t2.length;i++)
liste.add(Categorie.toCategorie(t2[i]));
if(valeur==null) {
valeur=new ArrayList<ArrayList<Categorie>>();
valeur.add(liste);
production.put(clé,valeur);
}
else
valeur.add(liste);
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
private void setAxiome() {
for(Categorie c:Categorie.values())
if(c.estNonTerminal()) {
axiome=c;
return;
}
}
public void setNullable() {
nullable.put(Categorie.NUL, true);
for(Categorie c:Categorie.values()) {
if(c.estTerminal())
nullable.put(c, false);
if(c.estNonTerminal()) {
ArrayList<ArrayList<Categorie>> valeur=production.get(c);
for(int i=0;i<valeur.size();i++) {
if(valeur.get(i).get(0).equals(Categorie.NUL))
nullable.put(c, true);
}
}
}
for(Categorie c:Categorie.values()) {
if(c.estNonTerminal()) {
ArrayList<ArrayList<Categorie>> valeur=production.get(c);
for(int i=0;i<valeur.size();i++) {
ArrayList<Categorie> prod=valeur.get(i);
boolean b=true;
for(int j=0;j<prod.size();j++) {
if(nullable.get(c)!=null && nullable.get(c))
break;
if(nullable.get(prod.get(j))==null || !nullable.get(prod.get(j)))
b=false;
}
nullable.put(c, b);
}
}
}
}
public void calculPremier() {
TreeSet<Categorie> ts=new TreeSet<Categorie>();
ts.add(Categorie.NUL);
premier.put(Categorie.NUL, ts);
for(Categorie c:Categorie.values()) {
if(c.estTerminal()) {
TreeSet<Categorie> valeur=new TreeSet<Categorie>();
valeur.add(c);
premier.put(c, valeur);
}
}
boolean changement=false;
do {
changement=false;
for(Categorie c:Categorie.values()) {
if(c.estNonTerminal()) {
TreeSet<Categorie> set=premier.get(c);
if(set==null)
set=new TreeSet<Categorie>();
if(nullable.get(c)) {
if(set.add(Categorie.NUL)) {
changement=true;
premier.put(c, set);
}
}
ArrayList<ArrayList<Categorie>> valeur=production.get(c);
for(int i=0;i<valeur.size();i++) {
ArrayList<Categorie> prod=valeur.get(i);
Categorie elt=prod.get(0);
if(premier.get(elt)!=null && !nullable.get(elt)) {
for(Iterator<Categorie> it=premier.get(elt).iterator();it.hasNext();) {
Categorie ca=it.next();
if(!ca.equals(Categorie.NUL) && set.add(ca)) {
changement=true;
premier.put(c, set);
}
}
}
for(int j=1;j<prod.size();j++) {
if(nullable.get(prod.get(j-1))) {
elt=prod.get(j);
if(premier.get(elt)!=null && !nullable.get(elt)) {
for(Iterator<Categorie> it=premier.get(elt).iterator();it.hasNext();) {
Categorie ca=it.next();
if(!ca.equals(Categorie.NUL) && set.add(ca)) {
changement=true;
premier.put(c, set);
}
}
}
}
else
break;
}
}
}
}
}
while(changement);
}
private boolean ajouterSuivant(Categorie c1, Categorie c2) {
boolean rep=false;
if(c1.estNonTerminal() && c2.estNonTerminal()) {
TreeSet<Categorie> set2=suivant.get(c2);
TreeSet<Categorie> set1=suivant.get(c1);
if(set1==null)
set1=new TreeSet<Categorie>();
if(set2!=null) {
for(Iterator<Categorie> it=set2.iterator();it.hasNext();)
rep=set1.add(it.next());
suivant.put(c1, set1);
}
}
return rep;
}
private boolean ajouterPremier(Categorie c1, Categorie c2) {
boolean rep=false;
if(c1.estNonTerminal()) {
TreeSet<Categorie> set2=premier.get(c2);
TreeSet<Categorie> set1=suivant.get(c1);
if(set1==null)
set1=new TreeSet<Categorie>();
if(set2!=null) {
for(Iterator<Categorie> it=set2.iterator();it.hasNext();) {
Categorie ca=it.next();
if(!ca.equals(Categorie.NUL))
rep=set1.add(ca);
}
suivant.put(c1, set1);
}
}
return rep;
}
public void calculSuivant() {
TreeSet<Categorie> set=new TreeSet<Categorie>();
set.add(Categorie.$);
suivant.put(axiome, set);
for(Categorie c:Categorie.values()) {
if(c.estNonTerminal()) {
ArrayList<ArrayList<Categorie>> productions=production.get(c);
for(ArrayList<Categorie> uneProduction:productions) {
for(int i=0;i<uneProduction.size()-1;i++) {
for(int j=i+1;j<uneProduction.size();j++) {
Categorie c1=uneProduction.get(j);
ajouterPremier(uneProduction.get(i), c1);
if(nullable.get(c1)!=null && !nullable.get(c1))
break;
}
}
}
}
}
boolean continuer=true;
while(continuer) {
continuer=false;
for(Categorie c:Categorie.values()) {
if(c.estNonTerminal()) {
ArrayList<ArrayList<Categorie>> productions=production.get(c);
for(ArrayList<Categorie> uneProduction:productions) {
for(int i=uneProduction.size()-1;i>=0;i--) {
Categorie c1=uneProduction.get(i);
continuer=ajouterSuivant(c1, c);
if(nullable.get(c1)!=null && !nullable.get(c1))
break;
}
}
}
}
}
}
public void calculPremierRegles() {
for(Categorie c:Categorie.values()) {
if(c.estNonTerminal()) {
ArrayList<ArrayList<Categorie>> productions=production.get(c);
for(ArrayList<Categorie> uneProduction:productions) {
TreeSet<Categorie> set=premierRegles.get(uneProduction);
if(set==null)
set=new TreeSet<Categorie>();
for(int i=0;i<uneProduction.size();i++) {
Categorie X=uneProduction.get(i);
TreeSet<Categorie> premierX=premier.get(X);
int j=0;
for(Categorie ca:premierX) {
if(!ca.equals(Categorie.NUL))
set.add(ca);
}
if(nullable.get(X)!=null && !nullable.get(X))
break;
else
if(nullable.get(X) && i==uneProduction.size()-1)
set.add(Categorie.NUL);
}
premierRegles.put(uneProduction, set);
}
}
}
}
public int indice(Categorie c) {
if(c.estNonTerminal()) {
return c.ordinal()-Categorie.MAX-1;
}
if(c.estTerminal()) {
return c.ordinal()-Categorie.MIN;
}
if(c.equals(Categorie.$))
return TA[0].length-1;
return -1;
}
public void remplirTableAnalyse() {
for(int i=0;i<TA.length;i++)
for(int j=0;j<TA[i].length;j++)
TA[i][j]=null;
for(Categorie c:Categorie.values()) {
int n1,n2;
if(c.estNonTerminal()) {
n1=indice(c);
ArrayList<ArrayList<Categorie>> productions=production.get(c);
for(ArrayList<Categorie> uneProduction:productions) {
TreeSet<Categorie> premierX=premierRegles.get(uneProduction);
for(Iterator<Categorie> it=premierX.iterator();it.hasNext();) {
Categorie ca=it.next();
if(ca.equals(Categorie.NUL)) {
TreeSet<Categorie> suivantA=suivant.get(c);
for(Iterator<Categorie> it1=suivantA.iterator();it1.hasNext();) {
Categorie ca1=it1.next();
n2=indice(ca1);
TA[n1][n2]=uneProduction;
}
}
else {
n2=indice(ca);
TA[n1][n2]=uneProduction;
}
}
}
}
}
}
public void analyserSyntaxe(Categorie a) {
int iX,ia;
ia=indice(a);
boolean accepter;
do {
accepter=false;
Categorie X=pile.peek();
if(X.estNonTerminal()) {
iX=indice(X);
ArrayList<Categorie> regle=(ArrayList<Categorie>)TA[iX][ia];
if(regle==null) {
System.err.println("ERREUR DE SYNTAXE!!!");
System.exit(0);
}
else {
pile.pop();
for(int i=regle.size()-1;i>=0;i--) {
Categorie Y=regle.get(i);
if(!Y.equals(Categorie.NUL)) {
pile.push(Y);
}
}
//System.out.println(X+" --> "+regle);
}
}
else
if(X.equals(Categorie.$)) {
if(a==Categorie.$) {
System.out.println("La syntaxe est correcte!!");
return;
}
else {
System.err.println("ERREUR DE SYNTAXE!!!");
System.exit(0);
}
}
else
if(X.equals(a)) {
pile.pop();
accepter=true;
}
else {
System.err.println("ERREUR DE SYNTAXE!!!");
System.exit(0);
}
}
while(!accepter);
}
}
//Classe Main.java
package smi5.compilation.main;
import java.util.ArrayList;
import smi5.compilation.anaLex.Categorie;
import smi5.compilation.anaLex.Scanner;
import smi5.compilation.anaLex.UniteLexicale;
import smi5.compilation.anaSyn.Parser;
/**
- @author samir MBARKI
- @version 06/11/2011
- /
public class Main {
public static void main(String[] args) {
Scanner anaLex=new Scanner("test.txt");
Parser parser=new Parser();
parser.lireProduction();
parser.setNullable();
parser.calculPremier();
parser.calculSuivant();
parser.calculPremierRegles();
parser.remplirTableAnalyse();
parser.initialiserPile();
UniteLexicale ul=null;
do {
ul=anaLex.lexemeSuivant();
//System.out.println(ul);
if(ul.getCategorie().equals(Categorie.EOF))
parser.analyserSyntaxe(Categorie.$);
else
parser.analyserSyntaxe(ul.getCategorie());
}
while(ul.getCategorie()!=Categorie.EOF);
}
}
//Fichier grammaire.txt
e::=t eprime
eprime::=plus t eprime
eprime::=nul
t::=f tprime
tprime::=fois f tprime
tprime::=nul
f::=id
f::=nombre
f::=pareng e parend
//Fichier test.txt
((alpha+beta )*20)
Conclusion :
En conclusion,
La publication de cette application a un but pédagogique, donnant la possibilité aux étudiants de deuxième cycle d'informatique de voir comment sont implémentés les algorithmes étudiés dans le cours de compilation.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.