Analyseur lexical et syntaxique des expressions arithmétiques

Soyez le premier à donner votre avis sur cette source.

Vue 13 870 fois - Téléchargée 2 933 fois

Description

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

meknour
Messages postés
10
Date d'inscription
mercredi 11 mai 2011
Statut
Membre
Dernière intervention
25 décembre 2011
-
//test.txt

((23alpha-beta + gamma )/20)
est que l'erreur c'est une erreur de syntaxe???? mais les langage que nous connaissant siqnalent une erreur lexical
et merci
meknour
Messages postés
10
Date d'inscription
mercredi 11 mai 2011
Statut
Membre
Dernière intervention
25 décembre 2011
-
hello,
j'ai une question,dans l'execution de cette programe le compilateur s'affiche pas l'erreur exactement par exemple
//test.txt
2a
c'est une erreur lexical mais le pgm signale une erreur de syntaxe,oui c'est une erreur de syntaxe mais avant que dire s'est une erreur de syntaxe c'est une erreur lex
que fait pour résoudre le probleme?????
MBARKI2005
Messages postés
5
Date d'inscription
mardi 24 mai 2005
Statut
Membre
Dernière intervention
19 décembre 2011
-
Bonjour,
Vous gardez le même projet et vous modifiez les fichiers suivants :

//Categorie.java

package smi5.compilation.anaLex;
/**
* @author samir MBARKI
* @version 06/11/2011
*/
public enum Categorie{
EOF,
$,
NUL,

PAREND,
PARENG,
PLUS,
FOIS,
NOMBRE,
ID,
MOINS,
DIVISE,


E,
EPRIME,
T,
TPRIME,
F;

public static final int MIN=3, MAX=10, MAX1=15;
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;
}
}



//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.MOINS, "");
if(caractereCourant=='/')
return new UniteLexicale(Categorie.DIVISE, "");


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();
}


}


//grammaire.txt

e::=t eprime
eprime::=plus t eprime
eprime::=moins t eprime
eprime::=nul
t::=f tprime
tprime::=fois f tprime
tprime::=divise f tprime
tprime::=nul
f::=id
f::=nombre
f::=pareng e parend


//test.txt

((alpha-beta + gamma )/20)
meknour
Messages postés
10
Date d'inscription
mercredi 11 mai 2011
Statut
Membre
Dernière intervention
25 décembre 2011
-
hello,
je modife le corp de cette application et j'ajoute la division et la soustraction mais il y'a boucoup d'erreur je demande l'aide et merci
MBARKI2005
Messages postés
5
Date d'inscription
mardi 24 mai 2005
Statut
Membre
Dernière intervention
19 décembre 2011
-
Bonjour,
En modifiant la grammaire, vous avez ajouté une unité lexical (moins). Ce qui fait que vous devez mettre à jour Categorie et Scanner pour que ça marche.
Si vous rencontrez des difficultés, prévenez moi.
A+

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.