Évaluation d'une expression arithmétique avec la méthode ll(1)

Soyez le premier à donner votre avis sur cette source.

Vue 6 893 fois - Téléchargée 589 fois

Description

le but de ce projet est implémenté l'algorithme ll(1)

la démarche suivi est:
1) définition de la grammaire:
j'ai pris cette grammaire qui défini mes expressions arithmétique
A --> A+C | A-C | C
C --> C*E | C/E | F
F --> -F |G
G --> (A) | ?(A) | n
2) transformation de cette grammaire pour générer la table LL(1)
ce qui donne en JAVA
---------------------------------------------
private String tableau[][] = new String[][]{
// + , - , * , / , ( , ) , ? , i , #
{null, "CB", null, null, "CB", null, "CB", "CB", null}, /*A*/
{"+CaB", "-CbB", null, null, null, "", null, "", ""}, /*B*/
{null, "ED", null, null, "ED", null, "ED", "ED", null}, /*C*/
{"", "", "*EcD", "/EdD", null, "", null, "", ""}, /*D*/
{null, "-Ee", null, null, "F", null, "F", "F", null}, /*E*/
{null, null, null, null, "(A)f", null, "?(A)g", "i", null} /*F*/};
-----------------------------------------------------
Avec : +,-,*,/*(,),?,i,# c'est des terminaux,
A,B,C,D,E,F c'est des non terminaux,
# indicateur de fin de la chaine et ? fonction mathématique

le code java est constitué de deux classes Lex et CompilLl1
1- Lex parce la chaine en entrée et renvoi le terme courant pour la class CompilLl1
2- CompilLl1 implémente l'algo LL1

Source / Exemple :


package pack;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Lex {

    private final Pattern nombre = Pattern.compile("\\d+(\\.\\d+)?");
    private final Pattern fonction = Pattern.compile("log|cos|sin|sqrt");
    private int pos;
    private double value;
    private String fct;
    private String s;

    public Lex(String str) {
        s = str;
        pos = 0;
        value = 0.0;
    }

    public String getFonction() {
        return fct;
    }
    
    public double  getVal() {
        return value;
    }

    public char nextToken() throws Exception { //fonction qui retourne la prochaine entite lexicale	
        if (pos == s.length()) //si chaine est lu entierement retourner #
        {
            return '#';
        }
        Matcher entM = nombre.matcher(s.substring(pos));//si c est un nombre
        if (entM.lookingAt()) {
            value = Double.parseDouble(entM.group());
            pos += entM.group().length();
            return 'i';
        }
        Matcher fonct = fonction.matcher(s.substring(pos));//si c'est une fonction
        if (fonct.lookingAt()) {
            fct = fonct.group();
            pos += fonct.group().length();
            return '?';
        }
        char c = s.charAt(pos++);
        if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') //operateur
        {
            return c;
        } 
        throw new Exception(); // symble inconnu 
    }
}

import java.util.Stack;

public class CompilLl1 {

    private String tableau[][] = new String[][]{
        //       +      , -      , *      , /      , (     , )     , ?      , i     , #
        {null, "CB", null, null, "CB", null, "CB", "CB", null}, /*A*/
        {"+CaB", "-CbB", null, null, null, "", null, "", ""}, /*B*/
        {null, "ED", null, null, "ED", null, "ED", "ED", null}, /*C*/
        {"", "", "*EcD", "/EdD", null, "", null, "", ""}, /*D*/
        {null, "-Ee", null, null, "F", null, "F", "F", null}, /*E*/
        {null, null, null, null, "(A)f", null, "?(A)g", "i", null} /*F*/};

    private String terminaux = "+-*/()?i#";
    private Stack<Double> pileValeur;
    private Stack<String> pileFonction;

    public void analyseur(String entrée) throws Exception {
        Lex lex = new Lex(entrée);
        Stack<Character> pile = new Stack<Character>();
        pileFonction = new Stack<String>();
        pileValeur = new Stack<Double>();
        pile.push('#');
        pile.push('A');
        char tc = lex.nextToken();
        char sommet = pile.peek();
        while (!pile.empty()) {
            sommet = pile.peek();
            if (sommet == tc) {
                if (tc == 'i'){
                    pileValeur.push(lex.getVal());
                }else{
                    if (tc == '?'){
                        pileFonction.push(lex.getFonction());
                    }
                }
                tc = lex.nextToken();
                pile.pop();
            } else {
                if (sommet >= 'a') {
                    pile.pop();
                    calculer(sommet - 'a');
                } else {
                    int col = terminaux.indexOf(tc);
                    int lig = sommet - 'A';
                    pile.pop();
                    String mdp = tableau[lig][col];
                    if (mdp == null) {
                        throw new Exception();
                    }
                    for (int i = mdp.length() - 1; i >= 0; i--) {
                        pile.push(mdp.charAt(i));
                    }
                }
            }
        }
        System.out.println("ok res = "+ pileValeur.pop());
    }

    private void calculer(int i) throws Exception {
        switch (i) {
            case 0: {
                double v2 = pileValeur.pop();
                double v1 = pileValeur.pop();
                pileValeur.push(v1+v2);
                break;
            }
            case 1: {
                double v2 = pileValeur.pop();
                double v1 = pileValeur.pop();
                pileValeur.push(v1-v2);
                break;
            }
            case 2: {
                double v2 = pileValeur.pop();
                double v1 = pileValeur.pop();
                pileValeur.push(v1*v2);
                break;
            }
            case 3: {
                double v2 = pileValeur.pop();
                double v1 = pileValeur.pop();
                pileValeur.push(v1/v2);
                break;
            }
            case 4: {
                double v1 = pileValeur.pop();
                pileValeur.push(-v1);
                break;
            }
            case 5: {
                break;
            }
            case 6: {
                double v1 = pileValeur.pop();
                pileValeur.push(fonction(pileFonction.pop(),v1));
                break;
            }
        }
    }

    private Double fonction(String ftc, double val) throws Exception{
        if (ftc.equalsIgnoreCase("log")) return Math.log(val); 
        if (ftc.equalsIgnoreCase("cos")) return Math.cos(val); 
        if (ftc.equalsIgnoreCase("sin")) return Math.sin(val); 
        if (ftc.equalsIgnoreCase("sqrt")) return Math.sqrt(val); 
        throw new Exception(); 
    }
}

import java.util.logging.Level;
import java.util.logging.Logger;

public class Annalyse {
    public Annalyse() {
    }

    public static void main(String[] args) {
        try {
            CompilLl1 compilLl1 = new CompilLl1();
            compilLl1.analyseur("sqrt(5+6)+5-5*2-(2+3)+11-1.5+log(5)");
        } catch (Exception ex) {
            Logger.getLogger(Annalyse.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
}

Codes Sources

A voir également

Ajouter un commentaire Commentaire
je vous remercie, ça m'était trés utils

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.