Analyseur lexical et syntaxique des formules propositionnelles [logique mathématique]

Télécharger le projet
Commenter

Description

C'est un petit source développé dans les séances de tps du module Logique mathématique.
Il s'agit d'un analyseur lexical et syntaxique des formules propositionnelles (logique propositionnelle).

L'analyseur lexical utilisé est un analyseur ascendant type LR sans précédence d'opérateurs (utilisant une pile pour la synthèse de l'arbre de l'analyse syntaxique (RF Compilation)).
La grammaire utilisée pour l'analyseur syntaxique est tres simple:
S -> F
F -> (F) | F & F | F => F | F <=> F | ~F | F|F

En ce qui concerne l'analyse lexicale, tout est basé sur les automates et la classe Regex

En plus, il permet de calculer la profondeur, la longueur et la complexité de la formule propositionnelle.

Source / Exemple : 


using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Windows.Forms;

/**********************************************************************************


     
  •  Analyseur lexical & syntaxique de formules propositionnelles (logique propositionnelle)

    •  
  •  Développé dans les tps du module Logique mathématique (en coop avec Compil)

    •  
  •  Boutemine Oualid (L3)

    •  
  •  Guetteche Ali (M1) 

    •   
  •  *********************************

    •  
  •  Last code modification 19/01/2009

       
      •  
        •  
          •  
            •  
              •  
                •  
                  •  
                    •  
                      •  
                        •  
                          •  
                            •  
                              •  
                                •  
                                  •  
                                    •  
                                      •  
                                        •  
                                          •  
                                            •  
                                              •  
                                                •  
                                                  •  
                                                    •  
                                                      •  
                                                        •  
                                                          •  
                                                            •  
                                                              •  
                                                                •  
                                                                  •  
                                                                    •  
                                                                      •  
                                                                        •  
                                                                          •  
                                                                            •  
                                                                              •  
                                                                                •  
                                                                                  •  
                                                                                    •  
                                                                                      •  
                                                                                        •  
                                                                                          •  
                                                                                            •  
                                                                                              •  
                                                                                                •  
                                                                                                  •  
                                                                                                    •  
                                                                                                      •  
                                                                                                        •  
                                                                                                          •  
                                                                                                            •  
                                                                                                              •  
                                                                                                                •  
                                                                                                                  •  
                                                                                                                    •  
                                                                                                                      •  
                                                                                                                        •  
                                                                                                                          •  
                                                                                                                            •  
                                                                                                                              •  
                                                                                                                                •  
                                                                                                                                  •  
                                                                                                                                    •  
                                                                                                                                      •  
                                                                                                                                        •  
                                                                                                                                          •  
                                                                                                                                            •  
                                                                                                                                              •  
                                                                                                                                                •  
                                                                                                                                                  •  
                                                                                                                                                    •  
                                                                                                                                                      •  
                                                                                                                                                        •  
                                                                                                                                                          •  
                                                                                                                                                            •  
                                                                                                                                                              •  
                                                                                                                                                                •  
                                                                                                                                                                  •  
                                                                                                                                                                    •  
                                                                                                                                                                    • /

// Chaine de teste: A & B | ~( C => (B <=> ~D)) => A
namespace tpLM
{
        public partial class frmMain : Form
        {

                #region Automates
                private string symbols = "()~|=><=>&";     // les symboles  
                // Automate des connecteurs logiques.
                Regex logicalConnectors = new Regex (@"^\||~|&|=\>|\<=\>$");
                // automate de recherche d'identificateurs.
                Regex identifier = new Regex ("^[a-zA-Z_][a-zA-Z0-9_]*$");
                // automates des parentheses.
                Regex parentheses = new Regex (@"^\(|\)$");
                // automates des unités lexicales. [BUG FIXED:\<=\> must appear befor =\> to identify equivalance before implication]
                Regex lexicalUnits = new Regex (@"[a-zA-Z0-9_]+|\(|\)|\||~|&|\<=\>|=\>");
                // automates des caracteres illegaux.
                Regex illegalChars = new Regex (@"[^a-zA-Z0-9()|~&=><_ ]");
                #endregion

                /// <summary>
                /// Retourne la profondeur de l'arbre d'analyse.
                /// </summary>
                /// <param name="root">Le sommet de l'arbre d'analyse.</param>
                /// <returns>La profondeur de l'arbre.</returns>

                public int GetDepth (TreeNode root)
                {
                        int depth = 0;
                        // Appels recursives.
                        switch (root.Nodes.Count)
                        {
                                case (0):
                                        {
                                                depth = 0;
                                                break;
                                        }
                                case (1):
                                        {
                                                depth += GetDepth (root.Nodes [0]) + 1;
                                                break;
                                        }
                                case (2):
                                        {
                                                depth += Math.Max (GetDepth (root.Nodes [0]), GetDepth (root.Nodes [1])) + 1;
                                                break;
                                        }
                        }
                        return depth;
                }

                /// <summary>
                /// Retourne la longueur de la formule
                /// </summary>
                /// <param name="input">La chaine a comparer.</param>
                /// <returns>Longueur</returns>
                public int GetLength (string input)
                {
                        // Nombre parentheses + Variables propositionnelles + connecteurs logiques
                        return GetParenthesis (input) + GetIdentifiers (input) + GetLogicalConnectors (input);
                }

                /// <summary>
                /// Retourne le nombre de parentheses dans la chaine.
                /// </summary>
                /// <param name="input">Chaine a comparer.</param>
                /// <returns>Nombre de parentheses.</returns>
                public int GetParenthesis (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResult = lexicalUnits.Matches (input);
                        // pour chaque mot dans la formule.
                        foreach (Match word in wordsResult)
                        {
                                if (parentheses.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                /// Retourne le nombre d'identificateurs.
                /// </summary>
                /// <param name="input">La chaine a comparer</param>
                /// <returns>Le nombre d'identificateur.</returns>
                public int GetIdentifiers (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResult = lexicalUnits.Matches (input);
                        // pour chaque mot dans la formule.
                        foreach (Match word in wordsResult)
                        {
                                // si c'est un identificateur valide, alors compte le.
                                if (identifier.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                ///  Routine de récupération sur les erreurs lexicales
                /// </summary>
                /// <param name="input">La formule propositionnelle</param>
                /// <returns>Dictionnaire d'erreurs.</returns>
                public Dictionary<int, string> GetLexicalErrors (string input)
                {
                        Dictionary<int, string> errors = new Dictionary<int, string> ();
                        // Recherche des caracteres speciaux non reconnues.
                        MatchCollection illegalchars = illegalChars.Matches (input);
                        foreach (Match illegalchar in illegalchars)
                                errors.Add (illegalchar.Index, illegalchar.Value);
                        // Unités lexicales
                        MatchCollection tookens = lexicalUnits.Matches (input);
                        // Pour chaque mot dans la formule
                        foreach (Match tooken in tookens)
                        {
                                // s'il n'est pas un identificateur ou un connecteur ou une parenthese.
                                if (!identifier.IsMatch (tooken.Value) &&
                                    !parentheses.IsMatch (tooken.Value) &&
                                    !logicalConnectors.IsMatch (tooken.Value))
                                        errors.Add (tooken.Index, tooken.Value);
                        }
                        return errors;
                }

                /// <summary>
                /// Retourne le nombre d'operateurs logiques.
                /// </summary>
                /// <param name="input">la formule propositionnelle.</param>
                /// <returns>Le nombre d'operateur</returns>
                public int GetLogicalConnectors (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResults = lexicalUnits.Matches (input);
                        lblDepth.Text = wordsResults.Count.ToString ();
                        // Pour chaque mots dans la formule
                        foreach (Match word in wordsResults)
                        {
                                // si le mot est un connecteur logique alors.
                                if (logicalConnectors.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                /// Retourne la complexité de la chaine (Nombre de connecteurs).
                /// </summary>
                /// <param name="input">La chaine a comparer.</param>
                /// <returns>La complexité.</returns>
                public int GetComplexity (string input)
                {
                        return GetLogicalConnectors (input);
                }

                /// <summary>
                /// Représente une production (Regle) dans la grammaire de l'analyseur syntaxique.
                /// </summary>
                public struct GrammarRule
                {
                        /// <summary>
                        /// Créer une nouvelle loie pour la grammaire.
                        /// </summary>
                        /// <param name="value">
                        /// Regle.
                        /// </param>
                        /// <param name="Operator">
                        /// Operateur.
                        /// </param>
                        /// <param name="operandsCount">
                        /// Nombre d'operandes.
                        /// </param>
                        public GrammarRule (string value, string Operator, int operandsCount)
                        {
                                this.Operator = Operator;
                                this.Value = value;
                                this.OperandsCount = operandsCount;
                        }
                        /// <summary>
                        /// Operateur.
                        /// </summary>
                        public string Operator;
                        /// <summary>
                        /// Regle.
                        /// </summary>
                        public string Value;
                        /// <summary>
                        /// Nombre d'operandes.
                        /// </summary>
                        public int OperandsCount;
                }
                /// <summary>
                /// Productions de la grammaire
                /// </summary>
                private List<GrammarRule> grammarRules = new List<GrammarRule> ();
                /// <summary>
                /// Pile des opérations de synthèse d'arbre (Synthese ascendante).
                /// </summary>
                private Stack<TreeNode> nodeStack = new Stack<TreeNode> ();
                /// <summary>
                /// Vérifie si la formule est syntaxiquement correcte.
                /// </summary>
                /// <param name="input">La forume a vérifier</param>
                /// <returns>Retourne le resultat de la vérification.</returns>
                private bool ContainsSyntaxicErrors (string input)
                {
                        bool error = false;
                        // Pile d'analyse de la chaine
                        string buffer = string.Empty;
                        // Jetons par l'analyseur lexicale.
                        MatchCollection tookensResult = lexicalUnits.Matches (input);
                        /******* Analyseur Syntaxique Ascendant LR********


                             
  •  sans précédence d'opérateurs

                               
      •                          
        •                          
          •                          
            •                          
              •                          
              • /

                        foreach (Match tooken in tookensResult)
                        {
                                // Etape 1: vérifie le type du jeton: (soit symbole (Connecteur ou parenthese) ou variable propositionnelle.
                                // Si c'est un symbole, l'empiler.
                                if (symbols.Contains (tooken.Value))
                                        buffer += tooken.Value;
                                else
                                {
                                        // Si c'est une variable propositionnelle (Identificateur).
                                        buffer += "F";
                                        // Creer un noeud (Nom = Unité Lexicale)
                                        TreeNode node = new TreeNode (tooken.Value);
                                        // Empiler le noeud.
                                        nodeStack.Push (node);
                                }
                        repeat:                // Etape 2: Substitions sur la pile d'entrée.
                                foreach (GrammarRule rule in grammarRules)
                                {
                                        if (buffer.Contains (rule.Value))
                                        {
                                                // substition en F
                                                buffer = buffer.Replace (rule.Value, "F");
                                                // donner pour nom du node l'operateur
                                                TreeNode parentNode = new TreeNode (rule.Operator);
                                                switch (rule.OperandsCount)
                                                {
                                                        case (1):
                                                                {
                                                                        // dépiler le noeud en somment de la pile
                                                                        TreeNode node1 = nodeStack.Pop ();
                                                                        // Mettre le noeud dans les sous-noeuds du parent.
                                                                        parentNode.Nodes.Add (node1);
                                                                        // Empiler le parent
                                                                        nodeStack.Push (parentNode);
                                                                        break;
                                                                }
                                                        case (2):
                                                                {
                                                                        // dépiler le noeud en somment de la pile
                                                                        TreeNode node1 = nodeStack.Pop ();
                                                                        TreeNode node2 = nodeStack.Pop ();
                                                                        // Mettre le noeud dans les sous-noeuds du parent.
                                                                        parentNode.Nodes.Add (node2);
                                                                        parentNode.Nodes.Add (node1);
                                                                        // Empiler le parent
                                                                        nodeStack.Push (parentNode);
                                                                        break;
                                                                }
                                                }
                                                // Répete l'analyse pour le nouveau buffer.
                                                goto repeat;
                                        }
                                }
                        }
                        // analyse syntaxique correcte.
                        error = (buffer != "F");
                        if (!error)
                        {
                                // Affichage de l'arbre.
                                trvSyntaxicTree.Nodes.Clear ();
                                trvSyntaxicTree.Nodes.Add (nodeStack.Pop ());
                        }
                        return error;
                }

                public frmMain ()
                {
                        InitializeComponent ();
                        // Initialization du dictionnaire des productions de la grammaire.
                        grammarRules.Add (new GrammarRule ("F&F", "&", 2));
                        grammarRules.Add (new GrammarRule ("F|F", "|", 2));
                        grammarRules.Add (new GrammarRule ("F=>F", "=>", 2));
                        grammarRules.Add (new GrammarRule ("F<=>F", "<=>", 2));
                        grammarRules.Add (new GrammarRule ("(F)", "", 0));
                        grammarRules.Add (new GrammarRule ("~F", "~", 1));
                }

                private void btnCalculer_Click (object sender, EventArgs e)
                {
                        // netoyage de la liste d'erreurs lexicales.
                        lstLexicalErrors.Items.Clear ();
                        // Traitement d'erreurs lexicales.
                        Dictionary<int, string> errors = GetLexicalErrors (txtFormule.Text);
                        // S'il existe des erreurs lexicales, on les affiche et on sort
                        if (errors.Count != 0)
                        {
                                // affichage des erreurs : lexicales.
                                foreach (KeyValuePair<int, string> error in errors)
                                        lstLexicalErrors.Items.Add ("Position " + error.Key.ToString () + ": " + error.Value.ToString ());
                                // sort.
                                return;
                        }

                        // Traitement des erreurs syntaxiques.
                        if (ContainsSyntaxicErrors (txtFormule.Text))
                        {
                                lblSyntaxicErrors.Text = "La chaine est syntaxiquement incorrecte";
                                return;
                        }

                        /*** Affichage des resultats. ***/
                        // longueur.
                        lblLenght.Text = GetLength (txtFormule.Text).ToString ();
                        // Complexité.
                        lblComplexity.Text = GetComplexity (txtFormule.Text).ToString ();
                        // Profondeur.
                        lblDepth.Text = GetDepth (trvSyntaxicTree.Nodes [0]).ToString ();
                }
        }
}

Conclusion :


C'est un tres bon exemple pour l'implementation d'une grammaire d'une calculatrice ou d'un traceur de courbes.

Bon prog
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_boutemine)